PHP 手动实现 Hash 表：从基础原理到拉链法处理冲突

程一诺

发布时间：2026-10-13| 4人浏览过

原创

Hash 表（散列表）是高性能数据存储的核心结构。本文演示如何仅用 PHP 内置特性手动构建一个 Hash 表。通过引入 SplFixedArray 优化底层存储效率，并利用链表技术（拉链法）妥善解决哈希冲突导致的覆盖问题，为理解其 O(1) 时间复杂度及实际应用场景提供直观参考。

Hash 表基本原理

Hash 表是一种通过映射函数将任意长度的 Key 转换为固定长度整数（Hash 值），进而定位数据在数组中存储位置的数据结构。理想的 Hash 表查找、插入和删除的时间复杂度均为 O(1)。但在实际实现中，不同 Key 可能产生相同的 Hash 值，这被称为哈希冲突。

基础版实现

在 PHP 中实现 Hash 表时，可以使用标准的 Array 或更底层的 SplFixedArray。SplFixedArray 因为具有固定的大小且内存布局更接近 C 语言数组，通常比普通的关联数组具有更高的遍历效率和更小的内存开销。

第一步：构建基础 Hash 表类

目的：建立一个基于数组的简单 Hash 表，支持基本的存取操作。

入口：定义 HashTable 类。

动作：

初始化存储区：在构造函数中使用 SplFixedArray($this->size) 创建定长数组。指定尺寸可避免动态扩容的开销。
实现 Hash 算法：编写私有方法 simpleHash($key)。示例采用 ASCII 累加法，即将 Key 字符串中每个字符的 ASCII 码相加后取余，得到索引位置。虽然此算法在复杂场景下冲突率高，但足以演示原理。
设置与获取：set() 直接写入计算出的索引位置；get() 根据相同逻辑读取索引处的值。

<?php
class HashTable{
  private $arr = array();
  private $size = 10;
  public function __construct(){
    //SplFixedArray创建的数组比一般的Array()效率更高，因为更接近C的数组。创建时需要指定尺寸
    $this->arr = new SplFixedArray($this->size);
  }
  /**
   * Description: 简单hash算法。输入key，输出hash后的整数
   * @param $key
   * @return int
   */
  private function simpleHash($key){
    $len = strlen($key);
    //key中每个字符所对应的ASCII的值
    $asciiTotal = 0;
    for($i=0; $i<$len; $i++){
      $asciiTotal += ord($key[$i]);
    }
    return $asciiTotal % $this->size;
  }
  /**
   * Description: 赋值
   * @param $key
   * @param $value
   * @return bool
   */
  public function set($key, $value){
    $hash = $this->simpleHash($key);
    $this->arr[$hash] = $value;
    return true;
  }
  /**
   * Description: 取值
   * @param $key
   * @return mixed
   */
  public function get($key){
    $hash = $this->simpleHash($key);
    return $this->arr[$hash];
  }
  public function getList(){
    return $this->arr;
  }
  public function editSize($size){
    $this->size = $size;
    $this->arr->setSize($size);
  }
}
?>

第二步：测试基础功能的局限性

目的：验证基础实现中存在的数据丢失问题。

动作：循环存入大量 Key-Value 对。

结果观察：由于简单的 ASCII 累加哈希算法，不同的 Key 极有可能落入同一个数组索引。当执行 set 时，新值会直接覆盖旧值，导致前一条数据丢失。这表明基础数组方案无法处理哈希冲突。

<?php
//测试1
$arr = new HashTable();
for($i=0; $i<15; $i++){
  $arr->set('key'.$i, 'value'.$i);
}
print_r($arr->getList());

//测试2
$arr->editSize(15);
for($i=0; $i<15; $i++){
  $arr->set('key'.$i, 'value'.$i);
}
print_r($arr->getList());
?>

进阶版：使用拉链法解决冲突

为了解决上述覆盖问题，需要采用“拉链法”（Chaining）。其核心思想是将具有相同 Hash 值的 Key-Value 对链接到一个单链表中。数组中的每个位置存储的是链表的头节点，而非单一值。

第三步：构建节点与高级 Hash 表类

目的：实现能够容纳多元素的冲突处理结构。

入口：定义 HashNode 类和重构后的 NewHashTable 类。

动作：

定义 Node 节点：HashNode 包含 $key、$value 和指向下一个节点的 $nextNode。这构成了链表的基本单元。
修改 Set 逻辑：在 set() 中，先计算 Hash 值并获取该位置的现有链表头节点。若存在，则新建一个 Node 作为新的头节点，将其 nextNode 指向旧头节点（头插法）。这样无需遍历链表即可在 O(1) 时间内完成插入。
修改 Get 逻辑：在 get() 中，从链表头开始遍历。逐个比对 $current->key 是否匹配目标 Key。若找到则返回值；若遍历完仍未找到或链表为空，则返回 NULL。此操作的最坏时间复杂度降为 O(n)，其中 n 为冲突链表的长度。

<?php
class HashNode{
  public $key;
  public $value;
  public $nextNode;
  public function __construct($key, $value, $nextNode=Null){
    $this->key = $key;
    $this->value = $value;
    $this->nextNode = $nextNode;
  }
}
class NewHashTable{
  private $arr;
  private $size = 10;
  public function __construct(){
    $this->arr = new SplFixedArray($this->size);
  }
  private function simpleHash($key){
    $asciiTotal = 0;
    $len = strlen($key);
    for($i=0; $i<$len; $i++){
      $asciiTotal += ord($key[$i]);
    }
    return $asciiTotal % $this->size;
  }
  public function set($key, $value){
    $hash = $this->simpleHash($key);
    if(isset($this->arr[$hash])){
      $newNode = new HashNode($key, $value, $this->arr[$hash]);
    }else{
      $newNode = new HashNode($key, $value, null);
    }
    $this->arr[$hash] = $newNode;
    return true;
  }
  public function get($key){
    $hash = $this->simpleHash($key);
    $current = $this->arr[$hash];
    while(!empty($current)){
      if($current->key == $key){
        return $current->value;
      }
      $current = $current->nextNode;
    }
    return NULL;
  }
  public function getList(){
    return $this->arr;
  }
}
?>

第四步：测试拉链法效果

目的：确认不同 Key 即使 Hash 值相同也能共存。

动作：向 NewHashTable 中存入较多数据（如 30 个元素），并进行查询。

结果观察：通过 print_r 查看列表，可以发现数组的各个槽位中存储的是 HashNode 对象。调用 get('key3') 时，系统会自动沿着链表查找正确的 Value，而不会被其他数据覆盖。这证明了拉链法在维护数据完整性方面的有效性。

<?php
//测试1
$newArr = new NewHashTable();
for($i=0; $i<30; $i++){
  $newArr->set('key'.$i, 'value'.$i);
}
print_r($newArr->getList());
var_dump($newArr->get('key3'));
?>

总结

通过上述步骤，我们从零构建了一个具备基础功能的 Hash 表，并成功应用拉链法解决了哈希冲突带来的数据覆盖难题。这种底层实现有助于深入理解 PHP 内置 HashTable（如用于 Map/Dict 类型的结构）的工作原理。以上就是 PHP 手动实现 Hash 表功能及解决冲突的详细内容，更多关于 PHP 数据结构优化的资料请关注本站其它相关文章！