詳解PHP中的那些哈希表
- 巴扎黑原創
- 2017-05-27 10:38:083586瀏覽
在PHP核心中，其中一個很重要的資料結構就是HashTable。我們常用的數組，在核心中就是用HashTable來實作。那麼，PHP的HashTable是怎麼實現的呢?最近在看HashTable的資料結構，但是演算法書籍裡面沒有具體的實現演算法，剛好最近也在閱讀PHP的源碼，於是參考PHP的HashTable的實現，自己實作了一個簡易版的HashTable，總結了一些心得，以下跟大家分享一下。
筆者github上有一個簡易版的HashTable的實作：HashTable實作
另外，我在github有對PHP原始碼更詳細的註解。有興趣的可以圍觀一下，給個star。 PHP5.4原始碼註解。可以透過commit記錄查看已新增的註解。
HashTable的介紹
雜湊表是實作字典運算的有效資料結構。
定義
簡單地說，HashTable(哈希表)就是一種鍵值對的資料結構。支援插入，查找，刪除等操作。在一些合理的假設下，在雜湊表中的所有操作的時間複雜度是O(1)(對相關證明感興趣的可以自行查閱)。
實作雜湊表的關鍵
在雜湊表中，不是使用關鍵字做下標，而是透過雜湊函數計算出key的雜湊值作為下標，然後在尋找/刪除時再計算出key的雜湊值，從而快速定位元素保存的位置。
在一個哈希表中，不同的關鍵字可能會計算相同的雜湊值，這叫做“哈希衝突”，就是處理兩個或多個鍵的哈希值相同的情況。解決哈希衝突的方法有很多，開放尋址法，拉鍊法等等。
因此，實作一個好的雜湊表的關鍵就是一個好的雜湊函數和處理雜湊衝突的方法。
Hash函數
判斷一個雜湊演算法的好壞有以下四個定義： > * 一致性，等價的鍵必然產生相等的雜湊值; > * 高效性，計算簡單; > * 均勻性，均勻地對所有的鍵進行哈希。
雜湊函數建立了關鍵值與雜湊值的對應關係，即：h = hash_func(key)。對應關係請看下圖：
設計一個完美的雜湊函數就交由專家去做吧，我們只管用已有的較成熟的雜湊函數就好了。 PHP核心使用的雜湊函數是time33函數，又叫DJBX33A，其實作如下：
static inline ulong zend_inline_hash_func(const char *arKey, uint nKeyLength)
{
register ulong hash = 5381;
/* variant with the hash unrolled eight times */
for (; nKeyLength >= 8; nKeyLength -= 8) {
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
}
switch (nKeyLength) {
case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 1: hash = ((hash << 5) + hash) + *arKey++; break;
case 0: break;
EMPTY_SWITCH_DEFAULT_CASE()
}
return hash;
}
：函數使用了一個8次迴圈+switch來實現，是對for迴圈的優化，減少迴圈的運行次數，然後在switch裡面執行剩下的沒有遍歷到的元素。
拉鍊法
將所有具有相同雜湊值的元素都保存在一條鍊錶中的方法叫做拉鍊法。尋找的時候透過先計算key對應的雜湊值，然後根據雜湊值找到對應的鍊錶，最後沿著鍊錶順序找出對應的值。 具體保存後的結構圖如下：
PHP的HashTable結構
簡單地介紹了哈希表的資料結構之後，繼續看看PHP中是如何實作哈希表的。
(圖片源自網絡，侵權即刪)
#PHP核心hashtable的定義：
typedef struct _hashtable {
uint nTableSize;
uint nTableMask;
uint nNumOfElements;
ulong nNextFreeElement;
Bucket *pInternalPointer;
Bucket *pListHead;
Bucket *pListTail;
Bucket **arBuckets;
dtor_func_t pDestructor;
zend_bool persistent;
unsigned char nApplyCount;
zend_bool bApplyProtection;
#if ZEND_DEBUG
int inconsistent;
#endif
} HashTable;nTableSize，HashTable的大小，以2的倍數成長
nTableMask，用在與雜湊值做與運算取得該雜湊值的索引取值，arBuckets初始化後永遠是nTableSize-1
nNumOfElements，HashTable目前擁有的元素個數，count函數直接回傳這個值
nNextFreeElement，表示數字鍵值數組中下一個數字索引的位置
pInternalPointer，內部指針，指向目前成員，用於遍歷元素
pListHead，指向HashTable的第一個元素，也是陣列的第一個元素
pListTail，指向HashTable的最后一个元素，也是数组的最后一个元素。与上面的指针结合，在遍历数组时非常方便，比如reset和endAPI
arBuckets，包含bucket组成的双向链表的数组，索引用key的哈希值和nTableMask做与运算生成
pDestructor，删除哈希表中的元素使用的析构函数
persistent，标识内存分配函数，如果是TRUE，则使用操作系统本身的内存分配函数，否则使用PHP的内存分配函数
nApplyCount，保存当前bucket被递归访问的次数，防止多次递归
bApplyProtection，标识哈希表是否要使用递归保护，默认是1，要使用
举一个哈希与mask结合的例子：
例如，”foo”真正的哈希值(使用DJBX33A哈希函数)是193491849。如果我们现在有64容量的哈希表，我们明显不能使用它作为数组的下标。取而代之的是通过应用哈希表的mask，然后只取哈希表的低位。
hash | 193491849 | 0b1011100010000111001110001001 & mask | & 63 | & 0b0000000000000000000000111111 ---------------------------------------------------------------------- = index | = 9 | = 0b0000000000000000000000001001
因此，在哈希表中，foo是保存在arBuckets中下标为9的bucket向量中。
bucket结构体的定义
typedef struct bucket {
ulong h;
uint nKeyLength;
void *pData;
void *pDataPtr;
struct bucket *pListNext;
struct bucket *pListLast;
struct bucket *pNext;
struct bucket *pLast;
const char *arKey;
} Bucket;h，哈希值(或数字键值的key
nKeyLength，key的长度
pData，指向数据的指针
pDataPtr，指针数据
pListNext，指向HashTable中的arBuckets链表中的下一个元素
pListLast，指向HashTable中的arBuckets链表中的上一个元素
pNext，指向具有相同hash值的bucket链表中的下一个元素
pLast，指向具有相同hash值的bucket链表中的上一个元素
arKey，key的名称
PHP中的HashTable是采用了向量加双向链表的实现方式，向量在arBuckets变量保存，向量包含多个bucket的指针，每个指针指向由多个bucket组成的双向链表，新元素的加入使用前插法，即新元素总是在bucket的第一个位置。由上面可以看到，PHP的哈希表实现相当复杂。这是它使用超灵活的数组类型要付出的代价。
一个PHP中的HashTable的示例图如下所示：
HashTable相关API
zend_hash_init
zend_hash_add_or_update
zend_hash_find
zend_hash_del_key_or_index
zend_hash_init
函数执行步骤
设置哈希表大小
设置结构体其他成员变量的初始值 (包括释放内存用的析构函数pDescructor)
详细代码注解点击：zend_hash_init源码
注：
1、pHashFunction在此处并没有用到，php的哈希函数使用的是内部的zend_inline_hash_func
2、zend_hash_init执行之后并没有真正地为arBuckets分配内存和计算出nTableMask的大小，真正分配内存和计算nTableMask是在插入元素时进行CHECK_INIT检查初始化时进行。
zend_hash_add_or_update
函数执行步骤
检查键的长度
检查初始化
计算哈希值和下标
遍历哈希值所在的bucket，如果找到相同的key且值需要更新，则更新数据，否则继续指向bucket的下一个元素，直到指向bucket的最后一个位置
为新加入的元素分配bucket，设置新的bucket的属性值，然后添加到哈希表中
如果哈希表空间满了，则重新调整哈希表的大小
函数执行流程图
CONNECT_TO_BUCKET_DLLIST是将新元素添加到具有相同hash值的bucket链表。
CONNECT_TO_GLOBAL_DLLIST是将新元素添加到HashTable的双向链表。
详细代码和注解请点击：zend_hash_add_or_update代码注解。
zend_hash_find
函数执行步骤
计算哈希值和下标
遍历哈希值所在的bucket，如果找到key所在的bucket，则返回值，否则，指向下一个bucket，直到指向bucket链表中的最后一个位置
详细代码和注解请点击：zend_hash_find代码注解。
zend_hash_del_key_or_index
函数执行步骤
计算key的哈希值和下标
遍历哈希值所在的bucket，如果找到key所在的bucket，则进行第三步，否则，指向下一个bucket，直到指向bucket链表中的最后一个位置
如果要删除的是第一个元素，直接将arBucket[nIndex]指向第二个元素;其余的操作是将当前指针的last的next执行当前的next
调整相关指针
释放数据内存和bucket结构体内存
详细代码和注解请点击：zend_hash_del_key_or_index代码注解。
性能分析
PHP的哈希表的优点：PHP的HashTable为数组的操作提供了很大的方便，无论是数组的创建和新增元素或删除元素等操作，哈希表都提供了很好的性能，但其不足在数据量大的时候比较明显，从时间复杂度和空间复杂度看看其不足。
不足如下：
保存数据的结构体zval需要单独分配内存，需要管理这个额外的内存，每个zval占用了16bytes的内存;
在新增bucket时，bucket也是额外分配，也需要16bytes的内存;
为了能进行顺序遍历，使用双向链表连接整个HashTable，多出了很多的指针，每个指针也要16bytes的内存;
在遍历时，如果元素位于bucket链表的尾部，也需要遍历完整个bucket链表才能找到所要查找的值
PHP的HashTable的不足主要是其双向链表多出的指针及zval和bucket需要额外分配内存，因此导致占用了很多内存空间及查找时多出了不少时间的消耗。
后续
上面提到的不足，在PHP7中都很好地解决了，PHP7对内核中的数据结构做了一个大改造，使得PHP的效率高了很多，因此，推荐PHP开发者都将开发和部署版本更新吧。看看下面这段PHP代码：
<?php
$size = pow(2, 16);
$startTime = microtime(true);
$array = array();
for ($key = 0, $maxKey = ($size - 1) * $size; $key <= $maxKey; $key += $size) {
$array[$key] = 0;
}
$endTime = microtime(true);
echo '插入 ', $size, ' 个恶意的元素需要 ', $endTime - $startTime, ' 秒', "\n";
$startTime = microtime(true);
$array = array();
for ($key = 0, $maxKey = $size - 1; $key <= $maxKey; ++$key) {
$array[$key] = 0;
}
$endTime = microtime(true);
echo '插入 ', $size, ' 个普通元素需要 ', $endTime - $startTime, ' 秒', "\n";上面这个demo是有多个hash冲突时和无冲突时的时间消耗比较。笔者在PHP5.4下运行这段代码，结果如下
插入 65536 个恶意的元素需要 43.72204709053 秒
插入 65536 个普通元素需要 0.009843111038208 秒
而在PHP7上运行的结果：
插入 65536 个恶意的元素需要 4.4028408527374 秒
插入 65536 个普通元素需要 0.0018510818481445 秒
可见不论在有冲突和无冲突的数组操作，PHP7的性能都提升了不少，当然，有冲突的性能提升更为明显。至于为什么PHP7的性能提高了这么多，值得继续深究。
最后，笔者github上有一个简易版的HashTable的实现：HashTable实现
另外，我在github有对PHP源码更详细的注解。感兴趣的可以围观一下，给个star。PHP5.4源码注解。可以通过commit记录查看已添加的注解。
以上是詳解PHP中的那些哈希表的詳細內容。更多資訊請關注PHP中文網其他相關文章！