摘要：那對(duì)于結(jié)構(gòu)又要如何處理，沒(méi)有結(jié)構(gòu)的索引，那怎么辦呢我們把鍵名變?yōu)楣Ｖ稻涂梢岳?。表示存在，表示不存在。例如轉(zhuǎn)換為二進(jìn)制后為每位為一組，假定為取出需要的位。類(lèi)對(duì)應(yīng)帶的，代表其子元素的數(shù)量。

上一片文章介紹的是 List 結(jié)構(gòu)。那對(duì)于 Map 結(jié)構(gòu)又要如何處理，沒(méi)有 List 結(jié)構(gòu)的索引，那怎么辦呢？ 我們把鍵名變?yōu)楣Ｖ稻涂梢岳瞺

HAMT：Hash Arrey Mapped Trie 。這個(gè)結(jié)構(gòu)就是Map中所用到的。

immutable中的hash計(jì)算核心代碼如下:

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);
}

上面只是一個(gè)計(jì)算hash值的函數(shù)，討論的重點(diǎn)再下面呢。

先看看Map的結(jié)構(gòu)：

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中沒(méi)有_tail，所有的數(shù)據(jù)都在_root里面。

再M(fèi)ap里，我們要分幾種情況：
1、當(dāng)鍵值對(duì)不超過(guò)8個(gè)
2、當(dāng)鍵值對(duì)超過(guò)8個(gè)小于16個(gè)
3、當(dāng)鍵值對(duì)超過(guò)16個(gè)
4、hash沖突怎么辦

用下面這段代碼調(diào)試看看每種情況的結(jié)構(gòu)：

  let jsObj = {};
  for (let i = 0; i < 8; i++) {
      jsObj[Math.random()] = Math.random();
  }
  let map1 = Immutable.Map(jsObj);
  console.log(map1);

當(dāng)鍵值對(duì)不超過(guò)8個(gè)的時(shí)候采用的是這個(gè)結(jié)構(gòu)。

這種方式是最簡(jiǎn)單的，所有鍵值對(duì)保存在 entries 里面。同時(shí) get/set 方法都較為簡(jiǎn)單，直接遍歷一下獲取就好了。

從圖中我們可以看到，immutable把key和value轉(zhuǎn)換為一個(gè)數(shù)組的arr[0]和arr[1]來(lái)存儲(chǔ)。

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;//是否存在這個(gè)key
    ......
    // 判斷個(gè)數(shù)是否大于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一個(gè)值進(jìn)去
    }
    ......
    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;

當(dāng)鍵值對(duì)超過(guò)8個(gè)小于16個(gè)的時(shí)候采用的是這個(gè)結(jié)構(gòu)。

BitmapIndexedNode 的子節(jié)點(diǎn)是 ValueNode或者BitmapIndexedNode。在 BitmapIndexedNode 里面查/增/改元素，都需要用到 bit-map(位圖)算法，BitmapIndexedNode.bitmap 存儲(chǔ)的是鍵名和存儲(chǔ)順序的位圖信息。例如 get 方法，通過(guò) BitmapIndexedNode.bitmap，以及 key 名就可以獲取該鍵值對(duì)的排列序號(hào)，從而獲取到相應(yīng)的 ValueNode。

BitmapIndexedNode.prototype.update:

update(ownerID, shift, keyHash, key, value, didChangeSize, didAlter) {
    if (keyHash === undefined) {
      keyHash = hash(key);//如果沒(méi)有hash值計(jì)算hash值
    }
    // 根據(jù)BitmapIndexedNode中存儲(chǔ)的bitmap判斷當(dāng)前傳入的key是否在某個(gè)位置已經(jīng)存在。bitmap用32 位（二進(jìn)制）來(lái)記錄元素是否存在。1表示存在，0表示不存在。
  
    // 例如：keyHash 轉(zhuǎn)換為二進(jìn)制后為11101110000110000001101001101 ,每5位為一組，shift假定為5
    // （keyHash >>> shift）& MASK 取出需要的5位。第一次取到從低位開(kāi)始的第一個(gè)5位：01101。keyHashFrag的十進(jìn)制的值為13
    // 1 << keyHashFrag 除第13位（從0開(kāi)始）外，其他位都為0 即：10000000000000
    // bit & bitmap 得出bitmap的第13位是否為1 
    // eg:bitmap=010101110111010000101011100010100   即 010101110111010000111011100010100 & 10000000000000 發(fā)現(xiàn)第13位為1 則存在這個(gè)元素
    const keyHashFrag = (shift === 0 ? keyHash : keyHash >>> shift) & MASK;
    const bit = 1 << keyHashFrag;
    const bitmap = this.bitmap;
    const exists = (bitmap & bit) !== 0;
    ......
    // 計(jì)算1的數(shù)量，即算出key在BitmapIndexedNode的存儲(chǔ)位置
    // eg:bitmap=010101110111010000111011100010100
    // bitmap & (bit - 1) 即 010101110111010000111011100010100 & 1111111111111 = 1011100010100
    // 使用 popCount 函數(shù)計(jì)算有多少個(gè)1 計(jì)算出 有 6 個(gè) 1
    // 即 idx = 6
    // 所以我們需要查找的元素在BitmapIndexedNode的存儲(chǔ)位置為6
    const idx = popCount(bitmap & (bit - 1));
    // 如果這個(gè)位置有數(shù)據(jù)，取出當(dāng)前BitmapIndexedNode中對(duì)應(yīng)的數(shù)據(jù)，如果不存在，置為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;
    }

    // 判斷是否超過(guò)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
    // 原來(lái)位置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的源碼也貼出來(lái)：

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;
}

當(dāng)鍵值對(duì)超過(guò)16個(gè)采用的是這個(gè)結(jié)構(gòu)。

HashArrayMapNode 的親子元素可以是 HashArrayMapNode/BitmapIndexedNode/ValueNode。由此看來(lái)巨量的鍵值對(duì)，將有 HashArrayMapNode/BitmapIndexedNode/ValueNode 組合而成，而每個(gè) HashArrayMapNode 最多有32個(gè)親子元素，BitmapIndexedNode 最多有16個(gè)親子元素。 HashArrayMapNode 類(lèi)對(duì)應(yīng)帶的 count，代表其子元素的數(shù)量。當(dāng)需要讀取的時(shí)候，直接鍵名的哈希值，就能夠?qū)崿F(xiàn)了

來(lái)一個(gè)龐大點(diǎn)的數(shù)據(jù)：

HashArrayMapNode.prototype.update:

  update(ownerID, shift, keyHash, key, value, didChangeSize, didAlter) {
    if (keyHash === undefined) {
      keyHash = hash(key);
    }
    // 計(jì)算當(dāng)前這個(gè)層級(jí)的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
) {
  //沒(méi)有子節(jié)點(diǎn)了，即找到了這個(gè)值
  if (!node) {
    if (value === NOT_SET) {
      return node;
    }
    SetRef(didAlter);
    SetRef(didChangeSize);
    return new ValueNode(ownerID, keyHash, [key, value]);
  }
  // 當(dāng)還有子節(jié)點(diǎn)，則繼續(xù)遞歸查找
  return node.update(
    ownerID,
    shift,
    keyHash,
    key,
    value,
    didChangeSize,
    didAlter
  );
}

雖然說(shuō)hash沖突的情況是很少的，但是也有這種情況出現(xiàn)的。比如 key = "Aa" key = "BB"，其哈希值是完全一樣的，這個(gè)時(shí)候就會(huì)啟動(dòng) HashCollisionNode 對(duì)象，將相同的哈希值的對(duì)象都放在同一個(gè) HashCollisionNode 里面，而這里面就是簡(jiǎn)單的線性讀寫(xiě)數(shù)組了，沒(méi)有之前的 Bitmapped 操作，畢竟一次性不可能有太多相同哈希值的鍵名出現(xiàn)。