Hashing

Size: px

Start display at page:

Download "Hashing"

婉黄
8 years ago
Views:

1 HASHING Michael Tsai 2012/05/29

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

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

4 概念 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: 所有可以放數櫃子資料數目

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

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

7 一些定義 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)

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

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

10 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 裡面

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

12 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

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

14 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 %m, h k %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)

15 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 的任一種排列組合出現的機率是一樣的

16 來做一些分析 ( 沒有推導 ) 在 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 ) 第三次有 α 2 機率要找 Worst case? 全部都連在一起, 全部都填滿了 O(n)

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

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

19 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!

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

21 一些 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

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

23 一些 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)

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

25 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

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

27 例子 k h(k) A A B B C C C C h(k,i)=bits 0-i of h(k) Example: h(a0,1)=0 h(a1,3)=001=1 h(b1,4)=1001=9

28 Dynamic hashing using directories directory depth= number of bits of the index of the hash table A0, B0 A1, B1 C2 C3 Insert C5 h(c5, 2)=01=1 C5, overflow we increase d by until not all h(k,d) of the keys in the cell are the same A0, B0 A1, B1 動腦時間 : 如果原本的要加入 C1 呢? 如果第二步驟後加入 A4 呢? 答案 : Horowitz p C2 C3 C5 k h(k) A A B B C C C C

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

30 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

31 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) A A B B C C C C

32 Today s Reading Assignment Cormen ch 11 (11.1, 11.2, 11.3 except , 11.4) Horowitz p (posted on the course web site)

Microsoft PowerPoint - lecture14.pptx

Microsoft PowerPoint - lecture14.pptx PRIORITY QUEUES Michael Tsai 00//8 Outline Dynamic hashing Priority Queue 的種類 DEPQ 的用途 Leftist Tree Binomial Heaps Dynamic hashing 觀察 : 當 n/b 比較大以後, O() 就開始崩壞 ( 往 O(n) 方向移動 ) 應變 : 所以要隨時觀察 n/b, 當它大過某一個