這篇文章主要介紹一下哈希表(Hash Table)的實現原理,哈希表(Hash Table) 也叫散列表,它通過把關鍵碼值(key-value)映射到表中一個位置來訪問,以加快其查找的速度。這個映射函數叫做哈希函數,存放記錄的數組叫哈希表(Hash Table)。
1.哈希表(Hash Table)的特點訪問速度很快,將指定的 Key 都映射到一個地址上,在訪問時,可以直接跳到那個地址。
空間換時間,哈希表充分體現了空間換時間的思想。
無序,哈希表是無序的。它為了能快速訪問元素,值是根據哈希函數直接找到存儲地址的。
可能會產生哈希衝突,不同的值通過哈希函數可能存在相同值的情況,這時就需要採用衝突解決方案。
2.哈希函數的原理下面舉幾個簡單的 哈希函數 實現原理,主要說明如何將不同類型的值轉化為一個小整數(小整數可以在數組中表示索引,即表示地址):
2.1 大整數轉化為小整數(數組索引)一個最簡單的辦法是 模(mod) 一個 素數:
Tips:從圖中可以看出,不同的數對一個 素數 模值區分度比較高,分布更加均勻。
下面是有人研究好的一個列表,其中 lwr 表示你取值範圍的下界,upr 表示你取值範圍的上界,prime 表示該範圍的值對該值求模區分度最好:
可以先將浮點型擴大倍數轉化為整型,然後按照大整數的方式處理即可。
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
Tips:其中 B 表示進位,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;
}
}
Tips:這裡簡單封裝成 trait HashCode 方便其他類調用,其中 $hash &= 0x7FFFFFFF 的意思是將輸出值最高位符號位保證為0,表示正數輸出。
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;
}
}
Tips:上述哈希函數 hashCode 只是演示哈希原理過程,具體實現需要結合數學計算,這裡不做討論。
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);
輸出如下:
Tips:上述代碼中 $arr 中存儲哈希值的時候沒有處理哈希值衝突的情況。
5.哈希表(Hash Table)原理圖和解決衝突示示意圖Tips:如果哈希衝突比較多的情況下,可以使用紅黑樹來代替拉鍊表解決哈希衝突。
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);
}
}
<?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;
}
}
<?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;
}
}
<?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";
代碼倉庫 :https://gitee.com/love-for-poetry/data-structure
掃碼關注愛因詩賢