讀懂immutable-js中的Map數(shù)據(jù)結構

jone5679 發(fā)布于2019-08-23 12:23 / 570人閱讀

摘要：一向量字典樹字典樹，一種用空間換取時間的樹形數(shù)據(jù)結構，主要特點是利用字符串的公共前綴來挺升查詢性能。還有最終的數(shù)組表示的真實存儲的鍵值，存儲了，存儲了。這其中還有一種節(jié)點進行了沖突的處理。

本文受深入探究Immutable.js的實現(xiàn)機制這篇文章啟發(fā)，結合自己對Map源碼的解讀，談談我對immutable-js中map數(shù)據(jù)結構的理解，若有不正確的地方，歡迎指正。

一、Vector Trie 向量字典樹

Trie 字典樹，一種用空間換取時間的樹形數(shù)據(jù)結構，主要特點是利用字符串的公共前綴來挺升查詢性能。比如一組字符串 ["abc","ab","bd","dda"] 它的字典樹結構如下：

紅色節(jié)點代表按查找路徑下來可以組成一個單詞，這樣在查找是否存在"abc"時，每個字符逐個進行對比，時間復雜度為O(len) = 3，len為要查找的字符串的長度，而按照一般逐個對比的方式，時間復雜度為O(lenxn) = 4x3 = 12，n為字符串的個數(shù)，顯然字典樹的方式效率更高。

Vector Trie 是在 Trie 的基礎上實現(xiàn)了以向量數(shù)組的形式進行數(shù)據(jù)分組存儲，每一個被存儲的值所對應的key都映射為數(shù)組的下標。
比如這樣的數(shù)據(jù)結構 {‘000’: ‘banana’, ‘001’: ‘grape’, ‘010’: ‘lemon’, ‘011’: ‘orange’, ‘100’: ‘a(chǎn)pple’}，每個key映射為數(shù)組的索引值，這樣生成簡單的兩位數(shù)組的Vector Trie是這樣子的：

二、位分區(qū)

我們可以將key映射為數(shù)字，然后再對應到數(shù)組中，比如一個key為 8899 映射為 5 個長度（即5進制）的數(shù)字是241044, 那么他要生成深度為6的數(shù)據(jù)結構，每一層的索引就是每位的數(shù)字，這樣對每個索引都要進行數(shù)學計算，而immutable-js中使用了效率更高的位運算來生成索引，將數(shù)據(jù)進行分區(qū)。比如，8899 映射為二進制位：10001011000011，1代表此位有數(shù)據(jù)，0代表沒有數(shù)據(jù)。這樣如果每層的數(shù)組長度是7，第一層的存儲情況可以直接位運算 8899 >> 7 得到 1000101（69），第二層 8899 & 127 (Math.pow(2, 7) - 1) 得到 1000011 (67)。
位運算可以很方便得到每位是否存儲值的情況，計算速度也要比數(shù)學運算快很多。

三、Map中做了什么操作

Map中有主要的這幾種節(jié)點類型：ArrayMapNode，ValueNode，BitmapIndexedNode，HashArrayMapNode。在每次set時，節(jié)點類型會在這幾個之間轉(zhuǎn)換。還有最終的entry數(shù)組表示的真實存儲的鍵值，entry[0]存儲了key，entry[1]存儲了value。ValueNode可以看作葉子節(jié)點，存儲了entry值。
首先，如果存儲的鍵值對不大于8，那么生成entry直接存儲在ArrayMapNode數(shù)組中，ArrayMapNode作為_root節(jié)點返回，再繼續(xù)存儲值，會調(diào)用_root的update方法，也就是ArrayMapNode的update方法，如果存儲的數(shù)量大于8，會創(chuàng)建ValueNode，并調(diào)用它的update方法，在這里會進行一個mergeIntoNode操作，即如果有相同索引到此處的節(jié)點，那么要進行一次合并操作，合并后會生成BitmapIndexedNode。
BitmapIndexedNode是經(jīng)過壓縮處理的層，最多存儲16個長度的內(nèi)容，bitmap屬性就表示了這個層的存儲情況。比如值為1935909891它的存儲情況是"1110011011000111010010000000011"，最多32位，不足的話，相當于高位補0。去除0后，1的數(shù)量就是這層實際存儲的個數(shù)。為什么說它經(jīng)過壓縮呢，因為這個bitmap表示了這層的存儲情況，是長度為32的數(shù)組的每位的存儲情況，但這層實際存儲的數(shù)量最多只是它的一半，為了減少空間占用和查找效率，就沒必要記錄不存儲的位了，那就有疑問了，那直接往數(shù)組里存儲就行了，要bitmap有什么用，我們繼續(xù)往下看，再新增數(shù)據(jù)，使BitmapIndexedNode這層的數(shù)據(jù)量超過16，此時就會進行一次轉(zhuǎn)換expandNodes展開節(jié)點操作，將這層的結構轉(zhuǎn)為HashArrayMapNode，這是一個長度為32的數(shù)組，此時，bitmap記錄的位存儲情況就是把之前的數(shù)據(jù)一個一個放到32位數(shù)組里對應的地方，沒有值的地方就是undefined。
再往后如果HashArrayMapNode的存儲數(shù)量降低小于16了，又會進行packNodes轉(zhuǎn)為BitmapIndexedNode。
Map中，每次set都將對應的層的節(jié)點進行類型轉(zhuǎn)換，updateNode這個方法會將受影響的節(jié)點生成新的結構返回，不影響其它層的節(jié)點，這就實現(xiàn)了結構共享。
這其中還有一種節(jié)點HashCollisionNode進行了hash沖突的處理。

四、分析下生成的Map數(shù)據(jù)結構

在Map中為了找到數(shù)據(jù)存儲位置，使用了很多的位操作，現(xiàn)在對一組map數(shù)據(jù)進行分析，看看它是如何進行計算的。這里用到的常量，
31 和 5 在TrieUtils.js文件中:

export const SHIFT = 5; // Resulted in best performance after ______?
export const SIZE = 1 << SHIFT;
export const MASK = SIZE - 1;

我們生成500個長度的map數(shù)據(jù)結構，使它包含BitmapIndexedNode，HashArrayMapNode這幾種結構：

比如我們選取"KEY6787241"這個節(jié)點進行分析，它的hash是這樣計算出來的：

我們根據(jù)這個hash計算出它在第一層即_root下面的位置：

看到它確實放在了對應位置下的HashArrayMapNode中，那在HashArrayMapNode中12的位置是怎么算出來的呢，我們執(zhí)行這樣的操作：

然后來看看這個bitmap 524352:

可以看出它只有兩位保存了數(shù)據(jù)。為了支持不定長的寬度，位置的計算是從后往前算的，那么，存儲數(shù)據(jù)的情況就是倒數(shù)第7位，相當于index為6和倒數(shù)第20位，相當于index為19，那么我們再計算下hash：785947024和-137605744是否在對應位置：

每深入一層，將位右移動5位，并且與上31來算出對應位置。
那為啥是 31 和 5 呢，在代碼中可以看到：

就是上面對應的兩個常量。
785947024的二進制是"101110110110001001100110010000"，31的二進制是"000000000000000000000000011111"，&，位與操作后意思就是留下最后的5位，"10000" 16。再位移5位并位與31后就是，"01100" 12。2 ^ 5 = 32，所以5位二進制就能保存32個數(shù)，也就能滿足我們每一層最多32個的情況。
那32是怎么來的呢，這里統(tǒng)計了位分區(qū)的查找更新效率情況：

可以看到64位查詢速度最快，8位更新速度最快。immutable-js選擇32是因為實際使用中，查詢的頻率要比更新多，所以選擇了查詢速度較優(yōu)，更新速度不是最差的32。

云服務器 GPU云服務器 js頁面獲取map中的數(shù)據(jù) php中的map標簽 immutable-js 讀懂sql

文章版權歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/98437.html

前端進階（11） - js 數(shù)據(jù)結構類型擴展：immutable-js

摘要：數(shù)據(jù)結構類型擴展相對之類的強類型語言，有一點很大的區(qū)別就是，數(shù)據(jù)結構只有與，并且都是動態(tài)可變的，而有等數(shù)據(jù)結構。所以，為了能在中也使用這些數(shù)據(jù)結構，就應運而生。擴充了中的不可變集合，即一旦創(chuàng)建就不能改變的數(shù)據(jù)類型。 js 數(shù)據(jù)結構類型擴展：immutable-js 相對 java、.net 之類的強類型語言，js 有一點很大的區(qū)別就是，數(shù)據(jù)結構只有 array 與 object，并且都...

BLUE 2019-08-23 11:59 評論0 收藏0
筆記, immutable-js 基礎操作

摘要：這篇文章是一些操作的整理目前只有基本的操作文檔請查看使用過程中遇到的寫法我會不會增加在后邊當中不可變數(shù)據(jù)有點不適應需要借鑒一些中的內(nèi)容更新六月份到十月份我們完成了不可變數(shù)據(jù)的重構配合簡聊的巨大的單一可以整理出來一些常用的方法示例代碼用的是這篇文章是 immutable-js 一些操作的整理, 目前只有基本的操作:文檔請查看: http://facebook.github.io/imm...

alexnevsky 2019-08-21 10:33 評論0 收藏0
immer.js 簡介及源碼解析

摘要：例如維護一份在內(nèi)部，來判斷是否有變化，下面這個例子就是一個構造函數(shù)，如果將它的實例傳入對象作為第一個參數(shù)，就能夠后面的處理對象中使用其中的方法上面這個構造函數(shù)相比源代碼省略了很多判斷的部分。 showImg(https://segmentfault.com/img/bV27Dy?w=1400&h=544); 博客鏈接：下一代狀態(tài)管理工具 immer 簡介及源碼解析 JS 里面的變量類...

Profeel 2019-08-26 11:34 評論0 收藏0
immutability-helper 學習筆記 -1

摘要：張偉輸出結果這樣就實現(xiàn)了在源數(shù)據(jù)的基礎上更改了值并且輸出一個與之地址完全不同數(shù)組。本來想將有關于immutability-helper的博文放在一起學React系列博文中，但是考慮到該插件不僅僅在React中實用到，所以就單獨拿出來分兩期寫。發(fā)現(xiàn)問題 immutability意為不變，不變性，永恒性。至于該插件能做什么，我想它的作者對它的標注已經(jīng)很明確了mutate a copy ...

xbynet 2019-08-26 13:34 評論0 收藏0
React性能優(yōu)化

摘要：當大家考慮在項目中使用的時候，第一個問題往往是他們的應用的速度和響應是否能和非版一樣，每當狀態(tài)改變的時候就重新渲染組件的整個子樹，讓大家懷疑這會不會對性能造成負面影響。當大家考慮在項目中使用 React 的時候，第一個問題往往是他們的應用的速度和響應是否能和非 React 版一樣，每當狀態(tài)改變的時候就重新渲染組件的整個子樹，讓大家懷疑這會不會對性能造成負面影響。React 用了一些黑...

n7then 2019-08-21 14:15 評論0 收藏0