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

这是为了使数字变为负数。哈希表的布局真是脑残(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 个指针，而是使用 1 个指向数据结构的中间。

使用 AND 进行取模并从 ht->arData 中减去就足够了，并且会产生相同的操作 - 似乎这已经经过手动优化，可以在某些糟糕的编译器上快速运行。