本文為清華大學開放式課程上課心得整理。
日查生活中處理資料，很常遇到插入、刪除等等動作，根據前面所介紹的資料處理方法，不同的方式會造成不同的時間複雜度；而雜湊則可以在 O(1) 的時間複雜度上完成資料處理，是非常方便的手法。
Hash Tables（ht）
Hash Table 是一個 container，裡面儲存字典（dictionary）的 record / key pair，record 指向資料儲存的位置。
Hash Table 的編號從 0 開始，直到 n−1 為止，通常來說 ht 裡的每個 bucket 都能儲存一組 pair（slots），但有時也會出現可以儲存四組的狀況，取決於如何運用。
Hash Function
Hash Function（h(k)）是用來產生 bucket address（也就是前述 dictionary pair 的 key），Hash Function 可以將 key mapping 到某個 bucket。
接下來介紹幾個與 hash 相關的名詞定義：
・key density（n／T）：n 指的是 table 中 pair 的數量，T 則是所有可能的 key 的數量。
・Loading density or loading factor：計算公式為 n / ( s * b ) ，s 指的是 table 中 pair 的最大存載量，n 為已經使用的存載量。
・synonyms：如果有兩個 key k1、k2，經過 Hash Function 的計算之後得到相同的結果，我們便稱呼這兩個 key 為 synonyms。這裡我們可以理解到幾個狀況：
・有時候不同的 key 會 mapping 到同一個 home bucket
・當一個 key mapped 到一個非空的 home bucket 時，這種狀況我們稱為撞擊（collision）
・如果 key mapped 到的是一個 full home bucket，則稱為 overflow
・如果 bucket 只能存放一個 slot，collision 同時也會是 overflowOverflow
接著要來討論 overflow 的處理方法。當 hash 的紀錄存入的 bucket 已經滿了、無法繼續存放新紀錄的時候，便稱為 overflow，這時會用一個 overflow file 把這些新紀錄存起來，overflow file 和 bucket 可以串接在一起。
當 bucket 上的 store number 不夠的時候，就需要對資料做處理，這稱為 overflow handling。overflow handling 主要有兩個方向：
・Open Addressing
Linear Probing
insert：先計算 h(k)，再依照順序尋找最接近且沒有放置資料的 bucket 將資料置入，當全部的 bucket 都填滿時，就代表 hash table 的 size 要增加，就 double 它的 size。
search：先計算 h(k)，在進入對應 bucket 做尋找Quadratic Probing
一樣先計算 h(k)，再檢查是否還有空的 bucket，若是 bucket 已經滿了，便利用算式 (h(k) +(或減) i2)%b，1 <= i <= (b-1)/2 去找出是否有空的 bucket，如果有的話便將資料儲存進去。Rehashing
一個 hash 有複數個 hash function，overflow 時則改以下個 function 計算 bucket，直到找到空位為止。
・Chaining：直接放在 bucket 後面做連結。
Dynamic Hashing
前面提到了很多處理 overflow 的方法，但是這些方法都有一個問題，就是當放大 bucket 的時候，資料的搬動都需要花很多時間，這時候 user 便不能使用資料庫，因此發展出動態雜湊（Dynamic Hashing，or Extendible Hashing）的技術。
動態雜湊使用一組指向 bucket 的 pointer 的目錄（directory of pointers to buckets），目錄使用 h(k) 的部分 binary representation 來指向。如此只要 double directory 就可以較快速解決 overflow 的問題。
動態雜湊目錄的作法如下：
・目錄通常是一個大小為 2 的 d 次方的陣列，d 我們稱為 global depth，d 的值可以視需求增減。
・目錄的 entries 會指向 bucket，當 bucket 滿了的時候，只要將 bucket 分割成兩個，並重新分配資料，再更新目錄中 pointer 的資訊即可。
由於不是每次插入資料都會出現 overflow，也不是每次 overflow 都需要擴大目錄的長度，何時才需要擴大目錄長度的判斷方法如下：
Hashing Properties
根據上面的敘述，可以歸納出 Hashing 有以下幾個特性：
・當 bucket 裡面的 slot 數量不多時，執行插入、搜尋、刪除等動作時，可以在 O(1) 的時間複雜度內完成。
・leading header 不是一個好的 hash function，反過來說，一個好的 hash function 應該要有下面兩個特性：
1. 容易計算
2. 較少衝突（few collisions）以下介紹幾種常見的 hash function：
・Division：算式為 h(k) = k % D，D 通常為一個很大的質數。此 function 通常應用在 key 為非負數的整數時，計算出來的 bucket address 範圍會落在 0 到 D − 1 之間，通常這也代表 table 的 bucket 數量至少會是 D 的值。
・Mid-Square：把 key 平方之後再取其中幾個 bit 來計算 bucket address。如果使用了 r 個 bits，則代表 table 的大小為 2 的 r 次方。
・Folding：將 key 分割為幾個部分後再相加，即得到 key address。
・Digit Analysis：假設已經事先知道所有的 key，將每個 key 轉換為以 r 為基底的數字，再將分布最不平均的數字刪除，剩下的便拿來作為 hash 的結果。
The Secure Hash Algorithm（SHA）
經過這串編譯之後，SHA-1 的內狀態（internal state）就會保持在五個 32 bits，可以再根據鏈結反應得到最後的結果 hi。
Bloom Filters
Bloom Filters 是 hash function 變化型的應用，根據前面的敘述，我們知道 hash function 在計算時會發生碰撞，兩個 key 得到一樣的結果，但實際上不一定是同一筆資料；反過來說，當 h(k1) != h(k2) 的時候，我們就可以確定 k1 和 k2 不是同一筆資料，因此我們可以利用這個特性，來檢查模糊匹配（approximate set membership problem）。
先假設 k1 是我們要找的 member，k2 是新的資料，想要檢查新的資料是否已經存在，計算 hash 若發現結果不同，便可以肯定裡面沒有相同資料，當結果相同時，代表資料有可能已經存在，但如果多做幾次驗算，就可以降低 錯誤（false positive probability）發生，這是 Bloom Filters 一個很重要的應用。
Bloom Filters 在設計時要考慮：
・filter 的 bits size，通常越大越好，看記憶體能提供多大的容量
・hash function 的數量，如果太少，發生碰撞的機率就會提高，如果太多 filter 很快就會被填滿
・hash function 必須各自獨立，避免計算結果重複。
參考資料：
