php 实现hashtable
PHP 实现哈希表
哈希表（Hash Table）是一种高效的数据结构，通过键值对（key-value）存储数据。PHP 本身提供了关联数组（associative array），其底层实现就是哈希表。如果需要手动实现哈希表，可以参考以下方法。
使用 PHP 数组模拟哈希表
PHP 的关联数组天然支持哈希表的功能，可以直接使用：
$hashTable = [];
$hashTable['key1'] = 'value1';
$hashTable['key2'] = 'value2';
// 访问值
echo $hashTable['key1']; // 输出: value1
// 检查键是否存在
if (isset($hashTable['key1'])) {
echo 'Key exists';
}
// 删除键值对
unset($hashTable['key1']);手动实现哈希表结构
如果需要更底层的实现，可以模拟哈希表的冲突处理（如链地址法）：
class HashTable {
private $buckets;
private $size = 10;
public function __construct() {
$this->buckets = array_fill(0, $this->size, []);
}
private function hash($key) {
return crc32($key) % $this->size;
}
public function set($key, $value) {
$index = $this->hash($key);
$this->buckets[$index][$key] = $value;
}
public function get($key) {
$index = $this->hash($key);
return $this->buckets[$index][$key] ?? null;
}
public function delete($key) {
$index = $this->hash($key);
unset($this->buckets[$index][$key]);
}
}
// 使用示例
$ht = new HashTable();
$ht->set('name', 'Alice');
echo $ht->get('name'); // 输出: Alice
$ht->delete('name');处理哈希冲突
链地址法（Chaining）是一种常见的冲突处理方法，将冲突的键值对存储在同一个桶的链表中：
class HashTableWithChaining {
private $buckets;
private $size = 10;
public function __construct() {
$this->buckets = array_fill(0, $this->size, []);
}
private function hash($key) {
return crc32($key) % $this->size;
}
public function set($key, $value) {
$index = $this->hash($key);
foreach ($this->buckets[$index] as &$pair) {
if ($pair[0] === $key) {
$pair[1] = $value;
return;
}
}
$this->buckets[$index][] = [$key, $value];
}
public function get($key) {
$index = $this->hash($key);
foreach ($this->buckets[$index] as $pair) {
if ($pair[0] === $key) {
return $pair[1];
}
}
return null;
}
}性能优化
调整哈希表的大小和哈希函数可以减少冲突：
private function hash($key) {
return abs(crc32($key) % $this->size);
}动态扩容可以在负载因子过高时提升性能：
public function set($key, $value) {
if ($this->count / $this->size > 0.7) {
$this->resize();
}
// ... 其他逻辑
}
private function resize() {
$this->size *= 2;
$newBuckets = array_fill(0, $this->size, []);
foreach ($this->buckets as $bucket) {
foreach ($bucket as $pair) {
$index = $this->hash($pair[0]);
$newBuckets[$index][] = $pair;
}
}
$this->buckets = $newBuckets;
}通过以上方法，可以在 PHP 中实现一个基本的哈希表结构。
