【php】数据结构-PHP 哈希表(Hash Table)的实现

​这篇文章主要介绍一下哈希表（Hash Table）的实现原理，哈希表(Hash Table) 也叫散列表，它通过把关键码值(key-value)映射到表中一个位置来访问，以加快其查找的速度。这个映射函数叫做哈希函数，存放记录的数组叫哈希表（Hash Table）。

1.哈希表(Hash Table)的特点

• 访问速度很快，将指定的 Key 都映射到一个地址上，在访问时，可以直接跳到那个地址。
• 空间换时间，哈希表充分体现了空间换时间的思想。
• 无序，哈希表是无序的。它为了能快速访问元素，值是根据哈希函数直接找到存储地址的。
• 可能会产生哈希冲突，不同的值通过哈希函数可能存在相同值的情况，这时就需要采用冲突解决方案。

2.哈希函数的原理

下面举几个简单的 哈希函数 实现原理，主要说明如何将不同类型的值转化为一个小整数(小整数可以在数组中表示索引，即表示地址)：

2.1 大整数转化为小整数(数组索引)

一个最简单的办法是 模(mod) 一个 素数：

下面是有人研究好的一个列表，其中 lwr 表示你取值范围的下界，upr 表示你取值范围的上界，prime 表示该范围的值对该值求模区分度最好：

2.2 浮点型转化为小整数(数组索引)

可以先将浮点型扩大倍数转化为整型，然后按照大整数的方式处理即可。

2.3 字符串

十进制表示数字：166 = 1 * 10^2 + 6 * 10^1 + 6 * 10^0
二十六进制表示字母：code = c * 26^3 + o * 26^2 + d * 26^1 + e * 26^0
hash(code) = (c * B^3 + o * B^2 + d * B^1 + e * B^0) % M
hash(code) = ((((c * B) + o) * B + d) * B + e) % M

2.4 用 PHP 代码实现的 HashCode 类

下面这个类可以实现输入一个字符串，然后返回一个正整数的哈希值：

<?php
trait HashCode
{
function hashCode64($str) {
$str = (string)$str;
$hash = 0;
$len = strlen($str);
if ($len == 0 )
return $hash;
for ($i = 0; $i < $len; $i++) {
$h = $hash << 5;
$h -= $hash;
$h += ord($str[$i]);
$hash = $h;
$hash &= 0x7FFFFFFF;
}
return $hash;
}
}

3. 定义一个带有哈希函数的 Student 类

为了方便对哈希值的理解，下面定义一个学生类(Student)，该类中包含 年级(grade)、班级(class)、姓氏(firstName)、名字(lastName)：

<?php
class Student
{
use HashCode;
//学生年级
public $grade = null;
//班级
public $class = null;
//姓氏
public $firstName = null;
//名字
public $lastName = null;
public function __construct($grade, $class, $firstName, $lastName) {
$this->grade = $grade;
$this->class = $class;
$this->firstName = $firstName;
$this->lastName = $lastName;
}
/**
* 生成哈希值
* 下面只是一个简单的展示过程，实际需要根据严格的数学运算来具体实现
*/
public function hashCode(){
$B = 31;
$hash = 0;
//对于小整型来说不需要转化
$hash = $hash * $B + $this->grade;
$hash = $hash * $B + $this->class;
//对于字符串来说需要 hashCode 一下
$hash = $hash * $B + $this->hashCode64($this->firstName);
$hash = $hash * $B + $this->hashCode64($this->lastName);
return $hash;
}
}

4.演示哈希值输出

下面给出 output_hash_table.php 代码：

<?php
require  'Student.php';
$arr = [];
//学生1
$student = new Student(5,3,"qin","shixian");
$arr[$student->hashCode()] = 'student-info';
echo $student->hashCode();
echo "n";
//学生2
$student1 = new Student(5,4,"zhu","geliang");
$arr[$student1->hashCode()] = 'student1-info';;
echo $student1->hashCode();
echo "n";
//学生3
$student2 = new Student(3,2,"zhang","xiaoliang");
$arr[$student2->hashCode()] = 'student2-info';
echo $student2->hashCode();
echo "n";
print_r($arr);

输出如下：

5.哈希表(Hash Table)原理图和解决冲突示示意图

6.定义哈希表

下面定义了一个 HashTable 类，其中包含了 hash() 函数用来生成哈希数组 $hashTable 中的索引值的，然后 $hashTable 中元素是用 基于二分搜索树实现的Map 来解决哈希冲突的，相当于哈希表中元素的值存放在一个 Map 中(也可以放在红黑树、链表中)：

<?php
require $root . '/Map/BinarySearchTreeMap.php';
require 'HashCode.php';
class HashTable
{
use HashCode;
private $hashTable;
private $m;
private $size;
public function __construct($m = 53) {
$this->m = $m;
$this->size = 0;
for ($i = 0; $i < $m; $i++) {
$this->hashTable[$i] = new BinarySearchTreeMap();
}
}
/**
* 将 k 转化成哈希数组里面的索引
* @param $k
* @return int
*/
private function hash($k) {
return $this->hashCode($k) % $this->m;
}
/**
* 获取哈希表元素个数
* @return int
*/
public function getSize() {
return $this->size;
}
/**
* 向哈希表中添加 key-value
* @param $k
* @param $v
*/
public function add($k, $v) {
$hashKey = $this->hash($k);
//判断哈希表值对应的连表中是否包含某个值
if ($this->hashTable[$hashKey]->contains($k)) {
//存在，则修改原来k对应的值
$this->hashTable[$hashKey]->set($k, $v);
} else {
//若不存在，则新增原来的值
$this->hashTable[$hashKey]->add($k, $v);
$this->size++;
}
}
/**
* 删除哈希表中 k 对应的值
* @param $k
*/
public function remove($k) {
$hashKey = $this->hash($k);
$reValue = null;
if ($this->hashTable[$hashKey]->contains($k)) {
//若包含对应的key才删除
$reValue = $this->hashTable[$hashKey]->remove($k);
$this->size--;
}
return $reValue;
}
/**
*
* 修改哈希表中key 对应的值
*/
public function set($k, $v) {
$hashKey = $this->hash($k);
if (!$this->hashTable[$hashKey]->contains($k)) {
throw new Exception("不存在对应的 key");
}
$this->hashTable[$hashKey]->set($k, $v);
}
/**
* 判断哈希表中是否包含某个元素
*/
public function contains($k) {
$hashKey = $this->hash($k);
return $this->hashTable[$hashKey]->contains($k);
}
/**
* 获取哈希表中 k 对应的值
* @param $k
*/
public function get($k) {
$hashKey = $this->hash($k);
return $this->hashTable[$hashKey]->get($k);
}
}

7.完整代码

7.1 基于二分搜素搜树实现的 Map 类

<?php
require 'Map.php';
class BinarySearchTreeMap implements Map
{
public $root;
public $size;
public function __construct() {
$this->root = null;
$this->size = 0;
}
/**
* 获取映射(Map)中某个key对应的value
* @param $key
* @return |null
*/
public function get($key) {
$node = $this->recursionGet($key, $this->root);
return $node == null ? null : $node->value;
}
/**
* 递归获取 key 对应的节点
* @param $key
* @param $root
* @return |null
*/
private function recursionGet($key, $root) {
if ($root == null) {
return null;
} elseif ($key == $root->key) {
return $root;
} elseif ($key < $root->key) {
return $this->recursionGet($key, $root->left);
} else {
return $this->recursionGet($key, $root->right);
}
}
/**
* 添加 key-value 数据
* @param $key
* @param $value
*/
public function add($key, $value): void {
$this->root = $this->recursionAdd($key, $value, $this->root);
}
/**
* 递归添加数据
* @param $key
* @param $value
* @param $root
*/
private function recursionAdd($key, $value, $root) {
if ($root == null) {
$root = new Node($key, $value);
$this->size++;
} elseif ($key == $root->key) {
$root->value = $value;
} elseif ($key < $root->key) {
$root->left = $this->recursionAdd($key, $value, $root->left);
} else {
$root->right = $this->recursionAdd($key, $value, $root->right);
}
return $root;
}
/**
* 查看map是否包含某个key
* @param $key
* @return bool
*/
public function contains($key): bool {
$node = $this->recursionGet($key, $this->root);
return $node != null;
}
/**
* 递归查看map是否存在某个 key
* @param $key
* @param $root
* @return bool
*/
private function recursionContains($key, $root) {
if ($root == null) {
return false;
} elseif ($key == $root->key) {
return true;
} elseif ($key < $root->key) {
return $this->recursionContains($key, $root->left);
} else {
return $this->recursionContains($key, $root->right);
}
}
/**
* 修改 key 对应的 value
* @param $key
* @param $value
*/
function set($key, $value) {
$node = $this->recursionGet($key, $this->root);
if ($node == null) {
echo "不存在该节点";
exit;
}
$node->value = $value;
}
public function traverseMinHeap($minHeap, $k) {
$this->recursionTraverse($this->root, $minHeap, $k);
}
private function recursionTraverse($root, $minHeap, $k) {
if ($root != null) {
$this->recursionTraverse($root->left, $minHeap, $k);
if ($minHeap->getSize() < $k) {
$minHeap->add(['key' => $root->key, 'value' => $root->value]);
} else {
$min = $minHeap->findMin();
if ($root->value > $min['value']) {
$minHeap->replaceMin(['key' => $root->key, 'value' => $root->value]);
}
}
$this->recursionTraverse($root->right, $minHeap, $k);
}
}
/**
* 删除二分搜索树元素
* @param $e
*/
public function remove($k) {
$value = $this->get($k);
$this->root = $this->recursionRemove($this->root, $k);
return $value;
}
/**
* 递归删除二分搜索树元素
* @param $root
* @param $e
*/
private function recursionRemove($root, $k) {
if ($root != null) {
if ($k == $root->key) {
$root = $this->joinRemoveNode($root);
} elseif ($k < $root->key) {
$root->left = $this->recursionRemove($root->left, $k);
} else {
$root->right = $this->recursionRemove($root->right, $k);
}
}
return $root;
}
/**
* 拼接删除节点 返回新节点
*/
private function joinRemoveNode($root) {
if ($root->left != null && $root->right == null) {
$root = $root->left;
} elseif ($root->left == null && $root->right != null) {
$root = $root->right;
} else {
$leftMax = $this->getMaxNode($root->left);
$leftMax->right = $root->right;
$root = $root->left;
}
return $root;
}
/**
* 获取某颗树最大元素节点
* @param $root
* @return mixed
*/
private function getMaxNode($root) {
for ($node = $root; $node != null; $node = $node->right) {
if ($node->right != null) {
$root = $node->right;
} else {
$root = $node;
}
}
return $root;
}
/**
* 获取最小元素
* @return mixed
*/
public function getMin() {
return $this->getMinNode($this->root)->e;
}
/**
* 获取某颗树最小元素节点
* @param $root
* @return mixed
*/
private function getMinNode($root) {
for ($node = $root; $node != null; $node = $node->left) {
if ($node->left != null) {
$root = $node->left;
} else {
$root = $node;
}
}
return $root;
}
/**
* 获取映射 Map 中 key-value 数量
* @return int
*/
public function getSize(): int {
return $this->size;
}
}
class Node
{
public $key;
public $value;
public $left = null;
public $right = null;
public function __construct($key, $value) {
$this->key = $key;
$this->value = $value;
}
}

7.2 正整数哈希值生成类

<?php
trait HashCode
{
function hashCode($str) {
$str = (string)$str;
$hash = 0;
$len = strlen($str);
if ($len == 0 )
return $hash;
for ($i = 0; $i < $len; $i++) {
$h = $hash << 5;
$h -= $hash;
$h += ord($str[$i]);
$hash = $h;
$hash &= 0x7FFFFFFF;
}
return $hash;
}
}

7.3 演示输出

<?php
require 'HashTable.php';
$hashTable = new HashTable();
$hashTable->add("qin","shixian");
$hashTable->add("liu","bei");
$hashTable->add("wu","sangui");
$hashTable->add("sun","wukong");
$hashTable->add("zhu","bajie");
$hashTable->add("sha","seng");
echo $hashTable->get("qin");
echo "n";
echo $hashTable->get("liu");
echo "n";
echo $hashTable->get("wu");
echo "n";
echo $hashTable->get("sun");
echo "n";
echo $hashTable->get("zhu");
echo "n";
echo $hashTable->get("sha");
echo "n";