扎啤伯格

Hash 表（HashTable）又称散列表，通过把关键字 Key 映射到数组中的一个位置来访问记录，以加快查找的速度。这个映射函数称为 Hash 函数，存放记录的数组称为 Hash 表。

Hash 表结构

Hash 表的实现步骤如下：

1. 创建一个固定大小的数组用于存放数据。
2. 设计 Hash 函数。
3. 通过 Hash 函数把关键字 Key 映射到数组的某个位置，并在此位置上进行数据存取。

PHP 具体实现

首先创建一个 HashTable 类。

<?php
class HashTable 
{
    private $buckets;   // 用于存储数据的数组
    private $size = 10; // $buckets 数组大小

    public function __construct()
    {
        $this->buckets = new SplFixedArray($this->size);    
    }

    /**
     * Hash 函数
     */
    private function hashfunc($key)
    {
        $strlen = strlen($key);
        $hashval = 0;
        for ($i = 0; $i < $strlen; $i++) {
            $hashval += ord($key[$i]);
        }
        return $hashval % $this->size;
    }

    /**
     * 插入数据
     */
    public function insert($key, $value)
    {
        $index = $this->hashfunc($key);
        // 新建一个节点
        if (isset($this->buckets[$index])) {
            $newNode = new HashNode($key, $value, $this->buckets[$index]);
        } else {
            $newNode = new HashNode($key, $value, null);
        }
        $this->buckets[$index] = $newNode;
    }

    /**
     * 查找数据
     */
    public function find($key)
    {
        $index = $this->hashfunc($key);
        $current = $this->buckets[$index];
        while (isset($current)) {           // 遍历当前链表
            if ($current->key == $key) {    // 比较当前节点的关键字
                return $current->value;     // 查找成功
            }
            $current = $current->nextNode;  // 比较下一个节点
        }
        return null; // 查找失败
    }
}

节点需要保存关键字 Key 和 Value，同时还要记录具有相同 Hash 值的节点。所以创建一个 HashNode 类存储这些信息。

<?php
class HashNode
{
    public $key;        // 节点关键字
    public $value;      // 节点值
    public $nextNode;   // 指向具有相同 Hash 值节点的指针

    public function __construct($key, $value, $nextNode = null)
    {
        $this->key = $key;
        $this->value = $value;
        $this->nextNode = $nextNode;
    }
}

测试代码如下：

<?php
$ht = new HashTable();
$ht->insert('key1', 'value1');
$ht->insert('key12', 'value12');
echo $ht->find('key1');
echo $ht->find('key12');

/** 
*   相同 Hash 值的节点会被连接在同一个链表。
*   
*   HashNode Object
*   (
*       [key] => key12
*       [value] => value12
*       [nextNode] => HashNode Object
*           (
*               [key] => key1
*               [value] => value1
*               [nextNode] => 
*           )
*   
*   )
*/

Hash 表冲突

冲突的原因是：不同的关键字通过 Hash 函数计算出来的 Hash 值相同。通过打印 “key1” 和 “key12” 的 Hash 值，可以发现它们都是 8。也就是说 “value1” 和 “value12” 同时被存储在 Hash 表的第 9 个位置上（索引从 0 开始）。

修改后的插入算法流程如下：

1. 使用 Hash 函数计算关键字的 Hash 值，通过 Hash 值定位到 Hash 表的指定位置。
2. 如果此位置已经被其他节点占用，把新节点的 $nextNode 指向此节点，否则把新节点的 $nextNode 设置为 NULL。
3. 把新节点保存到 Hash 表的当前位置。

修改后的查找算法流程如下：

1. 使用 Hash 函数计算关键字的 Hash 值，通过 Hash 值定位到 Hash 表的指定位置。
2. 遍历当前链表，比较链表中每个节点的关键字与查找关键字是否相等。如果相等，查找成功。
3. 如果整个链表都没有要查找的关键字，查找失败。