摘要:那對于結構又要如何處理,沒有結構的索引,那怎么辦呢我們把鍵名變為哈希值就可以啦。表示存在,表示不存在。例如轉換為二進制后為每位為一組,假定為取出需要的位。類對應帶的,代表其子元素的數量。
上一片文章介紹的是 List 結構。那對于 Map 結構又要如何處理,沒有 List 結構的索引,那怎么辦呢? 我們把鍵名變為哈希值就可以啦~
HAMT:Hash Arrey Mapped Trie 。這個結構就是Map中所用到的。
immutable中的hash計算核心代碼如下:
function hashString(string) { // This is the hash from JVM // The hash code for a string is computed as // s[0] * 31 ^ (n - 1) + s[1] * 31 ^ (n - 2) + ... + s[n - 1], // where s[i] is the ith character of the string and n is the length of // the string. We "mod" the result to make it between 0 (inclusive) and 2^31 // (exclusive) by dropping high bits. let hashed = 0; for (let ii = 0; ii < string.length; ii++) { hashed = (31 * hashed + string.charCodeAt(ii)) | 0; } return smi(hashed); }
// v8 has an optimization for storing 31-bit signed numbers. // Values which have either 00 or 11 as the high order bits qualify. // This function drops the highest order bit in a signed number, maintaining // the sign bit. export function smi(i32) { return ((i32 >>> 1) & 0x40000000) | (i32 & 0xbfffffff); }
上面只是一個計算hash值的函數,討論的重點再下面呢。
一、Map 的結構先看看Map的結構:
function makeMap(size, root, ownerID, hash) { const map = Object.create(MapPrototype); map.size = size; map._root = root; map.__ownerID = ownerID; map.__hash = hash; map.__altered = false; return map; }
和list不同,Map中沒有_tail,所有的數據都在_root里面。
再Map里,我們要分幾種情況:
1、當鍵值對不超過8個
2、當鍵值對超過8個小于16個
3、當鍵值對超過16個
4、hash沖突怎么辦
用下面這段代碼調試看看每種情況的結構:
let jsObj = {}; for (let i = 0; i < 8; i++) { jsObj[Math.random()] = Math.random(); } let map1 = Immutable.Map(jsObj); console.log(map1);二、ArrayMapNode
當鍵值對不超過8個的時候采用的是這個結構。
這種方式是最簡單的,所有鍵值對保存在 entries 里面。同時 get/set 方法都較為簡單,直接遍歷一下獲取就好了。
從圖中我們可以看到,immutable把key和value轉換為一個數組的arr[0]和arr[1]來存儲。
ArrayMapNode.prototype.update:
update(ownerID, shift, keyHash, key, value, didChangeSize, didAlter) { ..... const entries = this.entries; let idx = 0; const len = entries.length; for (; idx < len; idx++) { // 尋找需要更新的值 if (is(key, entries[idx][0])) { break; } } const exists = idx < len;//是否存在這個key ...... // 判斷個數是否大于8 MAX_ARRAY_MAP_SIZE的值為8 if (!exists && !removed && entries.length >= MAX_ARRAY_MAP_SIZE) { return createNodes(ownerID, entries, key, value); } ...... const newEntries = isEditable ? entries : arrCopy(entries); if (exists) { if (removed) { idx === len - 1 ? newEntries.pop() : (newEntries[idx] = newEntries.pop()); } else { newEntries[idx] = [key, value];//存在就直接把值賦值給idx的位置 } } else { newEntries.push([key, value]);//不存在 就是新增 push一個值進去 } ...... return new ArrayMapNode(ownerID, newEntries); } }
上面代碼中MAX_ARRAY_MAP_SIZE的定義:
const MAX_ARRAY_MAP_SIZE = SIZE / 4; const MAX_BITMAP_INDEXED_SIZE = SIZE / 2; const MIN_HASH_ARRAY_MAP_SIZE = SIZE / 4;
export const SIZE = 1 << SHIFT;三、BitmapIndexedNode
當鍵值對超過8個小于16個的時候采用的是這個結構。
BitmapIndexedNode 的子節點是 ValueNode或者BitmapIndexedNode。在 BitmapIndexedNode 里面查/增/改元素,都需要用到 bit-map(位圖)算法,BitmapIndexedNode.bitmap 存儲的是鍵名和存儲順序的位圖信息。例如 get 方法,通過 BitmapIndexedNode.bitmap,以及 key 名就可以獲取該鍵值對的排列序號,從而獲取到相應的 ValueNode。
BitmapIndexedNode.prototype.update:
update(ownerID, shift, keyHash, key, value, didChangeSize, didAlter) { if (keyHash === undefined) { keyHash = hash(key);//如果沒有hash值計算hash值 } // 根據BitmapIndexedNode中存儲的bitmap判斷當前傳入的key是否在某個位置已經存在。bitmap用32 位(二進制)來記錄元素是否存在。1表示存在,0表示不存在。 // 例如:keyHash 轉換為二進制后為11101110000110000001101001101 ,每5位為一組,shift假定為5 // (keyHash >>> shift)& MASK 取出需要的5位。第一次取到從低位開始的第一個5位:01101。keyHashFrag的十進制的值為13 // 1 << keyHashFrag 除第13位(從0開始)外,其他位都為0 即:10000000000000 // bit & bitmap 得出bitmap的第13位是否為1 // eg:bitmap=010101110111010000101011100010100 即 010101110111010000111011100010100 & 10000000000000 發現第13位為1 則存在這個元素 const keyHashFrag = (shift === 0 ? keyHash : keyHash >>> shift) & MASK; const bit = 1 << keyHashFrag; const bitmap = this.bitmap; const exists = (bitmap & bit) !== 0; ...... // 計算1的數量,即算出key在BitmapIndexedNode的存儲位置 // eg:bitmap=010101110111010000111011100010100 // bitmap & (bit - 1) 即 010101110111010000111011100010100 & 1111111111111 = 1011100010100 // 使用 popCount 函數計算有多少個1 計算出 有 6 個 1 // 即 idx = 6 // 所以我們需要查找的元素在BitmapIndexedNode的存儲位置為6 const idx = popCount(bitmap & (bit - 1)); // 如果這個位置有數據,取出當前BitmapIndexedNode中對應的數據,如果不存在,置為undefined const nodes = this.nodes; const node = exists ? nodes[idx] : undefined; const newNode = updateNode( node, ownerID, shift + SHIFT, keyHash, key, value, didChangeSize, didAlter ); if (newNode === node) { return this; } // 判斷是否超過16 if (!exists && newNode && nodes.length >= MAX_BITMAP_INDEXED_SIZE) { return expandNodes(ownerID, nodes, bitmap, keyHashFrag, newNode); } ...... // 生成新的Bitmap const newBitmap = exists ? (newNode ? bitmap : bitmap ^ bit) : bitmap | bit; // 生成新的nodes // eg:exists=false, idx=1情況: // oldArray: [vA, undefind, vC, vD] // newArray: [vA, newVNode, vC, vD] // exits=true情況,idx=8 // 原來位置8指向新生成的BitmapIndexedNode const newNodes = exists ? newNode ? setAt(nodes, idx, newNode, isEditable) : spliceOut(nodes, idx, isEditable) : spliceIn(nodes, idx, newNode, isEditable); if (isEditable) { this.bitmap = newBitmap; this.nodes = newNodes; return this; } return new BitmapIndexedNode(ownerID, newBitmap, newNodes); } }
這里我把popCount的源碼也貼出來:
function popCount(x) { x -= (x >> 1) & 0x55555555; x = (x & 0x33333333) + ((x >> 2) & 0x33333333); x = (x + (x >> 4)) & 0x0f0f0f0f; x += x >> 8; x += x >> 16; return x & 0x7f; }四、HashArrayMapNode
當鍵值對超過16個采用的是這個結構。
HashArrayMapNode 的親子元素可以是 HashArrayMapNode/BitmapIndexedNode/ValueNode。由此看來巨量的鍵值對,將有 HashArrayMapNode/BitmapIndexedNode/ValueNode 組合而成,而每個 HashArrayMapNode 最多有32個親子元素,BitmapIndexedNode 最多有16個親子元素。 HashArrayMapNode 類對應帶的 count,代表其子元素的數量。當需要讀取的時候,直接鍵名的哈希值,就能夠實現了
來一個龐大點的數據:
HashArrayMapNode.prototype.update:
update(ownerID, shift, keyHash, key, value, didChangeSize, didAlter) { if (keyHash === undefined) { keyHash = hash(key); } // 計算當前這個層級的idx const idx = (shift === 0 ? keyHash : keyHash >>> shift) & MASK; const removed = value === NOT_SET; const nodes = this.nodes; const node = nodes[idx]; ...... const newNode = updateNode( node, ownerID, shift + SHIFT, keyHash, key, value, didChangeSize, didAlter ); ...... if (isEditable) { this.count = newCount; this.nodes = newNodes; return this; } return new HashArrayMapNode(ownerID, newCount, newNodes); } }
function updateNode( node, ownerID, shift, keyHash, key, value, didChangeSize, didAlter ) { //沒有子節點了,即找到了這個值 if (!node) { if (value === NOT_SET) { return node; } SetRef(didAlter); SetRef(didChangeSize); return new ValueNode(ownerID, keyHash, [key, value]); } // 當還有子節點,則繼續遞歸查找 return node.update( ownerID, shift, keyHash, key, value, didChangeSize, didAlter ); }五、HashCollisionNode
雖然說hash沖突的情況是很少的,但是也有這種情況出現的。比如 key = "Aa" key = "BB",其哈希值是完全一樣的,這個時候就會啟動 HashCollisionNode 對象,將相同的哈希值的對象都放在同一個 HashCollisionNode 里面,而這里面就是簡單的線性讀寫數組了,沒有之前的 Bitmapped 操作,畢竟一次性不可能有太多相同哈希值的鍵名出現。
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/99365.html
摘要:文章博客地址所創建的數據有一個迷人的特性數據創建后不會被改變。是的基類,使用該類時需要至少繼承其子類中的一個??偨Y所提供的和固有的各有優勢,未來有可能制定一套原生的規范,在這之前,是一個不錯的選擇。參考資料官方文檔 文章博客地址:http://pinggod.com/2016/Immutable/ Immutable.js 所創建的數據有一個迷人的特性:數據創建后不會被改變。我們使用 ...
摘要:一向量字典樹字典樹,一種用空間換取時間的樹形數據結構,主要特點是利用字符串的公共前綴來挺升查詢性能。還有最終的數組表示的真實存儲的鍵值,存儲了,存儲了。這其中還有一種節點進行了沖突的處理。 本文受深入探究Immutable.js的實現機制這篇文章啟發,結合自己對Map源碼的解讀,談談我對immutable-js中map數據結構的理解,若有不正確的地方,歡迎指正。 一、Vector Tr...
摘要:首先是把原生的轉換為的類型此時的就是上面的數組判斷是否為空判斷是否已經是的類型序列化數組判斷是否超過。。。。。。若沒有超過,所有數據都放在中。通過計算要尋找的節點的位置在這個例子中,的值依次是。我上面所解析的情況有構建修改查詢。 一、存儲圖解 我以下面這段代碼為例子,畫出這個List的存儲結構: let myList = []; for(let i=0;i 0 && size < SI...
摘要:往往純的單頁面應用一般不會太復雜,所以這里不引入和等等,在后面復雜的跨平臺應用中我會將那些技術一擁而上。構建極度復雜,超大數據的應用。 showImg(https://segmentfault.com/img/bVbvphv?w=1328&h=768); React為了大型應用而生,Electron和React-native賦予了它構建移動端跨平臺App和桌面應用的能力,Taro則賦...
摘要:往往純的單頁面應用一般不會太復雜,所以這里不引入和等等,在后面復雜的跨平臺應用中我會將那些技術一擁而上。構建極度復雜,超大數據的應用。 showImg(https://segmentfault.com/img/bVbvphv?w=1328&h=768); React為了大型應用而生,Electron和React-native賦予了它構建移動端跨平臺App和桌面應用的能力,Taro則賦...
閱讀 3409·2021-09-22 16:00
閱讀 3452·2021-09-07 10:26
閱讀 2989·2019-08-30 15:55
閱讀 2858·2019-08-30 13:48
閱讀 1366·2019-08-30 12:58
閱讀 2162·2019-08-30 11:15
閱讀 945·2019-08-30 11:08
閱讀 525·2019-08-29 18:41