Detaillierte Erklärung von Hash-Tabellen in PHP

Im PHP-Kernel ist HashTable eine der sehr wichtigen Datenstrukturen. Die von uns üblicherweise verwendeten Arrays werden mithilfe von HashTable im Kernel implementiert. Wie wird PHPs HashTable implementiert? Ich habe kürzlich die Datenstruktur von HashTable gelesen, aber in den Algorithmusbüchern, die ich kürzlich gelesen habe, gibt es keinen spezifischen Implementierungsalgorithmus, also habe ich einen implementiert, indem ich darauf verwiesen habe Die Implementierung von PHPs HashTable fasst einige Erfahrungen zusammen und wird im Folgenden mit Ihnen geteilt.

Der Autor hat eine einfache Version der HashTable-Implementierung auf Github: HashTable-Implementierung

Außerdem habe ich eine detailliertere Version von PHP Quellcode zur Github-Annotation. Wenn Sie Interesse haben, können Sie einen Blick darauf werfen und einen Stern vergeben. Anmerkungen zum PHP5.4-Quellcode. Sie können die hinzugefügten Anmerkungen über den Commit-Datensatz anzeigen.

Einführung in HashTable

Hash-Tabelle ist eine effektive Datenstruktur, die Wörterbuchoperationen implementiert.

Definition

Einfach ausgedrückt ist HashTable (Hash-Tabelle) eine Datenstruktur aus Schlüssel-Wert-Paaren. Unterstützt Vorgänge wie Einfügen, Suchen und Löschen. Unter einigen vernünftigen Annahmen beträgt die zeitliche Komplexität aller Operationen in der Hash-Tabelle O(1) (wenn Sie an dem entsprechenden Beweis interessiert sind, können Sie ihn selbst überprüfen).

Der Schlüssel zur Implementierung einer Hash-Tabelle

In einer Hash-Tabelle verwenden Sie Hash-Funktionen, um den Hash zu berechnen, anstatt Schlüsselwörter als Indizes zu verwenden Wert des Schlüssels als Index und berechnen Sie dann beim Suchen/Löschen den Hash-Wert des Schlüssels, um schnell den Speicherort des Elements zu finden.

In einer Hash-Tabelle können verschiedene Schlüssel den gleichen Hash-Wert berechnen. Dies wird als „Hash-Kollision“ bezeichnet, bei der es um den Umgang mit zwei oder mehr Schlüsseln geht sind gleich. Es gibt viele Möglichkeiten, Hash-Konflikte zu lösen, z. B. offene Adressierung, Zippering usw.

Daher ist der Schlüssel zur Implementierung einer guten Hash-Tabelle eine gute Hash-Funktion und eine Methode zum Umgang mit Hash-Konflikten.

Hash-Funktion

Es gibt vier Definitionen zur Beurteilung der Qualität eines Hash-Algorithmus: > * Konsistenz, äquivalente Schlüssel müssen gleichen Hash erzeugen Werte; > * Effizient und einfach zu berechnen; Einheitlichkeit, Hashes aller Schlüssel gleichmäßig.

Die Hash-Funktion stellt die entsprechende Beziehung zwischen dem Schlüsselwert und dem Hash-Wert her, also: h = hash_func(key). Die entsprechende Beziehung ist in der folgenden Abbildung dargestellt:

Überlassen wir es den Experten, eine perfekte Hash-Funktion zu entwerfen . Verwenden Sie einfach eine vorhandene, ausgereiftere Hash-Funktion. Die vom PHP-Kernel verwendete Hash-Funktion ist die time33-Funktion, auch DJBX33A genannt. Ihre Implementierung ist wie folgt:

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

Hinweis: Funktionsverwendung Eine 8-malige Schleife + Schalter wird implementiert, um die for-Schleife zu optimieren, die Anzahl der Schleifenläufe zu reduzieren und dann die verbleibenden Elemente auszuführen, die im Schalter nicht durchlaufen wurden.

Zipper-Methode

Die Methode zum Speichern aller Elemente mit demselben Hashwert in einer verknüpften Liste wird als Zipper-Methode bezeichnet. Berechnen Sie bei der Suche zunächst den dem Schlüssel entsprechenden Hash-Wert, suchen Sie dann anhand des Hash-Werts die entsprechende verknüpfte Liste und suchen Sie schließlich nacheinander entlang der verknüpften Liste nach dem entsprechenden Wert. Das spezifische gespeicherte Strukturdiagramm lautet wie folgt:

PHPs HashTable-Struktur

Nachdem wir kurz die Datenstruktur der Hash-Tabelle vorgestellt haben, schauen wir uns weiter an, wie die Hash-Tabelle in PHP implementiert wird.

(Bilder stammen aus dem Internet, jegliche Verstöße werden gelöscht)

Definition der PHP-Kernel-Hashtabelle:

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, die Größe der HashTable, erhöht sich um ein Vielfaches von 2

nTableMask, wird verwendet, um eine UND-Operation mit dem Hash-Wert durchzuführen, um den Index zu erhalten Wert des Hash-Werts, arBuckets Nach der Initialisierung ist es immer nTableSize-1

nNumOfElements, die Anzahl der Elemente, die derzeit der HashTable gehören. Die Zählfunktion gibt diesen Wert direkt zurück

nNextFreeElement, was die Position des nächsten numerischen Index im numerischen Schlüsselwertarray bedeutet

pInternalPointer, interner Zeiger, der auf das aktuelle Mitglied zeigt, Wird zum Durchlaufen der Elemente

pListHead verwendet. Zeigt auf das erste Element der HashTable und das erste Element des Arrays

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 &#39;插入 &#39;, $size, &#39; 个恶意的元素需要 &#39;, $endTime - $startTime, &#39; 秒&#39;, "\n";

$startTime = microtime(true);
$array = array();
for ($key = 0, $maxKey = $size - 1; $key <= $maxKey; ++$key) {
    $array[$key] = 0;
}
$endTime = microtime(true);
echo &#39;插入 &#39;, $size, &#39; 个普通元素需要 &#39;, $endTime - $startTime, &#39; 秒&#39;, "\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记录查看已添加的注解。

Das obige ist der detaillierte Inhalt vonDetaillierte Erklärung von Hash-Tabellen in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!