Hashing

HASHING Michael Tsai 2012/05/29

有沒有一種天方夜壇 Insert (key, data) Search Delete =O(1) 神秘的資料結構 Hint: 以空間換取時間

概念 很多很多有編號的櫃子 問 : 菜瓜布 的資料去哪找? ( 菜瓜布, 資料 ) 管理員 管理員 : 菜瓜布 對應到 1028 號櫃子 1028 如果箱子夠多, 則花費在一個箱子裡面尋找的時間 =O(1)

概念 Hash table 很多很多有編號的櫃子 問 : 菜瓜布 的資料去哪找? Hash function: h(k) 管理員 管理員 : 菜瓜布 對應到 1028 號櫃子 key: 拿來當索引的東西例如 : 菜瓜布 U : 所有可能的 key 的數目 n= K : 所有要存入的 pair 的數目 1028 Key density: n/t Load density (load factor): n/sm 櫃子數目 : m 每個位子可以放的資料數 :s sm: 所有可以放數櫃子資料數目

概念 : Hash Table U: 所有可能出現的各種 key 很多很多有編號的櫃子 K: 結果真的出現在 input 的各種 key 把 key 做一次轉換以後得到 櫃子的編號 櫃子數目變少 有可能有兩個 key 對應到同一個櫃子

概念 : Direct-address Table U: 所有可能出現的各種 key 很多很多有編號的櫃子 K: 結果真的出現在 input 的各種 key 裡面存資料 如果 K U, 櫃子就浪費很多空間

一些定義 h(k): hash function hash function 把 key 對應到一個數值 ( 通常為櫃子編號 ) 有可能把不同的 key 對應到同一個數值 ( 但是沒關係 ) 如果 h k 1 = h k 2, 則 k 1, k 2 are synonyms with respect to h. 最簡單的 hash function: k%m (k mod m) collision: 要把資料存進某櫃子的時候, 該櫃子已經有東西了 overflow: 要把資料存進某櫃子的時候, 該櫃子已經滿了 if s==1, 則每次 collision 都會造成 overflow ( 通常 s==1)

為什麼是 O(1) 當沒有 overflow 的時候 : 計算 hash function 的時間 : O(1) 進到某一個櫃子去 insert, delete, search 的時間都是 O(1) worst case 為尋找 s 個空間的時間 : 固定 所以為 O(1) 剩下的問題 : (1) 當 collision 發生的時候怎麼處理? (2) 怎麼 implement 一個好的 hash function?

Collision 處理 注意 : 要確保能夠下次也能找到同一個地方! 兩種常用處理 collision 的方法 : (1) Open addressing (2) Chaining Full! Full! Find another empty cabinet 多出來的吊在下面

Open addressing Linear probing 有好幾種方法 : (1) Linear probing T[(h(k)+1)%m], T[(h(k)+2)%m], Insert 的時候順著往下找 ( 找的動作又叫做 probe): 一直找到 1. 有空位 填入 2. 回到原來的位置 h(k) 了, 則沒有空位 可能要擴大. (load factor 永遠小於 1) Search 的時候, 一樣是從 T[h(k)] 開始往下找, 一直找到 1. 有空位 k 不在 table 裡 2. 找到了, k 在 T[(h(k)+j)%m] 的位置 3. 回到原本的位置 h(k) 了, k 不在 table 裡面

Open addressing 好處 : 利用 hash table 裡面沒有儲存東西的空間 不用使用記憶體來存 pointer, 省下來的記憶體可以開更大的 hash table 壞處 : 尋找 overflow 出去的 element 需要花額外的時間 ( 不是 O(1) 了 ) 讓在櫃子裏面的 key 容易集結 (clustering) 在一起 平均尋找時間更長

Open addressing General Form 我們把 hash function h 變成以下的形式 : h: U 0,1,, m 1 也就是我們 probe 的順序為 (probing sequence) h k, 0, h k, 1, h k, 2, h k, m 1 以上為 0,1,2,, m 1 的排列組合 所以 Linear probing 的可以寫成 : h(k,i)=(h (k)+i))%m h (k) 是原本的 hash function Linear probing 總共只有 m 種 probing sequence

Open addressing Linear probing Input sequence of keys: {8,16,18,5,31,15} Primary clustering: 某些 open addressing 的 probing 方法會產生一長串填滿的格子 [0] [1] 8 8 8 8 8 8 [2] 16 16 16 16 16 [3] 31 31 [4] 18 18 18 18 [5] 5 5 5 [6] 15

Open addressing Quadratic probing h k, i = h k + c 1 i + c 2 i 2 %m, c 1, c 2 為正常數 例 1: 我們可以用 h k, i = h k + i 2 %m h k %m, h k + 1 2 %m, h k + 2 2 %m,, h k + m 1 2 %m 例 2: 如果 m = 2 n, 則我們可以用 h k, i = h k + i 2 + i2 2 %m h k %m, h k + 1 %m, h k + 3 %m, h k + 6 %m, h k + 10 %m, 用這些方法可以使得 clustering 的現象較為減輕 : Secondary Clustering 只有當一開始的 hash function 產生一樣的位置才會造成一樣的 probing sequence h k 1, 0 == h(k 2, 0) implies h k 1, i == h(k 2, i) 和 linear probing 一樣, 只有 m 種 probing sequence ( 開始的 h (k) 決定 sequence)

Open addressing Double hashing h k, i = h 1 k + i h 2 k %m 為 open addressing 最好的方法之一 例子 : h 1 k = k % m, h 2 k = 1 + k% m 1 如果 k=123456, m=701, h 1 k = 80, h 2 k = 257 一開始找 T[80], 後面每隔 257 格找一次 關鍵 : 即使 h 1 k 1 == h 1 (k 2 ), h 2 k 1 == h 2 (k 2 ) 應該不成立 因此 probing sequence 有 m 2 種! ( 通常須要求 m = 2 n ) Double hashing 是最接近 uniform hashing 的方法 Uniform hashing: 任何 probing sequence 出現的機率是一樣的 也就是 0,1,2,, m 1 的任一種排列組合出現的機率是一樣的

來做一些分析 ( 沒有推導 ) 在 Uniform Hashing 的假設下 : Expected number of probes: 尋找一個 key 時平均所需要找 ( 比較 ) 的 key 個數 因為其他的 operation 都只需要 O(1), 所以這個動作決定了 search 的 time complexity α: load factor= n/m < 1 第一次一定要找 第二次有 α 機率要找 失敗 ( 找到空位 ): 成功 : 1 α ln 1 1 α 1 1 α = 1 + α + α2 + α 3 + ( 詳細的證明參見 Cormen p.274-276) 第三次有 α 2 機率要找 Worst case? 全部都連在一起, 全部都填滿了 O(n)

Chaining 之前的方法的缺點? 尋找過程中, 需多其他的資料的 hash 值和現在要找的 key k 的 hash 值根本就不一樣 有點冤枉 所以採取 掛勾 的方法 每個櫃子是一個 linked list 搜尋的時候只會找掛在下面的 (h(k) 都一樣 ) Not here Not here Not here 結果在這邊

Chaining Worst case Worst case: 全部都塞在同一個櫃子下面的 linked list time complexity 這樣是? O(n) 小小的進步 : 底下可以用 binary search tree ( 之後有 balanced 版 ) 可以進步到 O log n

Chaining - Expected performance 每個櫃子的 chain 上面平均有幾個 pair? n: 總共存入的資料 pair 數目 m: 櫃子數目 所以假設使用 simple uniform hashing 的話 也就是存到每個櫃子的機率相等 平均一個 chain 有 n/m 個 pair (α 個 pair) 這也是如果找不到的話, 平均需要比較的次數 加上 hash 本身要花的時間, 總共為 Θ 1 + α 如果是找得到的話, 平均需要比較的次數為 1 + α 2 α 2n 加上 hash 本身要花的時間, 總共仍為 Θ 1 + α ( 詳細證明可見 Cormen p.260) 因此總體來說, 只要 n = O m, α = n = O m = O(1) m m n 為 m 的一個比例時, 總時間可為 constant time!

Hash function 先要知道的事情 : 不可能讓所有 key 都 map 到不同的櫃子 ( 因為 K 遠大於櫃子數目 ) 目標 : (1) 希望隨便取一個 key, 則平均來說它存到任何一個櫃子的機率都是 1/m (m 為櫃子數目 ) ( 都是一樣的 ) (2) 計算 hash function 的時間為 O(1) 當 (1) 符合時, 此 hash function 稱為 simple uniform hashing (hash function)

一些 hash function 的例子 複習 : h(k) 把 k 轉成另外一個數字 ( 櫃子編號 ) (1) Division: h(k)=k%d 則結果為 0 ~ D-1 通常我們可以把 D 設為櫃子數目 (2) Mid-square: h(k)=bits i,i+r 1 (k 2 ) 則結果為 0 ~ 2 r 1, 所以通常櫃子數目為 2 r

一些 hash function 的例子 (3) shift folding 用例子解釋 : k=12320324111220 每隔幾位數切一份. 例如, 三位數 : ( 櫃子有 1000 個 ) {123, 203, 241, 112, 20} h(k)=(123+203+241+112+20)%1000=699 (4)folding at the boundaries {123,302,241,211,20} h(k)=(123+302+241+211+20)%1000=897

一些 hash function 的例子 (5) digit analysis 假設先知道所有的 key 了 此時就可以尋找一個比較好的 hash function 假設 k 有 5 位數, 我們有 100 個櫃子 則需要把 5 位數轉換成 2 位數 則我們可以每次選某一位數來分類成 10 組 最不平均的 3 個位數可以刪掉 ( 記得 : 最好可以使得分到某櫃子的機率都相等 ) (6) Multiplication Method: 取 0<A<1, then h(k)= m (ka % 1) ( 參看 Cormen p.264)

Key 是 string 怎麼辦? 轉成數字! ( 然後再使用 hash function) 可不可以把不同字串轉成一樣數字? 答 : 可以! 反正 hash function 一樣已經會把不同 key 轉成一樣的櫃子號碼了 方法 : (1) 把所有字串的 character( 數字 ) 加起來, 進位的通通丟掉. ( 類似 checksum) (2) 把所有字串的 character ( 數字 ) 分別往左位移 i 格, i 為該 character 在字串中的位置, 然後通通加起來. 舉例

Dynamic hashing 觀察 : 當 n/m 比較大以後, O(1) 就開始崩壞 ( 往 O(n) 方向移動 ) 應變 : 所以要隨時觀察 n/m, 當它大過某一個 threshold 時就把 hash table 變大 觀察 : 把 hash table 變大的時候, 需要把小 hash table 的東西通通倒出來, 算出每一個 pair 在大 hash table 的位置 然後重新放進大 hash table 有個可憐鬼做 insert 正好碰到應該 hash table rebuild 的時候, 他就會等非常非常久. T_T

Dynamic hashing 目標 : 重建的時候, 不要一次把所以重建的事情都做完 或許, 留一些之後慢慢做? 每個 operation 的時間都要合理 又叫做 extendible hashing

例子 k h(k) A0 100 000 A1 100 001 B0 101 000 B1 101 001 C1 110 001 C2 110 010 C3 110 011 C5 110 101 h(k,i)=bits 0-i of h(k) Example: h(a0,1)=0 h(a1,3)=001=1 h(b1,4)=1001=9

Dynamic hashing using directories directory depth= number of bits of the index of the hash table 00 01 10 11 A0, B0 A1, B1 C2 C3 Insert C5 h(c5, 2)=01=1 C5, overflow 000 001 010 011 100 101 110 we increase d by 1 111 until not all h(k,d) of the keys in the cell are the same A0, B0 A1, B1 動腦時間 : 如果原本的要加入 C1 呢? 如果第二步驟後加入 A4 呢? 答案 : Horowitz p. 412-413 C2 C3 C5 k h(k) A0 100 000 A1 100 001 B0 101 000 B1 101 001 C1 110 001 C2 110 010 C3 110 011 C5 110 101

Dynamic hashing using directories 為什麼比較快? 只需要處理 overflow 的櫃子 如果把 directory 放在記憶體, 而櫃子資料放在硬碟 則 search 只需要讀一次硬碟 insert 最多需要讀一次硬碟 ( 讀資料, 發現 overflow 了 ), 寫兩次硬碟 ( 寫兩個新的櫃子 ) 當要把 hash table 變兩倍大時, 不需要碰硬碟 ( 只有改 directory)

Directoryless Dynamic hashing 假設 hash table 很大, 但是我們不想一開始就整個開來用 (initialization 會花很大 ) 用兩個變數來控制的 hash table 大小 : r, q hash table 開啟的地方為 0, 2 r + q 1 之間 q~2 r 1 之間使用 h(k,r) 0~q-1 及 2 r ~2 r + q 1 之間使用 h(k,r+1) r=2, q=2

Directoryless Dynamic hashing 每次輸入的時候, 如果現在這個櫃子滿了 則開一個新的櫃子 : 2 r + q 原本 q 櫃子裡面的東西用 h(k,r+1) 分到 q 和 2 r + q 兩櫃子裡 注意有可能還是沒有解決問題 多出來的暫時用 chain 掛在櫃子下面 000 A0 00 B4, A0 01 A1, B5 C5 01 A1, B5 insert C5, full 10 C2 10 C2 11 C3 11 C3 100 B4 r=2, q=0 r=2, q=1 問 : 再加入 C1 呢? (Horowitz p.415) k h(k) A0 100 000 A1 100 001 B4 101 100 B5 101 101 C1 110 001 C2 110 010 C3 110 011 C5 110 101

Today s Reading Assignment Cormen ch 11 (11.1, 11.2, 11.3 except 11.3.3, 11.4) Horowitz p. 410-416 (posted on the course web site)