共计 5788 个字符，预计需要花费 15 分钟才能阅读完成。
上一片文章介绍的是 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 操作，毕竟一次性不可能有太多相同哈希值的键名出现。