PHP7哈希表内部结构

Question

有非常有效的关联。 php 源代码中使用的数组 C 语言实现。

/*
 * HashTable Data Layout
 * =====================
 *
 *                 +=============================+
 *                 | HT_HASH(ht, ht->nTableMask) |
 *                 | ...                         |
 *                 | HT_HASH(ht, -1)             |
 *                 +-----------------------------+
 * ht->arData ---> | Bucket[0]                   |
 *                 | ...                         |
 *                 | Bucket[ht->nTableSize-1]    |
 *                 +=============================+
 */

结构：

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

typedef struct _zend_array HashTable;

struct _zend_array {
    zend_refcounted_h gc;
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(
                zend_uchar    flags,
                zend_uchar    _unused,
                zend_uchar    nIteratorsCount,
                zend_uchar    _unused2)
        } 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;
};

示例函数：

static zend_always_inline Bucket *zend_hash_find_bucket(const HashTable *ht, zend_string *key)
{
    zend_ulong h;
    uint32_t nIndex;
    uint32_t idx;
    Bucket *p, *arData;

    h = zend_string_hash_val(key);
    arData = ht->arData;
    nIndex = h | ht->nTableMask; //index calculation
    idx = HT_HASH_EX(arData, nIndex);
    while (EXPECTED(idx != HT_INVALID_IDX)) {
        p = HT_HASH_TO_BUCKET_EX(arData, idx);
        if (EXPECTED(p->key == key)) { /* check for the same interned string */
            return p;
        } else if (EXPECTED(p->h == h) &&
             EXPECTED(p->key) &&
             EXPECTED(ZSTR_LEN(p->key) == ZSTR_LEN(key)) &&
             EXPECTED(memcmp(ZSTR_VAL(p->key), ZSTR_VAL(key), ZSTR_LEN(key)) == 0)) {
            return p;
        }
        idx = Z_NEXT(p->val);
    }
    return NULL;
}

h 是哈希函数返回的大整数。

问题是：为什么索引要这样计算？

nIndex = h | ht->nTableMask; //index calculation

为什么哈希表大小不是简单的除法 h 整数的余数？

nIndex = h & (ht->nTableSize - 1); //analog: nIndex = h % ht->nTableSize

Answer 1

这是为了让数字变成负数。 hash的布局table真是脑残(Zend/zend_types.h):

/*
 * HashTable Data Layout
 * =====================
 *
 *                 +=============================+
 *                 | HT_HASH(ht, ht->nTableMask) |
 *                 | ...                         |
 *                 | HT_HASH(ht, -1)             |
 *                 +-----------------------------+
 * ht->arData ---> | Bucket[0]                   |
 *                 | ...                         |
 *                 | Bucket[ht->nTableSize-1]    |
 *                 +=============================+
 */

ht->nTableMask 是一个整数，被解释为 2 的补码是负数，目的是通过与此进行 ORring，并转换为 int32_t 得到 ht->arData 的负偏移量.然后将指向 Bucket 的指针类型 ht->arData 转换为指向 uint32_t 的指针，并使用负索引对该指针进行索引。 IE。所有这些可疑的诡计都不需要每个散列有 2 个指针 table，而是使用 1 个指向数据结构的中间。

使用 AND 并从 ht->arData 中减去的模数就足够了，并导致相同的操作 - 似乎这已经被手动优化以在一些糟糕的编译器上速度很快。

Answer 2

NikiC 写道: 这与 h & size -1 基本相同，但进入负数而不是正数

您没有将最高位设置为零，而是将它们设置为一所以你得到一个介于 -1 和 -size

之间的负数

掩码为 -（大小 << 1）。与 ~(size << 1) + 1 或 ~((size << 1) - 1)

相同

所以基本上和你得到普通面具的方法一样，但是 a) inverted 因为你想设置高位而不是低位 b) 移动一位以便正确处理边界

PHP7哈希表内部结构

PHP7 hashtable internal structure

php

c

php-internals