讀懂immutable-js中的Map數據結構

jone5679 發布于2019-08-23 12:23 / 522人閱讀

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

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

一、Vector Trie 向量字典樹

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

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

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

二、位分區

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

三、Map中做了什么操作

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

四、分析下生成的Map數據結構

在Map中為了找到數據存儲位置，使用了很多的位操作，現在對一組map數據進行分析，看看它是如何進行計算的。這里用到的常量，
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數據結構，使它包含BitmapIndexedNode，HashArrayMapNode這幾種結構：

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

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

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

然后來看看這個bitmap 524352:

可以看出它只有兩位保存了數據。為了支持不定長的寬度，位置的計算是從后往前算的，那么，存儲數據的情況就是倒數第7位，相當于index為6和倒數第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個數，也就能滿足我們每一層最多32個的情況。
那32是怎么來的呢，這里統計了位分區的查找更新效率情況：

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

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/98437.html

前端進階（11） - js 數據結構類型擴展：immutable-js

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

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

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

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

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

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

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

xbynet 2019-08-26 13:34 評論0 收藏0
React性能優化

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

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