PHP 해시 테이블 원리

소개

해시 테이블은 거의 모든 C 프로그램에서 사용됩니다. C 언어에서는 배열의 키 이름으로 정수만 사용할 수 있으므로 PHP는 해시 알고리즘을 통해 strings의 키 이름을 제한된 크기의 배열로 매핑하는 해시 테이블을 설계했습니다. 이로 인해 필연적으로 충돌이 발생하며 PHP는 이 문제를 해결하기 위해 연결 목록을 사용합니다.

해시 테이블을 구현하는 방법에는 여러 가지가 있지만 어느 것도 완벽하지는 않습니다. 각 디자인은 특정 초점에 초점을 맞추고 일부는 CPU 사용량을 줄이고 일부는 메모리를 보다 합리적으로 사용하며 일부는 스레드 수준 확장을 지원할 수 있습니다.

해시 테이블 구현 방식에 다양성이 있는 이유는 각 구현 방식이 그 자체의 초점을 향상시킬 뿐 모든 것을 다룰 수는 없기 때문입니다.

데이터 구조

소개를 시작하기 전에 다음 사항을 미리 선언해야 합니다.

해시 테이블의 키 이름은 문자열이거나 정수일 수 있습니다. 문자열인 경우 유형을 zend_string으로 선언하고, 정수인 경우 유형을 zend_ulong으로 선언합니다.

해시 테이블의 순서는 테이블의 요소 삽입 순서를 따릅니다.

해시 테이블의 용량은 자동으로 확장 및 축소됩니다.

내부적으로 해시 테이블의 용량은 항상 2의 배수입니다.

해시 테이블의 각 요소는 zval 유형의 데이터여야 합니다.

다음은 HashTable의 구조입니다.

PHP

struct _zend_array {  
    zend_refcounted_h gc;
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(
                zend_uchar    flags,
                zend_uchar    nApplyCount,
                zend_uchar    nIteratorsCount,
                zend_uchar    reserve)
        } v;
        uint32_t flags;
    } u;
    uint32_t          nTableMask;
    Bucket           *arData;
    uint32_t          nNumUsed;
    uint32_t          nNumOfElements;
    uint32_t          nTableSize;
    uint32_t          nInternalPointer;
    zend_long         nNextFreeElement;
    dtor_func_t       pDestructor;
};

이 구조는 56바이트를 차지합니다.

가장 중요한 필드는 Bucket 유형 데이터에 대한 포인터인 arData입니다. Bucket 구조는 다음과 같이 정의됩니다.

typedef struct _Bucket {  
    zval              val;
    zend_ulong        h;                /* hash value (or numeric index)   */
    zend_string      *key;              /* string key or NULL for numerics */
} Bucket;

Bucket은 더 이상 zval 유형 데이터에 대한 포인터를 사용하지 않고 데이터 자체를 직접 사용합니다. PHP7에서는 zval이 더 이상 힙 할당을 사용하지 않기 때문에 힙 할당이 필요한 데이터는 zval 구조에 포인터로 저장되기 때문입니다. (예: PHP 문자열).

다음은 메모리에 저장되는 arData의 구조입니다.

모든 Bucket이 순서대로 저장되어 있음을 알 수 있습니다.

요소 삽입

PHP는 배열의 요소가 삽입 순서대로 저장되도록 합니다. 이런 식으로 foreach를 사용하여 배열을 반복할 때 삽입된 순서대로 순회할 수 있습니다. 다음과 같은 배열이 있다고 가정해 보겠습니다.

$a = [9 => "foo", 2 => 42, []];
var_dump($a);
 
array(3) {  
    [9]=>
    string(3) "foo"
    [2]=>
    int(42)
    [10]=>
    array(0) {
    }
}

모든 데이터는 메모리에서 인접해 있습니다.

이렇게 하면 해시 테이블의 반복자를 처리하는 논리가 매우 간단해집니다. arData 배열을 직접 탐색하면 됩니다. 메모리에서 인접한 데이터를 탐색하면 CPU 캐시를 크게 활용하게 됩니다. CPU 캐시는 전체 arData 를 읽을 수 있으므로 각 요소에 대한 액세스는 마이크로초 수준에서 이루어집니다.

size_t i;  
Bucket p;  
zval val;
 
for (i=0; i < ht->nTableSize; i++) {  
    p   = ht->arData[i];
    val = p.val;
    /* do something with val */
}

보시다시피 데이터는 arData에 순차적으로 저장됩니다. 이러한 구조를 구현하려면 다음 사용 가능한 노드의 위치를 ​​알아야 합니다. 이 위치는 배열 구조의 nNumUsed 필드에 저장됩니다.

새 데이터가 추가될 때마다 저장 후 ht->nNumUsed++가 실행됩니다. nNumUsed 값이 해시 테이블에 있는 모든 요소의 최대값(nNumOfElements)에 도달하면 "압축 또는 확장" 알고리즘이 트리거됩니다.

다음은 해시 테이블에 요소를 삽입하는 간단한 구현 예입니다.

idx = ht->nNumUsed++; /* take the next avalaible slot number */  
ht->nNumOfElements++; /* increment number of elements */  
/* ... */
p = ht->arData + idx; /* Get the bucket in that slot from arData */  
p->key = key; /* Affect it the key we want to insert at */  
/* ... */
p->h = h = ZSTR_H(key); /* save the hash of the current key into the bucket */  
ZVAL_COPY_VALUE(&p->val, pData); /* Copy the value into the bucket's value : add operation */

삽입하면 arData 배열의 맨 마지막에만 삽입되고 삭제된 노드는 삽입되는 것을 볼 수 있습니다. 채워지지 않습니다.

요소 삭제

해시 테이블의 요소가 삭제되면 해시 테이블은 실제 저장된 데이터 공간을 자동으로 확장하거나 축소하지 않습니다. 대신 UNDEF 값을 가진 zval이 설정되어 현재 노드가 삭제되었음을 나타냅니다. 삭제되었습니다.

아래 그림과 같이

따라서 배열 요소를 반복할 때 빈 노드를 특별히 판단해야 합니다.

size_t i;  
Bucket p;  
zval val;
 
for (i=0; i < ht->nTableSize; i++) {  
    p   = ht->arData[i];
    val = p.val;
    if (Z_TYPE(val) == IS_UNDEF) { /* empty hole ? */
        continue; /* skip it */
    }
    /* do something with val */
}

아주 큰 해시 테이블이라도 각 노드를 반복하고 삭제된 노드는 건너뜁니다. 노드는 arData의 노드가 항상 메모리에 서로 인접하여 저장된다는 사실 덕분에 매우 빠릅니다.

해시 위치 요소

문자열의 키 이름을 얻을 때 해시 알고리즘을 사용하여 해시된 값을 계산해야 하며, 해시 값 인덱스를 통해 arData에서 해당 요소를 찾을 수 있습니다.

요소가 삽입 순서대로 저장된다는 보장이 없기 때문에 해시된 값을 arData 배열의 인덱스로 직접 사용할 수 없습니다.

예: foo의 해시 결과가 5이고 bar의 해시 결과가 3이라고 가정할 때 삽입한 키 이름이 foo이고 그 다음이 bar인 경우. foo를 arData[5]에 저장하고 bar를 arData[3]에 저장한다면 이는 bar 요소가 foo 요소 앞에 있어야 함을 의미하며 이는 삽입한 순서와 정반대입니다.

所以，当我们通过算法哈希了键名后，我们需要一张 转换表，转换表保存了哈希后的结果与实际存储的节点的映射关系。

这里在设计的时候取了个巧：将转换表存储以 arData 起始指针为起点做镜面映射存储。这样，我们不需要额外的空间存储，在分配 arData 空间的同时也分配了转换表。

以下是有8个元素的哈希表 + 转换表的数据结构：

现在，当我们要访问 foo 所指的元素时，通过哈希算法得到值后按照哈希表分配的元素大小做取模，就能得到我们在转换表中存储的节点索引值。

如我们所见，转换表中的节点的索引与数组数据元素的节点索引是相反数的关系，nTableMask 等于哈希表大小的负数值，通过取模我们就能得到0到-7之间的数，从而定位到我们所需元素所在的索引值。综上，我们为 arData 分配存储空间时，需要使用 tablesize * sizeof(bucket) + tablesize * sizeof(uint32) 的计算方式计算存储空间大小。

在源码里也清晰的划分了两个区域：

#define HT_HASH_SIZE(nTableMask) (((size_t)(uint32_t)-(int32_t)(nTableMask)) * sizeof(uint32_t))
#define HT_DATA_SIZE(nTableSize) ((size_t)(nTableSize) * sizeof(Bucket))
#define HT_SIZE_EX(nTableSize, nTableMask) (HT_DATA_SIZE((nTableSize)) + HT_HASH_SIZE((nTableMask)))
#define HT_SIZE(ht) HT_SIZE_EX((ht)->nTableSize, (ht)->nTableMask)
 
Bucket *arData;  
arData = emalloc(HT_SIZE(ht)); /* now alloc this */

我们将宏替换的结果展开：

(((size_t)(((ht)->nTableSize)) * sizeof(Bucket)) + (((size_t)(uint32_t)-(int32_t)(((ht)->nTableMask))) * sizeof(uint32_t)))

碰撞冲突

接下来我们看看如何解决哈希表的碰撞冲突问题。哈希表的键名可能会被哈希到同一个节点。所以，当我们访问到转换后的节点，我们需要对比键名是否我们查找的。如果不是，我们将通过 zval.u2.next 字段读取链表上的下一个数据。

注意这里的链表结构并没像传统链表一样在在内存中分散存储。我们直接读取 arData 整个数组，而不是通过堆（heap）获取内存地址分散的指针。

这是 PHP7 性能提升的一个重要点。数据局部性让 CPU 不必经常访问缓慢的主存储，而是直接从 CPU 的 L1 缓存中读取到所有的数据。

所以，我们看到向哈希表添加一个元素是这样操作的：

    idx = ht->nNumUsed++;
    ht->nNumOfElements++;
    if (ht->nInternalPointer == HT_INVALID_IDX) {
        ht->nInternalPointer = idx;
    }
    zend_hash_iterators_update(ht, HT_INVALID_IDX, idx);
    p = ht->arData + idx;
    p->key = key;
    if (!ZSTR_IS_INTERNED(key)) {
        zend_string_addref(key);
        ht->u.flags &= ~HASH_FLAG_STATIC_KEYS;
        zend_string_hash_val(key);
    }
    p->h = h = ZSTR_H(key);
    ZVAL_COPY_VALUE(&p->val, pData);
    nIndex = h | ht->nTableMask;
    Z_NEXT(p->val) = HT_HASH(ht, nIndex);
    HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);

同样的规则也适用于删除元素：

#define HT_HASH_TO_BUCKET_EX(data, idx) ((data) + (idx))
#define HT_HASH_TO_BUCKET(ht, idx) HT_HASH_TO_BUCKET_EX((ht)->arData, idx)
 
h = zend_string_hash_val(key); /* get the hash from the key (assuming string key here) */  
nIndex = h | ht->nTableMask; /* get the translation table index */
 
idx = HT_HASH(ht, nIndex); /* Get the slot corresponding to that translation index */  
while (idx != HT_INVALID_IDX) { /* If there is a corresponding slot */  
    p = HT_HASH_TO_BUCKET(ht, idx); /* Get the bucket from that slot */
    if ((p->key == key) || /* Is it the right bucket ? same key pointer ? */
        (p->h == h && /* ... or same hash */
         p->key && /* and a key (string key based) */
         ZSTR_LEN(p->key) == ZSTR_LEN(key) && /* and same key length */
         memcmp(ZSTR_VAL(p->key), ZSTR_VAL(key), ZSTR_LEN(key)) == 0)) { /* and same key content ? */
        _zend_hash_del_el_ex(ht, idx, p, prev); /* that's us ! delete us */
        return SUCCESS;
    }
    prev = p;
    idx = Z_NEXT(p->val); /* get the next corresponding slot from current one */
}
return FAILURE;

转换表和哈希表的初始化

HT_INVALID_IDX 作为一个特殊的标记，在转换表中表示：对应的数据节点没有有效的数据，直接跳过。

哈希表之所以能极大地减少那些创建时就是空值的数组的开销，得益于他的两步的初始化过程。当新的哈希表被创建时，我们只创建两个转换表节点，并且都赋予 HT_INVALID_IDX 标记。

#define HT_MIN_MASK ((uint32_t) -2)
#define HT_HASH_SIZE(nTableMask) (((size_t)(uint32_t)-(int32_t)(nTableMask)) * sizeof(uint32_t))
#define HT_SET_DATA_ADDR(ht, ptr) do { (ht)->arData = (Bucket*)(((char*)(ptr)) + HT_HASH_SIZE((ht)->nTableMask)); } while (0)
 
static const uint32_t uninitialized_bucket[-HT_MIN_MASK] = {HT_INVALID_IDX, HT_INVALID_IDX};
 
/* hash lazy init */
ZEND_API void ZEND_FASTCALL _zend_hash_init(HashTable *ht, uint32_t nSize, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)  
{
    /* ... */
    ht->nTableSize = zend_hash_check_size(nSize);
    ht->nTableMask = HT_MIN_MASK;
    HT_SET_DATA_ADDR(ht, &uninitialized_bucket);
    ht->nNumUsed = 0;
    ht->nNumOfElements = 0;
}

注意到这里不需要使用堆分配内存，而是使用静态的内存区域，这样更轻量。

然后，当第一个元素插入时，我们会完整的初始化哈希表，这时我们才创建所需的转换表的空间（如果不确定数组大小，则默认是8个元素）。这时，我们将使用堆分配内存。

#define HT_HASH_EX(data, idx) ((uint32_t*)(data))[(int32_t)(idx)]
#define HT_HASH(ht, idx) HT_HASH_EX((ht)->arData, idx)
 
(ht)->nTableMask = -(ht)->nTableSize;
HT_SET_DATA_ADDR(ht, pemalloc(HT_SIZE(ht), (ht)->u.flags & HASH_FLAG_PERSISTENT));  
memset(&HT_HASH(ht, (ht)->nTableMask), HT_INVALID_IDX, HT_HASH_SIZE((ht)->nTableMask))

HT_HASH 宏能够使用负数偏移量访问转换表中的节点。哈希表的掩码总是负数，因为转换表的节点的索引值是 arData 数组的相反数。这才是C语言的编程之美：你可以创建无数的节点，并且不需要关心内存访问的性能问题。

以下是一个延迟初始化的哈希表结构：

哈希表的碎片化、重组和压缩

当哈希表填充满并且还需要插入元素时，哈希表必须重新计算自身的大小。哈希表的大小总是成倍增长。当对哈希表扩容时，我们会预分配 arBucket 类型的C数组，并且向空的节点中存入值为 UNDEF 的 zval。在节点插入数据之前，这里会浪费 (new_size – old_size) * sizeof(Bucket) 字节的空间。

如果一个有1024个节点的哈希表，再添加元素时，哈希表将会扩容到2048个节点，其中1023个节点都是空节点，这将消耗 1023 * 32 bytes = 32KB 的空间。这是 PHP 哈希表实现方式的缺陷，因为没有完美的解决方案。

编程就是一个不断设计妥协式的解决方案的过程。在底层编程中，就是对 CPU 还是内存的一次取舍。

哈希表可能全是 UNDEF 的节点。当我们插入许多元素后，又删除了它们，哈希表就会碎片化。因为我们永远不会向 arData 中间节点插入数据，这样我们就可能会看到很多 UNDEF 节点。

举个例子来说：

重组 arData 可以整合碎片化的数组元素。当哈希表需要被重组时，首先它会自我压缩。当它压缩之后，会计算是否需要扩容，如果需要的话，同样是成倍扩容。如果不需要，数据会被重新分配到已有的节点中。这个算法不会在每次元素被删除时运行，因为需要消耗大量的 CPU 计算。

以下是压缩后的数组：

压缩算法会遍历所有 arData 里的元素并且替换原来有值的节点为 UNDEF。如下所示：

Bucket *p;  
uint32_t nIndex, i;  
HT_HASH_RESET(ht);  
i = 0;  
p = ht->arData;
 
do {  
    if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) {
        uint32_t j = i;
        Bucket *q = p;
        while (++i < ht->nNumUsed) {
            p++;
            if (EXPECTED(Z_TYPE_INFO(p->val) != IS_UNDEF)) {
                ZVAL_COPY_VALUE(&q->val, &p->val);
                q->h = p->h;
                nIndex = q->h | ht->nTableMask;
                q->key = p->key;
                Z_NEXT(q->val) = HT_HASH(ht, nIndex);
                HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(j);
                if (UNEXPECTED(ht->nInternalPointer == i)) {
                    ht->nInternalPointer = j;
                }
                q++;
                j++;
            }
        }
        ht->nNumUsed = j;
        break;
    }
    nIndex = p->h | ht->nTableMask;
    Z_NEXT(p->val) = HT_HASH(ht, nIndex);
    HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i);
    p++;
} while (++i < ht->nNumUsed);

结语

到此，PHP 哈希表的实现基础已经介绍完毕，关于哈希表还有一些进阶的内容没有翻译，因为接下来我准备继续分享 PHP 内核的其他知识点，关于哈希表感兴趣的同学可以移步到原文。

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