重建散列表

2.2.6 重建散列表

当删除元素达到一定数量或扩容后都需要重建散列表，因为value在Bucket位置移动了或哈希数组nTableSize变化了导致key与value的映射关系改变，重建过程实际就是遍历Bucket数组中的value，然后重新计算映射值更新到散列表，除了更新散列表之外，这里还有一个重要的处理：移除已删除的value，开始的时候我们说过，删除value时只是将value的type设置为IS_UNDEF，并没有实际从Bucket数组中删除，如果这些value一直存在那么将浪费很多空间，所以这里会把它们移除，操作的方式也比较简单：将后面未删除的value依次前移，具体过程如下：

//zend_hash.c
ZEND_API int ZEND_FASTCALL zend_hash_rehash(HashTable *ht)
{
    Bucket *p;
    uint32_t nIndex, i;
    ...
    i = 0;
    p = ht->arData;
    if (ht->nNumUsed == ht->nNumOfElements) { //没有已删除的直接遍历Bucket数组重新插入索引数组即可
        do {
            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);
    } else {
        do {
            if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) {
                //有已删除元素则将后面的value依次前移，压实Bucket数组
                ......
                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中关于HashTable的还有很多，这里不再介绍。