首頁  >  文章  >  後端開發  >  php數組的基礎結構介紹

php數組的基礎結構介紹

不言
不言轉載
2018-10-17 15:51:261692瀏覽

這篇文章帶給大家的內容是關於組的基礎架構介紹,有一定的參考價值,有需要的朋友可以參考一下,希望對你有幫助。

以下為 PHP 陣列的基礎結構,插入,尋找和 rehash 過程。

基礎架構:

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; // 哈希值计算掩码,等于nTableSize的负值(nTableMask = -nTableSize)
    Bucket            *arData;     // 存储元素数组,指向第一个Bucket
    uint32_t          nNumUsed;   // 已用Bucket数
    uint32_t          nNumOfElements; // 哈希表有效元素数 = nNumUsed - num(is_undef)
    uint32_t          nTableSize;   // 哈希表总大小,为2的n次方, 最小为8
    uint32_t          nInternalPointer;  // 怀疑是内部指针
    zend_long         nNextFreeElement; // 下一个可用的数值索引 arr[] = 1;arr["a"] = 2;arr[] = 3;  则nNextFreeElement = 2;
    dtor_func_t       pDestructor;
};

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

說明:

#陣列存放的時候先依照順序儲存 value,再儲存 value 的位置。

存放記錄的數組稱做散列表,這個數組用來存儲 value,而 value 按順序保存,其存儲位置會保存在由 key 計算 hash 取模 nTableMask 得到的 idx 中。

陣列初始化的時候最小大小為 8,以此為16,32,64。 。 。

陣列初始化的時候邊做的 idx 區會全部初始化為 -1,rehash 的時候也會初始化為 -1。

數組中刪除一個元素的時候,是把該刪除的元素的 type 標記為 is_undef, 並且 nNumOfEmelment - 1,如果該元素為最後一個元素,那麼 nNumUsed - 1。

插入:

以$arr = ['a'=>1, 'b'=>2] 為例:

先把1 放到數組中,其val.u2.next = -1, 根據其下標a 計算hash, 然後hash 取模nTableMask 得到一個idx, 在該idx 的位置保存前邊保存1 的索引nindex。

再存放2, 其val.u2.next = -1, 如果根據其下標b 計算hash 取模nTableMask 得到的idx 中已經有值,那麼說明出現了哈希碰撞,這個時候把目前idx 中的值取出來儲存到目前val.u2.next,把儲存2 的索引nindex 儲存在目前idx,以此類推。

查找:

根據下標a 計算hash 取模nTableMask 得到一個idx ,拿到該idx 中的值nindex 去arData 中查找,如果找到的位置中的key != a, 那麼找不到;如果找到的位置中的key == a,那麼檢查其u2.next, 如果為-1, 那麼找到了;如果不為-1,說明插入的過程中出現了哈希衝突,那麼根據u2.next 繼續在arData 中查找,直到找到為止。

rehash:

rehash 的時候,先把nindex 區的所有記錄全部重設為-1,然後從第一個元素開始挪動指標*p,如果元素沒有被標記為is_undef,那麼重新計算該元素的key hash 並放到nindex,然後循環, p 。如果元素被標記為is_undef, 那麼繼續挪動指標p ,並設定一個新的指標j 指向該位置,繼續循環,把後邊不為is_undef 的元素一個一個挪到前邊來,p 每次移動,j 遇到is_undef就不移動,直到被賦值。一直挪動到最後的 nNunUsed ,那麼把 j 賦值給 nNunUsed,之後再插入元素的時候就從這個位置開始插入,以前的元素直接被覆蓋就是了。

#

以上是php數組的基礎結構介紹的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:segmentfault.com。如有侵權,請聯絡admin@php.cn刪除