PHP 实现 Hash 表
Hash 表(HashTable)又称散列表,通过把关键字 Key 映射到数组中的一个位置来访问记录,以加快查找的速度。这个映射函数称为 Hash 函数,存放记录的数组称为 Hash 表。
Hash 表结构
Hash 表的实现步骤如下:
- 创建一个固定大小的数组用于存放数据。
- 设计 Hash 函数。
- 通过 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 开始)。
修改后的插入算法流程如下:
- 使用 Hash 函数计算关键字的 Hash 值,通过 Hash 值定位到 Hash 表的指定位置。
- 如果此位置已经被其他节点占用,把新节点的 $nextNode 指向此节点,否则把新节点的 $nextNode 设置为 NULL。
- 把新节点保存到 Hash 表的当前位置。
修改后的查找算法流程如下:
- 使用 Hash 函数计算关键字的 Hash 值,通过 Hash 值定位到 Hash 表的指定位置。
- 遍历当前链表,比较链表中每个节点的关键字与查找关键字是否相等。如果相等,查找成功。
- 如果整个链表都没有要查找的关键字,查找失败。