數據結構-PHP 哈希表(Hash Table)的實現

2021-02-19 愛因詩賢

這篇文章主要介紹一下哈希表(Hash Table)的實現原理,哈希表(Hash Table) 也叫散列表,它通過把關鍵碼值(key-value)映射到表中一個位置來訪問,以加快其查找的速度。這個映射函數叫做哈希函數,存放記錄的數組叫哈希表(Hash Table)

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

訪問速度很快,將指定的 Key 都映射到一個地址上,在訪問時,可以直接跳到那個地址。

空間換時間,哈希表充分體現了空間換時間的思想。

無序,哈希表是無序的。它為了能快速訪問元素,值是根據哈希函數直接找到存儲地址的。

可能會產生哈希衝突,不同的值通過哈希函數可能存在相同值的情況,這時就需要採用衝突解決方案。

2.哈希函數的原理

下面舉幾個簡單的 哈希函數 實現原理,主要說明如何將不同類型的值轉化為一個小整數(小整數可以在數組中表示索引,即表示地址):

2.1 大整數轉化為小整數(數組索引)

一個最簡單的辦法是 模(mod) 一個 素數:

Tips:從圖中可以看出,不同的數對一個 素數 模值區分度比較高,分布更加均勻。

下面是有人研究好的一個列表,其中 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

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);
}
}

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";

代碼倉庫 :https://gitee.com/love-for-poetry/data-structure

掃碼關注愛因詩賢

相關焦點

  • PHP哈希表碰撞攻擊原理
    本文結合PHP內核源碼,聊一聊這種攻擊的原理及實現。哈希表碰撞攻擊的基本原理哈希表是一種查找效率極高的數據結構,很多語言都在內部實現了哈希表。PHP中的哈希表是一種極為重要的數據結構,不但用於表示Array數據類型,還在Zend虛擬機內部用於存儲上下文環境信息(執行上下文的變量及函數均使用哈希表結構存儲)。
  • 數據結構 | 哈希表
    本文為數據結構系列第 11 篇,介紹哈希表的實現。哈希表(也叫散列表)是數據結構課程中都會介紹的概念,一般出現在「散列與查找」相關章節。哈希表的核心思想是構造一個散列函數,鍵值作為散列函數輸入,將元素映射到哈希表某一位置存儲。這樣,在進行查找時就可以根據散列函數快速找到元素所在位置。常見散列函數有:直接定址法、平方取中法、除留餘數法、數字分析法等。
  • 談談 Hash Table
    一.數據結構在我們編程的世界裡數據的基本組織可以說有三種形式。鍊表的單個節點一般為結構體或者對象,因為鍊表的單個節點除了需要保存數據之外還需要維護它的相鄰節點的關係,如果想獲得鍊表中的某個節點的值,需要從鍊表的頭結點開始遍歷,直到找到需要的東西,而插入或者刪除某個節點的話,需要找到相應的節點,修改其以及其相鄰節點的相關指針的引用即可。像其他的數據結構,比如 隊列,棧,樹,都可以通過數組或者鍊表來組織,並實現相應的操作功能。
  • 深入理解哈希表
    哈希表概述Objective-C 中的字典 NSDictionary 底層其實是一個哈希表,實際上絕大多數語言中字典都通過哈希表實現,比如我曾經分析過的 Swift 字典的實現原理。在討論哈希表之前,先規範幾個接下來會用到的概念。哈希表的本質是一個數組,數組中每一個元素稱為一個箱子(bin),箱子中存放的是鍵值對。
  • 圖解redis五種數據結構底層實現(動圖哦)
    redis有五種基本數據結構:字符串、hash、set、zset、list。但是你知道構成這五種結構的底層數據結構是怎樣的嗎? 今天我們來花費五分鐘的時間了解一下。 (目前redis版本為3.0.6)動態字符串SDSSDS是"simple dynamic string"的縮寫。
  • 淺談「Hash table」
    關注(mjw-java)——不一樣的技術分享,不一樣的學習體驗,跟威哥一起學Java,你一定可以!每天早上六點半,我們不見不散。哈希表(Hash Table)也叫散列表,是根據關鍵碼值(Key Value)而直接進行訪問的數據結構。它通過把關鍵碼值映射到哈希表中的一個位置來訪問記錄,以加快查找的速度。這個映射函數就做散列函數,存放記錄的數組叫做散列表。
  • 哈希函數和哈希表
    ,並且這種均勻與數據的輸入規律無關。比如「aa1」、"aa2"經過hash後可能結果會相差很多,當一個哈希函數的輸出在S中是均勻的,那麼我們將輸出值對m取餘(%m),就會將不定長輸入映射到0~m-1空間中,並且在這個空間也保持均勻分布!哈希表就是這麼做的,一會再說!
  • 理解 Golang 哈希表 Map 的原理
    在上一節中我們介紹了 數組和切片的實現原理,這一節會介紹 Golang 中的另一個集合元素 — 哈希,也就是 Map 的實現原理;哈希表是除了數組之外,最常見的數據結構,幾乎所有的語言都會有數組和哈希表這兩種集合元素,有的語言將數組實現成列表,有的語言將哈希表稱作結構體或者字典,但是它們其實就是兩種設計集合元素的思路,數組用於表示一個元素的序列,而哈希表示的是鍵值對之間映射關係,只是不同語言的叫法和實現稍微有些不同
  • Redis 內部數據結構詳解(1):dict
    在不要求數據有序存儲,且能保持較低的哈希值衝突概率的前提下,基於哈希表的查找性能能做到非常高效,接近O(1),而且實現簡單。在Redis中,dict也是一個基於哈希表的算法。和傳統的哈希算法類似,它採用某個哈希函數從key計算得到在哈希表中的位置,採用拉鏈法解決衝突,並在裝載因子(load factor)超過預定值時自動擴展內存,引發重哈希(rehashing)。
  • 揭秘| 帶你走進哈希表(Hash Table)的世界
    為什麼會有哈希表這種數據結構呢?讓我們用一個通俗的例子來理解:大家一定都查過字典吧,我們知道,《新華字典》是按照讀音排序的,可以理解為一個以讀音為key,按升序排列的資料庫。對於讀音已知的字,可以通過「二分查找法」,很快地查找到要找的字,其時間複雜度為O(log2n)。
  • 揭秘 | 帶你走進哈希表(Hash Table)的世界
    為什麼會有哈希表這種數據結構呢?讓我們用一個通俗的例子來理解:大家一定都查過字典吧,我們知道,《新華字典》是按照讀音排序的,可以理解為一個以讀音為key,按升序排列的資料庫。對於讀音已知的字,可以通過「二分查找法」,很快地查找到要找的字,其時間複雜度為O(log2n)。但是,對於不知道讀音的字怎麼辦呢?
  • 一看就懂的數據結構基礎「哈希表」
    哈希表哈希表(Hash table),是存儲鍵值(Key Value)對數據的一種數據結構。例如,我們可以將人的名字作為鍵,性別作為值來存儲。通過把鍵映射到表中的一個位置來訪問數據,以提高查找速度。而這個映射關係就是哈希函數。哈希函數因為哈希表的數據映射關係以哈希函數為體現,為了避免小夥伴對哈希函數不夠了解,此處先介紹哈希函數。
  • 圖解:什麼是哈希?
    由於上述限制,使用直接訪問表並不是最明智的方法。而哈希則是解決以上問題的最好數據結構,並且與上面所提到的數據結構(數組,鍊表,AVL樹)在實踐中相比,性能非常好。鏈地址法實現首先創建一個空的哈希表,哈希表的表長為
  • 哈希(Hash)和哈希樹(Merkletree)
    哈希函數(英語:Hash function)又稱散列函數,是一種從任何一種數據中創建小的數字「指紋」的方法。散列函數把消息或數據壓縮成摘要,使得數據量變小,將數據的格式固定下來。
  • 哈希表的原理,真的很難弄懂麼?
    【Java】基礎25:List、Set以及哈希表昨天學習了幾種簡單數據結構,為何要了解數據結構?一方面的原因是因為集合的底層就是與其息息相關的。ArrayList的底層數據結構:數組。LinkedList的底層數據結構:鍊表。TreeSet的底層數據結構:紅黑樹。
  • Hash(哈希)密碼破解原理
    通常我們能想到的兩種辦法,一種就是暴力破解法,把P中的每一個p都算一下H(p),直到結果等於q;另一種辦法是查表法,搞一個很大的數據 庫,把每個p和對應的q都記錄下來,按q做一下索引,到時候查一下就知道了。這兩種辦法理論上都是可以的,但是前一種可能需要海量的時間,後一種需要海量 的存儲空間,以至於以目前的人類資源無法實現。
  • 圖解MySQL | [原理解析] Adaptive Hash Index 是如何建立的
    Adaptive Hash Index(以下簡稱 AHI)估計是 MySQL 的各大特性中,大家都知道名字但最說不清原理的一個特性。
  • Redis 設計與實現 4:字典
    Redis 中,字典是基礎結構。Redis 資料庫數據、過期時間、哈希類型都是把字典作為底層結構。字典的結構哈希表哈希表的實現代碼在:dict.h/dictht ,Redis 的字典用哈希表的方式實現。
  • Redis字典的數據結構和實現方式的精華
    由於Redis使用的是C語言,沒有內置的字典,Redis自己實現了字典,具體總結如下:結構說明:(1)Redis 中每個 hash 可以存儲 232- 1 鍵(unsigned long size)(2)哈希表大小掩碼sizemark,sizemark屬性的值總是等於size-1,size是hash表大小。
  • Python | Leetcode哈希表系列
    哈希表哈希表(散列表)的思想是將關鍵字 Key 映射到存放記錄的散列表中從而進行快速訪問,其中映射函數 f(key) 稱為哈希函數(散列函數),依據哈希函數建立的查找表稱為哈希表。假如班級裡面有50個學生,都有各自的名字,我們想把學生的名字放在一個表上,同時便於很快的查找,你會毫無想到數組,但是查找的複雜度是O(n),所以哈希表就是為了解決這問題,將查找的複雜度達到 O(1)假如有個學生的名字叫做lies,通過hash函數,得到下標9 ,將lies的ASCII碼加起來