昨天我們看了插補搜尋法，今天我們要來看雜湊表 (又名哈希表)，還記得我們之前Leetcode實作的Two Sum嗎? 今天要來學怎麼讓他變得更快~

常見名詞

• Key(鍵值) : 拿來查找資料的識別值，例如學號、編號
• Value(值) : Key對應存放的實際資料
• Hash Value / Hash Code(雜湊值) : 雜湊函式計算出來的結果，通常用來當索引
• Bucket(桶) : 雜湊表裡的儲存位置，存放資料的容器
• slot(槽) : 用來存放 key
• Collision(碰撞) : 兩個不同的key 算出同一個雜湊值

雜湊函式(Hash function)

雜湊函式是一個將輸入的 Key 轉換成數值的函式，這個數值可以用來決定資料在雜湊表中的位置

一、除法雜湊(Division Method)

最常見的做法，是把輸入值除以陣列大小再取餘數 : h(k) = k % m

k : 是輸入的鍵值(key)
m : 是陣列的大小
%(mod) : 是取餘數運算

舉例來說 :
假設陣列大小 m = 7，要存放的數字是 10 22 31:

h(10) = 10 % 7 = 3
h(22) = 22 % 7 = 1
h(31) = 31 % 7 = 3

但10 跟 31 算出來的雜湊值一樣都是3
這種情況稱為碰撞(Collision)，是雜湊函式(Hash function)設計裡幾乎無法完全避免的問題，
等一下會介紹怎麼處理它。

二、平方取中間值法(Mid-Square Method)

把 key 平方，再取中間幾位數字當作雜湊值。

例如 :
k = 512, k^2 = 262144
取中間 2位 : 21，所以 h(512) = 21。

三、折疊法(flodding)

將較長的 key 切割成數段 平均長度 的部分(最後一段不用)

• 位移折疊法(shift floding) : 相加後 mod bucket的數量即為索引
  

• 邊界折疊法(floading at the boundaries) : 將特定段落反轉後再相加
  

字串的雜湊函式

實務上常常需要對字串做雜湊(雜湊表的鍵值可能是名字、單字)。常見做法是把字串每個字元轉成對應數字(如ASCII碼)，再加權組合，這個做法稱為 多項式滾動雜湊函數（polynomial rolling hash function）:

p 是一個質數(通常選31 or 53)
s[i] 是字串第 i 個字元的數值
每個字元依照位置乘上不同權重，這樣即使兩個字串只是字元順序不同，雜湊值通常也會不同(例如 "ab" 跟 "ba" 雜湊值不同)
有興趣可以觀看以下文章 : String Hashing — CP-Algorithms，這邊就不細講了怕資訊量太大~

雜湊表

雜湊表（Hash Table）是一種利用 雜湊函式（Hash Function） 來儲存資料的資料結構。
透過一個函式，將資料轉換成陣列中的索引位置（Index），再把資料存放到對應的位置，透過這種方式，我們可以快速找到資料的位置

假設今天有一個大小為 10 的陣列
索引：0 1 2 3 4 5 6 7 8 9

我們設計一個雜湊函式

hash(key) = key % 10

15 % 10 = 5 代表 15 要放到索引 5

How to 解決碰撞(Collision)

因為很難設計一個近乎完美的雜湊，所以碰撞和溢位是不可免的
所以這邊來介紹幾種解決方法

1. 鏈結串列法 (Chaining)
   陣列的每個位置，不是直接存一個值，而是存一個鏈結串列。發生碰撞時，新資料就直接接到對應位置的鏈結串列後面
   

2. 重新雜湊法(rehashing)
   當雜湊表中的資料越來越多時，發生碰撞(Collision)的機率也會增加，這時候可以建立一個更大的雜湊表，將原本的資料重新計算位置、重新放入新的表格。

   例如原本的表格大小是 10，資料增加後建立更大的表格 : 30
   所以原本的 h(k) = k % 10 會變成：h(k) = k % 30，因此原本的資料需要重新計算位置

C++ STL(標準函式庫)

#include <unordered_map>
unordered_map<string, int> map;

兩個 int 分別為(key)鍵值 和 (value)
如果key 為字串

unordered_map<string, int> score;

score["Amy"] = 90;
score["Bob"] = 85;
score["Nina"] = 95;

Two sum (Hash table解法)

複習
給定一個整數陣列 nums，以及一個整數 target，請找出陣列中兩個數字，使它們的和等於 target，並回傳這兩個數字的索引（index）。

我們之前已經寫過O(n²)解法

這次要把他優化到 O(n)

class Solution { 
    public: 
    vector<int> twoSum(vector<int>& nums, int target) {
         unordered_map<int, int> map; 
         for(int i = 0; i < nums.size(); i++){
             int pos = target - nums[i]; 
             if(map.find(pos) != map.end()){ 
                return {map[pos], i}; 
            } 
            map[nums[i]] = i; 
        } 
        return {}; 
        } 
        
};

參考資料和書籍

1. https://cp-algorithms.com/string/string-hashing.html
2. 資料結構初學指引 : 入門精要版(第四版)