前言

今天要介紹的是 Hash Table，它在 JavaScript 裡最常見的樣貌就是我們每天都在寫的物件。

前面兩篇都在談 Array，而 Array 快的地方在於，只要給一個數字 index，位置就能直接算出來，然而實際在寫程式的時候，我們手上有的東西不一定是 0、1、2 這種可以直接拿來當 index 的數字。

上一篇文章提到，要在一堆資料裡找東西的做法是把資料排好序，用 Binary Search 每次砍掉一半，換來 O(log N)，但如果我們想知道的事很單純呢？只是想知道「編號 A-1025 那筆的金額是多少」，不需知道它排在第幾位。

那有沒有辦法讓「給我這個編號，直接把那筆訂單拿出來」也像 orders[2] 一樣，一步就到呢？今天就來看看～

同一個問題，三種結構的答案

在拆解之前，先把前幾篇的東西放在一起看。假設手上有一批訂單，我們想知道編號 A-1025 那筆的金額是多少，那麼到目前為止學過的做法各要花多少成本？

前兩列就是 Day 05 和 Day 06 的內容，而它們其實有個共同點：不論比得多塊、多聰明，終究都還是在「比較」，Binary Search 只是讓每一次比較排除掉更多資料，本質上仍然得一路縮小範圍才能逼近答案。

第三列 Hash Table 是今天的主題，它完全不比較，而是直接算出那筆資料在哪裡，而今天要看的就是這個「算出來」是怎麼做到的。

為什麼不直接把編號當 index？

一樣用訂單來舉例，不過這批資料的形狀和前兩篇不太一樣。Day 05 的訂單是一個裝著物件的陣列，每一筆都有 id 和 amount；到了 Day 06 要談搜尋的時候，因為需要拿來比對的只有編號，就簡化成 [1003, 1008, 1012, ...] 這種只剩編號的陣列。而今天想問的是「編號 A-1025 那筆的金額是多少」，光有編號回答不了，還得有編號對應的內容，所以這裡先把訂單改寫成一個編號直接對應到一筆資料的形式，編號也跟著改回 Day 05 那種帶前綴的字串：

const orders = {
  'A-1003': { amount: 180 },
  'A-1008': { amount: 500 },
  'A-1025': { amount: 90 },
  'A-1031': { amount: 510 },
  'A-1042': { amount: 240 },
};

A-1003 是一個字串，而 Array 的 index 只能是數字，也就是說如果我們想改用 Array 來放這批訂單，A-1003 沒辦法拿來當位置用。

不過可能有人會想說，那如果編號本來就是純數字 1003 呢？這樣不就可以直接 orders[1003] 了嗎？

技術上確實可以，但也要考慮代價，光是要讓 orders[1003] 這個位置存在，陣列就得從 index 0 一路開到 1003，也就是 1004 格，而這 1004 格裡真正裝了東西的只有一格。5 筆訂單全放進去也不會好到哪裡去，編號最大的 1042 會把長度撐到 1043 格，其中 1038 格全都空著，超過 99% 的空間是浪費掉的。

空間之外還有另一層代價。Day 05 談過 V8 的 elements kind，其中一個判斷方向就是陣列裡有沒有空洞，而把編號當 index 正好就是那篇說要避開的跳號賦值：

const orders = [];
orders[1003] = { amount: 180 };

orders.length; // 1004      ← 只放了 1 筆，長度卻是 1004
kind(orders); // HOLEY_ELEMENTS

kind 是 Day 05 那個用 --allow-natives-syntax 把 elements kind 拼出來的小工具（完整程式碼）。可以看到只放進一筆訂單，這個陣列就已經被標成 HOLEY 了，之後每次讀取都得多確認一次原型鏈上有沒有定義那個 index，而且這個標記是單向的，後面再怎麼補都回不去。

因此「編號當 index」會有兩個問題：陣列開得又大又空，佔空間；而且從最快的那一級掉了下來，影響存取速度。後面這一項是 JavaScript 特有的，和 V8 怎麼標記陣列有關。

圖 1 兩種放法要開多少格

這樣我們就要放棄 Array 這個解法了嗎？也不一定，因為它快速存取的特性正是我們想要的，orders[2] 之所以能一步抵達，是因為 index 可以直接換算成記憶體位址，而這是目前為止唯一不必比較就能定位的機制，問題在於 A-1003 沒辦法像 2 那樣換算成位址。

所以真正卡住的地方是，我們想用來查找的東西（A-1003），和 Array 能接受的位置（index 數值）之間少了一層轉換。只要有東西負責把 A-1003 翻譯成 Array 收得下的數字，後面就還是那套熟悉的快速定位方法，而 Hash Table 要做的正是補上這層翻譯。

圖 2 A-1003 到 index 中間缺一段

先認識它的介面：Dictionary

在談轉換怎麼做之前，先看看這種結構長什麼樣子。一樣先給一句話的定義：

Dictionary（字典）是一種用 key 存取 value 的資料結構，給定一個 key，就能取出與它配對的 value。

這個結構在不同語言裡有不同的名字，例如 Hash、Map、Hash Map、Dictionary、Associative Array，指的都是同一個概念，差別只在命名習慣。JavaScript 裡我們最熟悉的物件就是它的一種實作，ES6 之後另外提供的 Map 也是。

JavaScript 的物件和 Map 雖然是同一個概念的兩種實作，實際用起來還是有幾個差異。最主要的是 key 的型別，物件的 key 只能是字串，就算寫成數字也會被悄悄轉掉：

const object = {};
object[1] = 'a';
object['1'] = 'b';

object; // { '1': 'b' }  ← 後者蓋掉了前者
Object.keys(object); // ['1']         ← 只有一個 key，而且是字串

Map 就沒有這個限制，它的 key 可以是任何型別，連函式或陣列都行，數字 1 和字串 '1' 在它眼裡也是兩個不同的 key：

const m = new Map();
m.set(1, 'a');
m.set('1', 'b');

m.size; // 2

另一個差別是走訪的順序。物件碰到看起來像整數的 key 時，會照數值大小排，而不是照存進去的順序：

Object.keys({ 'A-1042': 1, 'A-1003': 1, 'A-1025': 1 });
// ['A-1042', 'A-1003', 'A-1025']   ← 字串 key 保留插入順序

Object.keys({ 1042: 1, 1003: 1, 1025: 1 });
// ['1003', '1025', '1042']         ← 數字 key 被重新排過

Map 則一律照插入順序走訪，不過要注意的是，這個順序保證是 Map 自己額外維護的東西，並不是 Hash Table 這個結構本身會提供的。

所以前面那個 orders 物件，用起來就是一張 Hash Table（V8 詳細實作在文章最後會補充）。今天就來看看它背後的一些東西～

Hash Function 在做什麼

前面說到，我們想用來查找的東西和 Array 能接受的位置之間少了一層轉換，那層轉換就是 hash function。

Hash Function（雜湊函式）會把一個較寬的定義域映射到較窄的值域，也就是不管輸入什麼 key，輸出的數字都會落在我們指定的範圍內。

（對定義域和值域不熟悉的可參考這篇關於函數的定義）

可以稍微注意一下後半句，它不只是「把字串變成數字」而已，還要保證變出來的數字剛好可以當成陣列的位置用，否則轉了也沒有意義。

不過並不是任何一個能把 key 變成數字的函式都能拿來用，hash function 需要滿足一些條件：

1. 同樣的輸入，一定要得到同樣的輸出
2. 算起來要夠快，而且成本不能隨著資料變多而增加
3. 輸出要盡量平均分布在值域裡

那字串要怎麼變成數字呢？最容易理解的做法是先給每個字母一個編號，像是 A = 1、B = 2、C = 3 這樣一路排下去，於是 BAD 就變成 2、1、4 三個數字。拿到這三個數字之後還要再把它們併成一個，而併的方式其實有很多種：

三種都是合格的 hash function，選哪一種都可以，重點是規則一旦定了就不能再改。

實際寫程式時我們不必自己排字母表，因為每個字元本來就有對應的數字，charCodeAt 可以直接取出來。以 A-1003 為例：

'A-1003'.split('').map((c) => c.charCodeAt(0));
// [65, 45, 49, 48, 48, 51]

把這 6 個數字相加會得到 306，這就是 A-1003 的 hash 值。

一個 key 只能有一個答案

A-1003 這次算出 306，下次、下下次都必須還是 306。這是前面三點裡的第一點，這性質叫做 determinism（決定性）：

同樣的輸入，每一次都必須產生同樣的輸出。

那它被破壞的時候會發生什麼事呢？假設有人把 hash function 寫成回傳一個亂數，那麼存 A-1003 的時候它可能算出 5，於是訂單被放進第 5 格；等到要取出來的時候再算一次，這次得到 2，程式跑去第 2 格看，發現那裡什麼都沒有，只好回報找不到，資料明明還在卻永遠拿不回來。用當前時間、或任何會隨著執行環境改變的東西來算 hash，也都會有一樣的問題，hash function 要能定位資料，前提是它每次都指向同一個地方。

圖 3 決定性被破壞時：存和取算出不同位置，就找不回資料

「同樣的輸入，每一次都必須產生同樣的輸出」這句話可能有點耳熟，因為它就是數學上「函數」的定義，也是 [Day04] Pure Function 是什麼？ 談過的純函數概念。而有意思的是，這條規則在 Hash Table 裡要守兩次，因為這個結構其實包含兩層對應，一層是 hash function 負責的「key 到位置」，另一層是表本身負責的「key 到 value」。

第一層剛剛講完了，第二層的意思則是同一張表裡不能同時存在兩筆 A-1003，否則 orders['A-1003'] 到底該給出哪一筆就沒有答案了。那如果真的把同一個 key 存進去兩次呢？多數語言的處理方式是一致的，保留原本的 key，並用新的 value 蓋掉舊的：

const menu = {};
menu['hamburger'] = 2.5;
menu['hamburger'] = 3.0;

menu['hamburger']; // 3.0 ← 後面存的蓋掉前面的
Object.keys(menu).length; // 1   ← 表裡仍然只有一個 key

不過函數的定義還有反過來的另一半：不同的輸入可以對應到同一個輸出。這一半在兩層對應裡都成立，在「key 到 value」這一層，它的意思是不同的 key 可以配到相同的 value，畢竟菜單上同價位的品項本來就可能有好幾樣：

const menu = { hamburger: 2.5, 'chicken sandwich': 2.5 };

圖 4 Key 與 Value 的對應關係

而在「key 到位置」那一層，就有些麻煩了，因為它代表兩個不同的 key 可能被算到同一格去。這個情況叫做碰撞，會在下一篇談到。

從 hash 值走到 bucket

A-1003 算出來是 306，那就把它放進第 306 格嗎？這樣一來又繞回這篇開頭那個問題了，編號越大就得把陣列開得越長，而且大半的格子都空著。實際的做法會是，先決定這個 hash table 要佔用幾格的位子，再把算出來的數字壓進這個範圍內，而壓的方式就是取餘數。

假設預計佔用 8 格，306 % 8 得到 2，那筆訂單就放進第 2 格，而這一步就是前面那句「保證落在指定範圍內」的實作方式，不管 key 有多長、算出來的數字有多大，除以 8 取餘數之後一定落在 0 到 7 之間，剛好就是這張表所有合法的位置。開別的大小也一樣，除以幾就落在幾格的範圍裡。

表裡的每一格習慣上稱為 bucket（桶），而 bucket 裡存的是 key 和 value 整組，不是只有 value。為什麼 key 也要存進去？因為不同的 key 有可能落到同一格，把 key 一起存著，之後才有辦法確認拿出來的到底是不是我們要的那一筆。

把 5 筆訂單放進 8 格的表，結果會是這樣：

圖 5 key 怎麼變成 bucket 位置

編號在數值上很接近的訂單，被打散到表的不同位置，且順序和原本的編號大小無關。這也是 Hash Table 和上一篇 Ordered Array 的差別，它不維持任何順序。

那不維持順序會有什麼影響呢？Ordered Array 之所以能用 Binary Search，靠的就是「已經排好序」這個額外資訊，而 Hash Table 把資料打散之後，這個資訊就不存在了。因此像「找出金額最高的那筆訂單」或「列出編號介於 1010 到 1030 之間的訂單」這種需要順序才能回答的問題，Hash Table 無法快速回答，只能整張表從頭到尾走一遍。它犧牲順序，換到的是另一件事：只要知道 key，就能一步到位。

寫成程式

把前面那些步驟湊起來，來寫一個簡單的 hash table：

class SimpleHashTable {
  constructor(size = 8) {
    this.buckets = Array.from({ length: size }, () => []); // 每一格都先放一個空陣列
  }

  hash(key) {
    let total = 0;
    for (const char of key) {
      total += char.charCodeAt(0); // 每個字元都有對應的數字
    }
    return total % this.buckets.length; // 壓進表的範圍
  }

  set(key, value) {
    const bucket = this.buckets[this.hash(key)];
    const pair = bucket.find(([k]) => k === key);
    if (pair) {
      pair[1] = value; // 同一個 key 就覆蓋掉舊的
    } else {
      bucket.push([key, value]); // key 和 value 一起存
    }
  }

  get(key) {
    for (const [k, v] of this.buckets[this.hash(key)]) {
      if (k === key) return v; // 確認是不是要找的那一筆
    }
    return undefined;
  }
}

set 和 get 都是先呼叫同一個 hash 算出位置，再去那一格處理，而兩邊算出來的位置一定相同，這就是前面 determinism 在程式裡的樣子。

set 裡那段 find 對應的則是前面說過的 key 唯一性，先看看這一格裡有沒有同樣的 key，有的話就覆蓋掉舊的 value，沒有才新增一組，這樣同一個 A-1003 才不會在表裡出現兩次。

另外補充，這個 hash 只是為了解釋原理而寫的最簡版本，真實世界使用的 hash function 遠比它複雜，各語言內建的版本都經過大量最佳化，不會直接拿字元碼相加作為正式實作。

走一次完整的流程

把 A-1025 這筆訂單拿來實際走一遍，先看存進去的時候：

1. set('A-1025', { amount: 90 }) 呼叫 hash('A-1025')
2. 取出每個字元對應的數字：65、45、49、48、50、53
3. 相加得到 310
4. 310 % 8 得到 6
5. 到 buckets[6] 看看有沒有同樣的 key，沒有
6. 把 ['A-1025', { amount: 90 }] 整組推進 buckets[6]

取出來的時候，前四步幾乎一模一樣：get('A-1025') 呼叫同一個 hash('A-1025')，算出來還是 310、取餘數還是 6，接著直接跳到 buckets[6]，比對 key 確認是 A-1025，回傳 { amount: 90 }。

第 4 步那個「直接跳到」才是重點。整段流程裡，程式從來沒有看過 bucket 0 到 5，也沒有看過 bucket 7，它不知道表裡還有沒有別的訂單，也不在乎總共存了幾筆，就這樣算到第 6 格去。這就是 O(1) 想表達的事情，這段流程的長度和表裡有多少資料無關，5 筆訂單是這幾步，500 萬筆訂單也還是這幾步。

那如果要找的是一筆根本不存在的訂單呢？假設查 A-9999，流程其實沒有差別，hash('A-9999') 算出 338，338 % 8 得到 2，程式跳到 buckets[2]，發現裡面是 A-1003，key 對不上，於是回傳 undefined。

在這情況下，「找不到」和「找得到」花的力氣幾乎相同，程式都只看了一格。Day 06 的 Binary Search 就不是這樣，那時找不到反而是最慢的情況，得一路砍到範圍空掉才能確定。

另一種 hash function

講到 hash function，不知大家有沒有聽過 md5、SHA-1、SHA-256 這些名字？它們也是 hash function 的一種，一樣把任意長度的輸入轉成固定長度的輸出，也具備前面說的決定性，不過用途和我們今天寫的那個不太一樣。

今天這種 hash function 追求的是快，因為它在每一次存取時都會被呼叫，而 SHA-256 複雜得多，算一次要花上不少時間，卻大量被用在密碼學上，原因是那裡在意的是另一件事：光看輸出的那串值，沒辦法回推原本的輸入是什麼。這個性質叫做 one way，而 Hash Table 完全用不到它。

四種操作各要多少？

延續 Day 05 分析 Array 的那四種操作，這些問題也可以用來檢視 Hash Table：

稍微補充下，Insert 和 Delete 的 O(1) 和查找一樣都是平均值。它們也得先算出 bucket 位置，而如果有很多筆資料剛好擠在同一格，在那一格裡處理正確的那一筆就不再是一步的事情了。

Day 05 說過，Array 的 delete 成本高是因為「不能有洞」，移除之後得把後面的元素全部往左補上來；而 Hash Table 相反，它的位置本來就是 hash 出來的，表裡有洞完全不影響任何一筆資料的定位。

Insert 那一列的理由相同，Day 06 的 Ordered Array 為了維持排序，找到位置之後還得把後面的元素通通往右挪一格，挪動本身就是 O(N)；Hash Table 則不必如此，新訂單該去哪一格是算出來的，和其他訂單待在哪裡沒有關係，算完放進去就結束了。

也就是說，同一個「位置需不需要連續」的性質，在兩種結構上導出了相反的結果。Array 用連續換到了「可以用算式算位置」，代價是任何改動都要維持連續；Hash Table 放棄連續，改用 hash function 來定位，於是插入和刪除都不再牽動別人。

平均 O(1) 依賴哪些條件？

大部分提到 hash table 查找的複雜度時，會說是「平均」O(1)，那為什麼不直接說 O(1) 呢？因為查找的背後可能還有別的事要做，並不是每次都 O(1)。那要讓查找真的維持在 O(1)，需要哪些條件成立？

答案就在前面列出的那三個條件裡。先看第二點，算 hash 的成本不能隨資料量增加，每次存取都要算一次 hash，聽起來像是額外的開銷，但各語言內建的 hash function 都已經最佳化到很快，而且它的計算量只和 key 的長度有關，不會因為表裡多了幾百萬筆資料就變慢，這通常直接視為 O(1)。

再來看第三點，輸出要夠分散，前面開 8 格的時候，5 筆訂單剛好落在 5 個不同的 bucket，所以每一格都只要看一筆就能回答，但如果反過來，所有 key 都被算到同一格去，這張表實際上就退化成一個普通的陣列了，查找又得回到逐一比對。因此 hash function 除了要快、要具備決定性，還得盡量把 key 打散到不同的 bucket，這個性質一般稱為 distribution。

麻煩的是，輸出分散這件事很難被完全滿足，而這就是「平均」兩個字的由來。先看一個極端的情況：我們的表只有 8 格，那只要存進第 9 筆訂單，就一定至少有 2 筆落在同一格，這不需要任何巧合，純粹是因為 9 個東西要放進 8 個位置，總得有一格裝到 2 個以上。

那把表開大一點呢？開到 1,000 格、100 萬格，撞在一起的機會確實會變小，但問題的本質並沒有改變，hash function 的輸出永遠比輸入少，key 可以是任意長度的字串、數量沒有上限，而 bucket 永遠只有固定的幾格，把無限多種可能塞進有限的格子裡，重複是無法避免的。

而且也不必等到那麼極端才會重疊。前面那個字元碼相加的版本就有個很明顯的弱點，它只在乎用到了哪些字元、完全不管順序，所以像 A-1003 和 A-1030 這種只是把數字換個位置的編號，算出來的值會一模一樣，連取餘數那一步都還沒走到就已經撞在一起了。

那撞在一起的時候會發生什麼事、又該怎麼處理？這會在下一篇談到～

單向的快速查找

最後還要補充一件事：Hash Table 的快是單向的，給定 key 求 value 走的是 key → hash → bucket → value 這條路，一步到位；但若反過來，手上只有 value 想找出對應的 key，就完全沒有捷徑了。原因是 hash function 只吃 key，value 根本沒有參與位置的計算，因此從 value 推不出它被放在哪一格，只能把整張表從頭走一遍。舉例來說，想知道「有沒有哪一筆訂單的金額剛好是 500」時，程式就只能把 8 個 bucket 一個一個打開、逐筆比對金額。

如果覺得有點眼熟，那不是錯覺，Binary Search 也只有在「照排序的那個欄位查」的時候才快，換一個欄位就得退回逐一檢查。兩種結構的限制長得不一樣，但它們的加速永遠是針對某一種特定的查法，不會是全面的。

圖 6 兩個查找方向的差別

JavaScript 的物件底層實作

這裡稍微延伸一下 V8 內部實作～JavaScript 物件確實就是前面說的那種 Dictionary，給一個 key 就能取出 value，但 V8 預設並不是拿一張 hash table 來實作它。

為什麼不用 hash table 實作物件？

先想想看，如果真的用 hash table 會怎樣：每讀一次 order.amount，就得把 'amount' 這個字串 hash 一次、找到 bucket、再比對 key——正是這篇前面寫的那一整套。而屬性讀取會是一個很頻繁的操作，每次都做這些事，成本並不低。

因此 V8 選擇繞過它，把「名字對應到第幾個位置」這件事先算好、存在別的地方，V8 原文敘述為「the name itself and the position where the value is stored」，也就是名字，以及值放在第幾個位置先被記錄起來。取值於是變成按編號存取，而不是按名字查表，而按編號存取一塊連續的儲存區，正是 Day 05 提過的 base + index × elementSize 在做的事，可以理解成 V8 想辦法把一個字典問題變回了陣列問題。

HiddenClass：把形狀抽出來共用

那它怎麼事先知道名字對應的位置？做法是把「形狀」抽出來共用，而這裡的形狀指的是「有哪些屬性、以什麼順序加入」，記錄形狀的那個東西則叫做 HiddenClass。

可以把它想成資料表的欄位定義：一萬筆訂單共用同一份「第 0 欄是 name、第 1 欄是 amount」的定義，每一列只存值。這裡的重點是，屬性名稱只在那份定義裡存一份，每一列裡完全不存名字。V8 實作就類似如此，物件本體只留下值、排成一個單純的陣列，名字（物件屬性）則是在共用的 HiddenClass 上。

所以前面那兩筆訂單在記憶體裡大概會長這樣：

圖 7 名字在 HiddenClass，值在物件裡

兩個物件指向同一個 HiddenClass，amount 在 a 裡是第 1 格，在 b 裡也是第 1 格，格號是跟著形狀走的，不是跟著哪一個物件，因此查一次就能用在所有同形狀的物件上。

稍微看一下程式，底下幾段都會用到 V8 的內部函式，和 Day 05 那個 kind 一樣要加上 --allow-natives-syntax 才能執行：

const a = { name: 'A-1003', amount: 180 };
const b = { name: 'A-1008', amount: 500 };

%HaveSameMap(a, b); // true ← 兩個物件共用同一個 HiddenClass

格號查一次就能重複使用

這樣繞一圈處理 HiddenClass 的好處是，格號一旦查出來就能重複使用。若程式裡出現一行 order.amount，第一次執行時 V8 確實得循著 HiddenClass 去查「amount 在第幾格」，但查完之後它會把答案記在那一行上：下次只要確認物件指向的還是同一個 HiddenClass，就直接拿那個格號去取值，不必再查一次。而且記住的是格號，而不是某個物件的實際位置，所以同一行程式碼跑過一萬個同形狀的物件，這個查找總共只做了一次。hash table 沒有「形狀」這種比對一次就能確認的東西，每一次讀取都得從頭算起。

前提是形狀要一樣

不過這有個前提：形狀要一樣。資料表的欄位是事先宣告好的，HiddenClass 則是邊加屬性邊長出來的，而且每個屬性的格子在被寫入的當下就決定，之後不會再移動。所以同一組屬性換個順序寫，第 0 格裝的東西就不一樣了，兩者算不同的形狀：

const c = {};
c.name = 'A-1003';
c.amount = 180;
const d = {};
d.amount = 180;
d.name = 'A-1003';

%HaveSameMap(c, d); // false

不同形狀會影響速度，但慢的其實不是這兩個物件本身，它們各自都有好好的形狀，讀取仍然是一步到位。變慢的是讀取它們的那一行程式碼，本來只要記一個形狀對一個格號，現在得記兩組，每次呼叫還要先確認這次拿到的是哪一種。

delete 後才會換回 hash table

那什麼時候 V8 才會用上 hash table 呢？delete 就是一個例子：

const order = { name: 'A-1003', amount: 180, note: 'x' };
%HasFastProperties(order); // true

delete order.amount;
%HasFastProperties(order); // false ← 已經切換成 dictionary mode

原因和剛剛提的規則有關，格子一旦決定就不會移動，刪掉 amount 之後第 1 格變成一個洞，而 note 還留在第 2 格，要維持原本那套算法，V8 只有兩條路：

1. 留著這個洞：但這種中間有洞的形狀在共用的體系裡無處可歸，得為這一個物件單獨開一份定義，共用的意義就沒了
2. 把 note 往前搬到第 1 格：但這樣所有已經記住「note 在第 2 格」的程式碼就全錯了

於是 V8 選了第三條路，不再假裝這個物件有形狀，直接改用 hash table，至於為什麼是 hash table，原因這篇前面有提到，hash table 裡有洞不影響資料的定位。

換成 hash table 也有對應代價，這個物件從此得自己帶著屬性名稱，因為沒有共用的定義可以查了，而且每次讀取都得重新 hash 一次。也就是說，我們在這篇手寫的那個 SimpleHashTable，大概就是 V8 在 delete 之後把物件變成的樣子。

最後補充兩件事。一是屬性多到一定程度時，放不下的值會溢出到物件之外的另一塊空間，取值就多一次跳轉，不過名字仍然只存在 HiddenClass 上。

二是這節講的都是字串 key 的屬性，走的是 properties store。Day 05 談的 elements kind 則是整數索引屬性的那一半，走的是 elements store，那邊不需要「名字對到第幾格」這層轉換，因為 key 本身就是格號。（更詳細的機制可以參考 V8：Fast properties in V8）

小結

小小總結一下今天對 Hash Table 的認識～

• 為什麼需要 Hash Table？ 因為現實中拿來查找的東西通常是編號、email 這類非數字的 key，而 Array 的位置只吃數字，中間需要一層轉換。
• 用了 Hash Table 之後差在哪？ 任意 key 都能像 index 一樣直接定位，而且插入和刪除不再牽動其他元素；代價是資料完全不維持順序。
• Hash Table 到底是什麼？ 用 hash function 把 key 轉成 bucket 位置，並在 bucket 裡存放 key-value 配對的結構。

最後補充幾點～

• Hash function 必須是決定性的，否則存進去的資料就再也定位不回來。
• Bucket 裡存的是 key 和 value 整組，因為需要確認拿出來的是不是要找的那一筆。
• Key 不能重複，存第二次會蓋掉原本的 value；Value 則沒有這個限制。
• 快是單向的，key → value 是平均 O(1)，反過來則是 O(N)。

圖表說明：本文圖表由作者整理，並使用 Claude Code 協助繪製；內容與數據由作者確認。

Reference

• Master the Coding Interview: Data Structures + Algorithms
• 《A Common-Sense Guide to Data Structures and Algorithms, Second Edition》
• samwho：Hashing
• MDN：Map
• V8：Fast properties in V8
• Rust Algorithm Club：HashMap