摘要:以下為數(shù)組的基礎(chǔ)結(jié)構(gòu),插入,查找和過程。再存放其,如果根據(jù)其下標(biāo)計算取模得到的中已經(jīng)有值,那么說明出現(xiàn)了哈希碰撞,這個時候把當(dāng)前中的值取出來保存到當(dāng)前,把保存的索引保存在當(dāng)前,以此類推。
以下為 PHP 數(shù)組的基礎(chǔ)結(jié)構(gòu),插入,查找和 rehash 過程。
基礎(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; // 哈希值計算掩碼,等于nTableSize的負(fù)值(nTableMask = -nTableSize) Bucket ? ? ? ? ? *arData; ? // 存儲元素數(shù)組,指向第一個Bucket uint32_t ? ? ? ? nNumUsed; // 已用Bucket數(shù) uint32_t ? ? ? ? nNumOfElements; // 哈希表有效元素數(shù) = nNumUsed - num(is_undef) uint32_t ? ? ? ? nTableSize; // 哈希表總大小,為2的n次方, 最小為8 uint32_t ? ? ? ? nInternalPointer; // 懷疑是內(nèi)部指針 zend_long ? ? ? ? nNextFreeElement; // 下一個可用的數(shù)值索引 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;說明:
數(shù)組存放的時候先按照順序保存 value,再保存 value 的位置。
存放記錄的數(shù)組稱做散列表,這個數(shù)組用來存儲 value,而 value 按順序保存,其存儲位置會保存在由 key 計算 hash 取模 nTableMask 得到的 idx 中。
數(shù)組初始化的時候最小大小為 8,以此為16,32,64。。。
數(shù)組初始化的時候邊做的 idx 區(qū)會全部初始化為 -1,rehash 的時候也會初始化為 -1。
數(shù)組中刪除一個元素的時候,是把該刪除的元素的 type 標(biāo)記為 is_undef, 并且 nNumOfEmelment - 1,如果該元素為最后一個元素,那么 nNumUsed - 1。
插入:以 $arr = ["a"=>1, "b"=>2] 為例:
首先把 1 放到數(shù)組中,其 val.u2.next = -1, 根據(jù)其下標(biāo) a 計算 hash, 然后 hash 取模 nTableMask 得到一個 idx, 在該 idx 的位置保存前邊保存 1 的索引 nindex。
再存放 2, 其 val.u2.next = -1, 如果根據(jù)其下標(biāo) b 計算hash 取模 nTableMask 得到的 idx 中已經(jīng)有值,那么說明出現(xiàn)了哈希碰撞,這個時候把當(dāng)前 idx 中的值取出來保存到當(dāng)前 val.u2.next,把保存 2 的索引 nindex 保存在當(dāng)前 idx,以此類推。
查找:根據(jù)下標(biāo) a 計算 hash 取模 nTableMask 得到一個 idx ,拿到該 idx 中的值 nindex 去 arData 中查找,如果找到的位置中的 key != a, 那么找不到;如果找到的位置中的 key == a,那么檢查其 u2.next, 如果為 -1, 那么找到了;如果不為-1,說明插入的過程中出現(xiàn)了哈希沖突,那么根據(jù) u2.next 繼續(xù)在 arData 中查找,直到找到為止。
rehash:rehash 的時候,首先把 nindex 區(qū)的所有記錄全部重置為 -1,然后從第一個元素開始挪動指針 *p,如果元素沒有被標(biāo)記為 is_undef,那么重新計算該元素的 key hash 并放到 nindex,然后循環(huán), p++。如果元素被標(biāo)記為 is_undef, 那么繼續(xù)挪動指針 p++,并設(shè)置一個新的指針 j 指向該位置,繼續(xù)循環(huán),把后邊不為 is_undef 的元素一個一個挪到前邊來,p 每次移動,j 遇到 is_undef 就不移動,直到被賦值。一直挪動到最后的 nNunUsed ,那么把 j 賦值給 nNunUsed,之后再插入元素的時候就從這個位置開始插入,以前的元素直接被覆蓋就是了。
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/29545.html
摘要:中基礎(chǔ)中的三大坑,遍歷,引用機(jī)制,數(shù)組。今天我們在講講中的一些奇怪現(xiàn)象。本文適合有一定基礎(chǔ)的。運(yùn)行流程共用一個結(jié)構(gòu)體開始遍歷數(shù)組,進(jìn)行判斷,拷貝數(shù)組是一個新的結(jié)構(gòu)體,操作的是新的結(jié)構(gòu)體。那么遍歷數(shù)組時,全程與原數(shù)組無關(guān)。 PHP中基礎(chǔ)中的三大坑,foreach遍歷,引用機(jī)制&,數(shù)組。 今天我們在講講foreach中的一些奇怪現(xiàn)象。 在講解之前,可以先看看我其他相關(guān)的文章,屬于同一個大的...
摘要:數(shù)組原理遍歷原理揭秘數(shù)組原理遍歷原理揭秘可見,數(shù)組其實(shí)已經(jīng)改變了,但是遍歷出來的并沒有增加的哪一項(xiàng)。此時,我們也可以輸出一下當(dāng)前指針位置數(shù)組原理遍歷原理揭秘數(shù)組原理遍歷原理揭秘數(shù)組指針停留在了位置上。 php中的中的數(shù)組跟js里面數(shù)組是不大一樣的。php中數(shù)組的下標(biāo)可以整數(shù)也可以是字符串,而且數(shù)組中元素的順序不是由下標(biāo)決定的,而是由添加元素的順序。數(shù)組基礎(chǔ) $arr1 = array(...
摘要:之所以這樣說不要認(rèn)為學(xué)就不需要學(xué)語言,是因?yàn)橐晃兜闹粚W(xué)而沒有語言等這些基礎(chǔ)語言的支撐,是很難深入理解的很多東西的。 之所以這樣說不要認(rèn)為學(xué)PHP就不需要學(xué)C語言,是因?yàn)橐晃兜闹粚W(xué)PHP而沒有C語言等這些基礎(chǔ)語言的支撐,是很難深入理解PHP的很多東西的。 這樣的例子其實(shí)很多,這里我就舉這個例子吧:PHP的數(shù)組和C語言的數(shù)組的區(qū)別和聯(lián)系。 學(xué)過C語言的朋友當(dāng)然知道C語言里有數(shù)組; PHP里...
摘要:語法數(shù)組刪除數(shù)組的最后一項(xiàng)語法數(shù)組在數(shù)組的最末添加一項(xiàng)語法數(shù)組刪除數(shù)組的首項(xiàng)語法數(shù)組在數(shù)組的首部添加一項(xiàng)案例分析 1:數(shù)組的指針操作: 語法:current(數(shù)組) 當(dāng)前指針指向的單元值(默認(rèn)是第零個)語法 next(數(shù)組) 當(dāng)前指針往下移動一幀語法 prev(數(shù)組) 當(dāng)前指針往前移動一個指針語法 end(array) 將當(dāng)前指針移動到最后一項(xiàng)語法 ...
摘要:學(xué)習(xí)至今一年有余,筆記積累挺多的,也挺雜的,寫篇文章整理一下吧。基礎(chǔ)部分輸出文本的基礎(chǔ)指令和。函數(shù)內(nèi)部聲明的變量擁有作用域,只能在函數(shù)內(nèi)部進(jìn)行訪問。布爾型要指定一個布爾值,使用關(guān)鍵字或。 php學(xué)習(xí)至今一年有余,筆記積累挺多的,也挺雜的,寫篇文章整理一下吧。 php基礎(chǔ)部分 showImg(http://segmentfault.com/img/bVcWhR); PHP 輸出文本...
摘要:為了防止你錯過了之前的文章,以下是鏈接第一部分給開發(fā)者的源碼源碼結(jié)構(gòu)第二部分理解內(nèi)部函數(shù)的定義第三部分的變量實(shí)現(xiàn)所有的東西都是哈希表基本上,里面的所有東西都是哈希表。哈希后的結(jié)果可以被作為正常的數(shù)組的鍵值又名為內(nèi)存塊。表示哈希表的容量。 文章來自:http://www.hoohack.me/2016/02/15/understanding-phps-internal-array-im...
閱讀 1558·2021-11-23 09:51
閱讀 1092·2021-10-12 10:12
閱讀 2811·2021-09-22 16:06
閱讀 3636·2019-08-30 15:56
閱讀 3458·2019-08-30 15:53
閱讀 3110·2019-08-29 16:29
閱讀 2361·2019-08-29 15:27
閱讀 2017·2019-08-26 10:49