[譯] PHP7 數組：HashTable

http://joshuais.me/yi-php7-shu-zu-hashtable/?utm_source=tuicool&utm_medium=referral

[譯] PHP7 數組：HashTable

 November 17, 2016

簡介

幾乎每個C程序中都會使用到哈希表。鑒于C語言只允許使用整數作為數組的鍵名，PHP 設計了哈希表，將字符串的鍵名通過哈希算法映射到大小有限的數組中。這樣無法避免的會產生碰撞，PHP 使用了鏈表解決這個問題。

眾多哈希表的實現方式，無一完美。每種設計都著眼于某一個側重點，有的減少了 CPU 使用率，有的更合理地使用內存，有的則能夠支持線程級的擴展。

實現哈希表的方式之所以存在多樣性，是因為每種實現方式都只能在各自的關注點上提升，而無法面面俱到。

數據結構

開始介紹之前，我們需要事先聲明一些事情：

• 哈希表的鍵名可能是字符串或者是整數。當是字符串時，我們聲明類型為 zend_string；當是整數時，聲明為 zend_ulong。

• 哈希表的順序遵循表內元素的插入順序。

• 哈希表的容量是自動伸縮的。

• 在內部，哈希表的容量總是2的倍數。

• 哈希表中每個元素一定是 zval 類型的數據。

以下是 HashTable 的結構體：

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個字節。

其中最重要的字段是 arData，它是一個指向 Bucket 類型數據的指針，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 循環數組時，能夠按照插入的順序遍歷。假設我們有這樣的數組：

<?php$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，然后是 bar，假設 foo 哈希后的結果是5，而 bar 哈希后的結果是3。如果我們將 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 內核的其他知識點，關于哈希表感興趣的同學可以移步到原文。

原文地址

http://jpauli.github.io//2016/04/08/hashtables.html