PHP 數(shù)組

tracy 發(fā)布于2019-07-01 10:50 / 3116人閱讀

摘要：以下為數(shù)組的基礎(chǔ)結(jié)構(gòu)，插入，查找和過(guò)程。再存放其，如果根據(jù)其下標(biāo)計(jì)算取模得到的中已經(jīng)有值，那么說(shuō)明出現(xiàn)了哈希碰撞，這個(gè)時(shí)候把當(dāng)前中的值取出來(lái)保存到當(dāng)前，把保存的索引保存在當(dāng)前，以此類推。

以下為 PHP 數(shù)組的基礎(chǔ)結(jié)構(gòu)，插入，查找和 rehash 過(guò)程。

基礎(chǔ)結(jié)構(gòu)：

struct _zend_array {
    zend_refcounted_h gc;
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(
                zend_uchar ?  flags,
                zend_uchar ?  nApplyCount,
                zend_uchar ?  nIteratorsCount,
                zend_uchar ?  consistency)
        } v;
        uint32_t flags;
    } u;
    uint32_t ? ? ? ?  nTableMask; // 哈希值計(jì)算掩碼，等于nTableSize的負(fù)值(nTableMask = -nTableSize)
    Bucket ? ? ? ? ?  *arData; ?   // 存儲(chǔ)元素?cái)?shù)組，指向第一個(gè)Bucket
    uint32_t ? ? ? ?  nNumUsed;   // 已用Bucket數(shù)
    uint32_t ? ? ? ?  nNumOfElements; // 哈希表有效元素?cái)?shù) = nNumUsed - num(is_undef)
    uint32_t ? ? ? ?  nTableSize;   // 哈希表總大小，為2的n次方, 最小為8
    uint32_t ? ? ? ?  nInternalPointer;  // 懷疑是內(nèi)部指針
    zend_long ? ? ? ? nNextFreeElement; // 下一個(gè)可用的數(shù)值索引 arr[] = 1;arr["a"] = 2;arr[] = 3;  則nNextFreeElement = 2;
    dtor_func_t ? ? ? pDestructor;
};

typedef struct _Bucket {
    zval ? ? ? ? ? ?  val; ?// 存儲(chǔ)的具體value
    zend_ulong ? ? ?  h; ? ?// hash value (or numeric index) ?
    zend_string ? ?  *key; ?// string key or NULL for numerics
} Bucket;

說(shuō)明:

數(shù)組存放的時(shí)候先按照順序保存 value，再保存 value 的位置。

存放記錄的數(shù)組稱做散列表，這個(gè)數(shù)組用來(lái)存儲(chǔ) value，而 value 按順序保存，其存儲(chǔ)位置會(huì)保存在由 key 計(jì)算 hash 取模 nTableMask 得到的 idx 中。

數(shù)組初始化的時(shí)候最小大小為 8，以此為16，32，64。。。

數(shù)組初始化的時(shí)候邊做的 idx 區(qū)會(huì)全部初始化為 -1，rehash 的時(shí)候也會(huì)初始化為 -1。

數(shù)組中刪除一個(gè)元素的時(shí)候，是把該刪除的元素的 type 標(biāo)記為 is_undef, 并且 nNumOfEmelment - 1，如果該元素為最后一個(gè)元素，那么 nNumUsed - 1。

插入：

以 $arr = ["a"=>1, "b"=>2] 為例：

首先把 1 放到數(shù)組中，其 val.u2.next = -1，根據(jù)其下標(biāo) a 計(jì)算 hash, 然后 hash 取模 nTableMask 得到一個(gè) idx, 在該 idx 的位置保存前邊保存 1 的索引 nindex。

再存放 2, 其 val.u2.next = -1，如果根據(jù)其下標(biāo) b 計(jì)算hash 取模 nTableMask 得到的 idx 中已經(jīng)有值，那么說(shuō)明出現(xiàn)了哈希碰撞，這個(gè)時(shí)候把當(dāng)前 idx 中的值取出來(lái)保存到當(dāng)前 val.u2.next，把保存 2 的索引 nindex 保存在當(dāng)前 idx，以此類推。

查找：

根據(jù)下標(biāo) a 計(jì)算 hash 取模 nTableMask 得到一個(gè) idx ，拿到該 idx 中的值 nindex 去 arData 中查找，如果找到的位置中的 key != a, 那么找不到；如果找到的位置中的 key == a，那么檢查其 u2.next, 如果為 -1，那么找到了；如果不為-1，說(shuō)明插入的過(guò)程中出現(xiàn)了哈希沖突，那么根據(jù) u2.next 繼續(xù)在 arData 中查找，直到找到為止。

rehash：

rehash 的時(shí)候，首先把 nindex 區(qū)的所有記錄全部重置為 -1，然后從第一個(gè)元素開(kāi)始挪動(dòng)指針 *p，如果元素沒(méi)有被標(biāo)記為 is_undef，那么重新計(jì)算該元素的 key hash 并放到 nindex，然后循環(huán), p++。如果元素被標(biāo)記為 is_undef，那么繼續(xù)挪動(dòng)指針 p++，并設(shè)置一個(gè)新的指針 j 指向該位置，繼續(xù)循環(huán)，把后邊不為 is_undef 的元素一個(gè)一個(gè)挪到前邊來(lái)，p 每次移動(dòng)，j 遇到 is_undef 就不移動(dòng)，直到被賦值。一直挪動(dòng)到最后的 nNunUsed ，那么把 j 賦值給 nNunUsed，之后再插入元素的時(shí)候就從這個(gè)位置開(kāi)始插入，以前的元素直接被覆蓋就是了。