PHP의 해시 테이블에 대한 자세한 설명

PHP 커널에서 매우 중요한 데이터 구조 중 하나가 HashTable입니다. 우리가 일반적으로 사용하는 배열은 HashTable을 사용하여 커널에서 구현됩니다. 그렇다면 PHP의 HashTable은 어떻게 구현되는 걸까요? 최근에 HashTable의 데이터 구조를 읽었는데, 최근에 우연히 PHP 소스코드를 보다가 구체적인 구현 알고리즘이 나와있지 않아서, 참고해서 구현해봤습니다. PHP HashTable의 구현 HashTable의 간단한 버전은 몇 가지 경험을 요약하고 아래에서 공유됩니다.

저자는 github에 HashTable 구현의 간단한 버전을 가지고 있습니다: HashTable 구현

또한 PHP의 더 자세한 버전이 있습니다. github 주석의 소스 코드. 관심있으신 분들은 한번 보시고 별점 부탁드립니다. PHP5.4 소스 코드 주석. 커밋 기록을 통해 추가된 주석을 확인할 수 있습니다.

해시 테이블 소개

해시 테이블은 사전 연산을 구현하는 효과적인 데이터 구조입니다.

정의

간단히 말하면 HashTable(해시 테이블)은 키-값 쌍의 데이터 구조입니다. 삽입, 검색, 삭제 등의 작업을 지원합니다. 합리적인 가정 하에서 해시 테이블의 모든 작업의 ​​시간 복잡도는 O(1)입니다(관련 증명에 관심이 있는 사람은 직접 확인할 수 있습니다).

해시 테이블 구현의 핵심

해시 테이블에서는 키워드를 첨자로 사용하는 대신 해시 함수를 사용하여 해시를 계산합니다. 키 값을 아래 첨자로 입력한 다음 검색/삭제 시 키의 해시 값을 계산하여 요소가 저장된 위치를 빠르게 찾을 수 있습니다.

해시 테이블에서는 서로 다른 키가 동일한 해시 값을 계산할 수 있습니다. 이를 "해시 충돌"이라고 하며, 이는 두 개 이상의 해시 값을 처리합니다. 동일합니다. 공개 주소 지정, 지퍼링 등 해시 충돌을 해결하는 방법에는 여러 가지가 있습니다.

따라서 좋은 해시 테이블을 구현하는 핵심은 좋은 해시 함수와 해시 충돌을 처리하는 방법입니다.

해시 함수

해시 알고리즘의 품질을 판단하는 네 가지 정의는 다음과 같습니다. > * 일관성, 동등 키 동일한 해시를 생성해야 합니다. 값 > * 효율적이고 계산하기 쉬움 > 균일성, 모든 키를 균등하게 해시합니다.

해시 함수는 키 값과 해시 값 간의 대응 관계, 즉 h = hash_func(key)를 설정합니다. 해당 관계는 아래 그림과 같습니다.

완벽한 해시 함수 설계는 전문가에게 맡기겠습니다. . 기존의 보다 성숙한 해시 함수를 사용하세요. PHP 커널에서 사용하는 해시 함수는 DJBX33A라고도 하는 time33 함수입니다.

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개 루프 + 스위치로 구현되며 for 루프를 최적화하여 루프 실행 횟수를 줄인 다음 스위치에서 통과하지 못한 나머지 요소를 실행합니다.

Zipper 방식

같은 해시값을 갖는 모든 요소를 ​​연결리스트에 저장하는 방식을 지퍼 방식이라고 합니다. 검색 시에는 먼저 키에 해당하는 해시값을 계산한 후, 해시값을 기준으로 해당 연결리스트를 찾고, 최종적으로 연결리스트를 따라 순차적으로 해당값을 검색한다. 구체적인 저장된 구조도는 다음과 같습니다.

PHP의 HashTable 구조

해시 테이블의 데이터 구조를 간략하게 소개한 후, 계속해서 해시 테이블이 PHP에서 어떻게 구현되는지 살펴보세요.

(사진은 인터넷에서 가져온 것이며 침해 내용은 삭제됩니다)

PHP 커널 해시 테이블 정의:

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;

HashTable의 크기인 nTableSize는 2의 배수로 증가합니다.

nTableMask는 해시 값과 AND 연산을 수행하여 인덱스 값을 얻는 데 사용됩니다. arBuckets가 초기화된 후의 해시 값은 항상 HashTable이 현재 소유하고 있는 요소 수인 nTableSize-1

nNumOfElements입니다. count 함수는 이 값을 직접 반환합니다.

nNextFreeElement, 이는 숫자 키를 나타냅니다. 값 배열에서 다음 숫자 인덱스의 위치

pInternalPointer, 현재 멤버를 가리키는 내부 포인터, 다음 작업에 사용됩니다. HashTable을 가리키는

pListHead 요소를 탐색합니다. 의 첫 번째 요소는 배열의 첫 번째 요소이기도 합니다.

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记录查看已添加的注解。

위 내용은 PHP의 해시 테이블에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!