上一片文章介紹的是 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 操作，畢竟一次性不可能有太多相同哈希值的鍵名出現。
