MIT 6.006 Introduction to Algorithms 10

10. Open Addressing, Cryptographic Hashing

4 min readMar 5, 2017

前述

前一堂課實作了 Dictionary，利用 Array + Chaining的方法，來避免 collision 的發生，但我們這堂會利用不同的方法：Open Addressing 來實作，這是將會是不一樣的方式來解決 collision。

總結

Open Addressing 的好處是你的 Table 不會是一堆指針（Chaining linked list），但是同樣的，你必須注意你的 Load Factor 是否太大，太大會使你的 operation cost 提升。

Hashing 好處多多，除了拿來實作 constant time operation，還可以拿來做密碼保護（ Cryptographic），防止密碼被駭入…

Open Addressing

先來簡介一下 Open Addressing 的特色：

No Chaining
#Slots m ≥ #Element N
Probing

他主要的特色是利用 probing來解決collision。

Probing
Hash function specifies order of slots to probe for a key (for insert/search/delete)

Probing Hash 是特別的 hash method，除了帶入key以外，還必須帶入一個數字（offset）當調整：

Probing Hash :probingHash(key,1) = 4
probingHash(key,2) = 2,
probingHash(key,3) = 9,
probingHash(key,4) = 13,
probingHash(key,5) = 1,... hash(key,m-1)

Probing Hash 依據你帶入不同的 offset，你可以得到不同的 hashing 結果。所以當你把 key 放入 slot 的時候發生 collision，你可以再一次的 hash（但帶入不同的條件 offset），你就可以得到新的結果。

舉個例子：

Insert

我們要 insert 參數至下面的 Array：

以左圖為範例：probingHash(586, 1) = 1
probingHash(133, 2) = 1
probingHash(264, 1) = 4
probingHash(481, 1) = 6
probingHash(496, 1) = 4  => fail，index 4 已經有 204 佔據著probingHash(496, 2) = 1  => fail，index 1 已經有 586 佔據著probingHash(496, 3) = 3  => success，空位

藉由不段的 probing，你的 index可以調整到有空位為止，這保證你每次 insert，都是放到空位中。

Probing Steps for Insert(k, v) ：
1. keep probing until an empty slot is found.
2. Insert item when found.

Search

Search的方法與 Insert 相似，你需要一直 probing ，直到你找到 key 為止。

舉個例子，你想要 Search for key = 496：

Search for "496" : probingHash(496, 1) = 4  => fail，發現 index 4 是 204 佔據
probingHash(496, 2) = 1 => fail，發現 index 1 是 586 佔據
probingHash(496, 3) = 3  => success，發現 index 3 是 496 佔據

經過三次 probing，你終於找到 key = 496 在 index = 3 的 slot。

當然有一種情況是找不到 key，比如說 search for key = 111：

probingHash(111, 1) = 7  => fail，empty slot found!

當你到一個空位，這就代表你的 Dictionary 根本沒有不存在這個 key。

Probing Steps for Search(k)：
1. As long as the slots encountered are occupied by key != k, Keep probing.
2. Keep probing until you either encounter k or found an empty slot.

Delete

如果是 delete，在找到 slot 並要刪除的時候，不是真的刪除 slot 的東西，而是用 flag 來取代他。

因為 Delete 是用 flag 來取代，所以我們需要對 Insert / Search 做調整，當你遇到 “delete me flag”時，你要做何處理：

Insert：treats “delete me flag” as none

Search：keep probing

Probing Steps for Delete(k)：
1. Keep probing until you either encounter k
2. Replace deleted item with “Delete Me” flag (Different from None)

為何使用 Delete Me Flag ，而不是直接砍掉變成 None？

用例子說明會比較快：

當你 delete key = 586，會把 index = 1 的 slot 清空。

這使你下一次在做搜尋的時候，就會出錯：

Search for key = 496 :probingHash(496, 1) = 4  => fail，發現 index 4 是 204 佔據
probingHash(496, 2) = 1 => fail，empty slot=> search stop by empty slot

當你 probing 到第二次的時候，你發現了一個 empty slot，這時 search 停止了，因為你以為 496 根本不存在 Dictionary，所以才會遇上 empty slot。

…但其實你錯了，496 存在 index = 3 的 slot！

這就是為什麼 Delete 的時候，我們必須要用 flag 而不是 none 來取代 slots！

Probing Strategies

怎樣的 Probing Hash Method 才是好的呢？

先介紹最簡單的開始介紹：

Linear Probing

linearProbeHash( k, i ) = ( hash( k ) + i ) mod m

你會發現 linear probing 有個特性，每次 probing 都只位移一個slot。這會造成你的 Array 資料會一群一群的聚集在一起（cluster）。

這讓你每次遇到 collision時，你必須浪費很多時間一個一個往下找，直到找到空位為止。這明顯的不是好事！

linearProbeHash(key, 1) occupied,
linearProbeHash(key, 2) occupied,
linearProbeHash(key, 3) occupied,...linearProbeHash(key, 57) none, Insert

Cluster
Consecutive groups of occupied slots which can growing longer

介紹另一種比較好的方式：

Double Hashing

利用兩個 Hashing method 同時 Hash

doubleHash(k, i) = ( h1(k) + i * h2(k) ) mod mif h2(k) is relatively prime to m  =>  permutation

Operation Cost for Open Addressing

到底 Open Addressing可以達到怎樣效率的operation呢？在證明 Cost 之前，我們一樣需要導入下面的假設：

Uniform Hashing Assumption

Each key is equally likely to have any one of the m! permutation as it’s probe sequence.

（假設我們的 Probing Hash 很有效率，他可以 Hash 到空位。並且每個空位的機率是一樣的。）

機率告訴我們，找到一個空位的機率 p 是

p = (m - n) / m 
  
  = 1 - loadFactor

Load Factor = n / m

所以當 insert 一個物件時，你需要嘗試 1 / p 次，才能找到空位：

expect number of trial = 1 / p                       = 1 / (1 - loadFactor)

所以我們可以得知 Insert Cost ：

Cost of Operation Insert ≤ 1 / ( 1 - loadFactor )

所以當你的 loadFactor 越大時，你的 cost 將會急劇增加。所以必須要小心，當 n 接近 m 時，就需要 re-size，建立新的 Table 來降低 load Factor

一般來說，當load Factor > 0.5時，Operation 效率就會變得很差。這時就需要 re-size，建立新的 Table 來降低 load Factor

目前沒有任何 Hash 的方法可以達到 Uniform Hashing Assumption，但是 Double Hashing 已經可以做到相近的結果

Cryptographic Hashes

hashing 的好處不是只有 Constant Time Operation，也常常使用在密碼儲存上。

登入你的 facebook，你需要輸入你的密碼，輸入之後，Server 會做比對驗證，但 Server 其實不是驗證你的密碼本身，而是驗證 hash 後的結果：

if hashPassword == hash(input) {
    logIn()
}else {
    fail()
}

因為 Server 其實沒有真正儲存你的密碼，而是儲存密碼的 Hash，這樣在駭客入侵的時候，他們就不會直接得到你的密碼，而是得到一堆亂碼，而且用這些亂碼也很難回推你的真正密碼。

如果對於加密有興趣，可以參考下面這部影片：

下一堂課我們將介紹數學相關的 Algorithm…

MIT 6.006 Introduction to Algorithms 11

前述

medium.com