Hashing 基礎介紹

發表於 更新於 分類於 閱讀次數： 閱讀次數： Disqus： 文章字數： 6.1k 所需閱讀時間 ≈ 6 分鐘
DS 筆記 : Hashing 基礎介紹

阿，終於紀錄了一下 hashing
在資工所算是必考的東西，希望能用這篇做一個總複習。

說是基礎介紹，其實也沒到這麼淺；
但要說深，肯定沒多深 XD

基本概念

  • hashing 就一個神奇的 function
    給他資料本身，他可以透過 function 計算 出 index 是多少
    沒錯，如果把計算實間當作 const，資料數量很多，這個成本就會接近 O(1)
  • 但 ... 總會有例外。實際上，我們很難去找到一個 function 可以完美的 1-to-1。
    如果是真的完美的 1-to-1，那我們稱之為 Perfect function

  • 也就是說，很可能發生 a ≠ b 但 f(a) = f(b)，對到同一個值 (同一個 index)。
    我們稱此現象叫做 collision (碰撞)
    collision 發生

  • 每個計算完後我們會得到 index，而我們的 table 中，一個 index 就是對一個 bucket
    而 ... 一個 bucket 裡面其實是可以不只放一個資料的，我們可以在一個 bucket 放很多 slot

    • 拿計組來比喻的話，Cache 中的 Set 就像是 bucket，而 Block 就像是 slot
      宛如一個 Set 可以放很多 block，Bucket 也是。
    • 所以，假如只看 Hash Table 本體，可以儲存的 data 量 = bucket數量*slot 數量

  • 如果放一放，結果 slot 也滿了 → 這叫做 overflow

  • 專有名詞 :

    • key : 拿來當索引的東西，因為索引不一定是數字，可能是字串。
      • 就是我們熟知的 index
    • T = |U| : indentiter 總數，當做是 key (index) 的 range 就好
      • 比如我的 key 是英文字母，那 T = 26
    • n =|K| :  所有要存入的 pair 的數目 (準備要使用的資料量)
    • Key  density (indentiter density) :  n / T，預計使用除以所有可能，合理。
    • **Loading  density (load  factor) :  n / (bucket*slot) = α **
      • α 越大 → 代表利用度越高。但 collision 機率也會提升。

Hashing Function 如何設計 ?

  • 前面提到，設計 Perfect function 其實是一件很難的事情。
    除此之外，我們要保握幾個原則 :

    1. 計算要簡單
    • 我們希望可以 O(1)
    1. Collision 要少
    • 我們希望接觸到每個 bucket 機率都盡量一樣
    1. 減少 **Clustering 現象 **
    • Load 平均

  • 實際情況中，function 算出來除了前面提到的，很難 1-to-1 之外，假如今天放大 slot 數量
    那就沒問題了吧 ?
    並沒有。

    也許你的算法會有偏頗，使得導致計算結果不夠分散 (有些 index 很少被碰到)
    這就是 **clustering 現象 (群聚現象)**。

  • 以下介紹一些常見的 Hashing function 類型

    • Division :  h(k)=k%D
    • Mid-square : 平方後取中間幾個位數
    • Folding addition : 切字串，加起來，又分 Shift 和 Boundary
    • Digit analysis : 從字串中分析過後，決定拿某幾位數

Division

  • h(k)= k % D

  • 舉例 : D = 7，把所有 input 都 mod 7 得到的就是 key。

  • 但是，隨便亂挑可能會很慘 ... 根據 Knuth 大師 :

    • D 最好是質數
    • D 如果可以整除 r^k ± a 就可能會狂撞 ... ( D ∤ r^k ± a 會比較好 )

      r 是基底，k 與 a 是很小的數 (實際上這定理 r k a 例子我也不太清楚)

  • 不過，至少有個例子是肯定會出問題的 : D = 2^t, t is a integer.
    由於 Hash table 大小高機率會是 2^n 的大小 (比較方便)
    所以如果每次都 mod 2^t ... 我們可以觀察得知就只是二進位的後面幾位在變而已

Mid-square

  • data 的值平方後，取中間幾位數當作 hashing address (key)
  • 寫成式子的話大概是這樣
    • 取 ( i+r-1 - i )+1= r 個數字，故 得到的通常是 0~2^r-1 (二進制)
    • 因此，通常 bucket 數量為 2^r (這樣就每個可能都能放進去了)
  • 舉例 : 8125 → 平方 = 66015625 → 十進制取 2~4 位 = 156

Folding addition

  • 把 data 值切割成幾個同樣長度片段，再將這些片段相加。
  • 但是相加的方式我們可以再做一點變化
    假設我們的 k 是 12320324111220
    • shift folding : 普通的相加普通的 mod
      {123,  203,  241,  112,  20}
      h(k)=(123+203+241+112+20)%1000=699
    • folding  at  the  boundaries : 偶數片段 inverse
      {123, 302, 241, 211, 20}
      h(k)=(123+302+241+211+20)%1000=897

Digit analysis

  • 假設先知道所有的 key，可以分析不同位數的分布情況來提取 key

  • 舉例 :
    01234567 <- 第幾位，方便解釋

    23211107
    23511407
    23311509
    23410208
    由上面可分析得到，從左數來第 2, 5, 7 位 這幾個位置在每個數裡面會比較不一樣
    假如果們都只挑 0, 1, 3 位，那每個數字都會得到 "231" 這個結果 ... 豈不無差異性

Multiplication Method

  • 比較少地方提到，這邊先貼原文

  • 實際情況中，無法預先得知「Key的範圍」以及「在該範圍內Key的分佈情形」
    這個方法就會可能比較好。

  • The functions take the form h(k) = ⌊m(kA mod 1)⌋
    where 0 < A < 1 and (kA mod 1) refers to the fractional part of kA.

  • Since 0 < (kA mod 1) < 1, the range of h(k) is from 0 to m. The advantage of the multiplication method is it works equally well with any size m. A should be chosen carefully. Rational numbers should not be chosen for A (why?).
    An example of a good choice for A is ((根號5)-1)/2 (黃金比例)

Collision, Overflow 的處理方法

  • 我們 Bucket 內的 slot 也不是無限大，總會有放滿的時候。
    如果我們再放一個進去 ... 那就會產生 Overflow
  • 不同的處理方式也會衍生不同的問題，以下將簡介幾種方式 :
    • Open addressing  
      • Linear Probing
      • Quadratic Probing
      • Double Hashing
    • Chaining
    • Rehashing

Linear Probing

  • 假設 Table 叫做 T，假設我們已經算出了 h(k) 就是我們的 index ! mod
    結果 T[ h(k)%m ] 已經有人了 QQ ( m 是 bucket 數量)
    那我們就會 T[ (h(k)+1)%m ],  T[ (h(k)+2)%m ],  … 這樣找下去
    ... 如果繞了一圈，那代表 load facor 已經 = 1 了，可能要擴大 ...

  • 公式 : h(k, i) = (h(k) + i) mod m

  • 只有 m 種 probing  sequence (畢竟變化就是 m 之內 ...)

  • 優點 : 很好實做，也不需要用記憶體來存pointer，而且空間利用度很好。

  • 缺點 :

    • 找 overflow 出去的格子需要花額外的時間，已經非 O(1) 了
    • 可能發生 **Clustering 現象 ** (群聚現象、集結現象)
      • 講個極端的，所有 hashing function 算出來剛好都打到 0 這個 index
        那不就得全部都從 0 開始找，於是第二個進來的找到了 1，第三個找到了 2 ...
        於是，假設有 100 格，進來了 20個，全都集中在 1~20，非常不平均。
    • Linear Probing 發生的 Clustering 叫做 Primary Clustering

  • insert example

Quadratic Probing

  • 公式 : h(k, i) = (h(k) + c1*i + c2*i^2 ) mod m，i 從 0 開始遞增
    其實看過上一個例子之後，這個應該比較能接受一點吧 ?
    比起 Linear Probing，Quadratic Probing 多了可以調整 c1,
    而且再多加一個 i^2，讓 next target bucket 更有變化。

  • 不過通常，比較簡單的例子介紹會把 c1 = 0，c2 = 1
    也就是 h(k, i) = (h(k) + i^2 ) mod m
    舉例 : h(k) = 3，3 已經有東西了，那就找 3+1=4，4 也有東西的話再找 3+4=7 ... 。

  • 如果 m = 2^n，那 c1 = c2 = 1/2，可以讓找的次序大概長這樣 :
    h(k), h(k)+1, h(k)+3, h(k)+6, h(k)+10, ... (容許我少寫 mod m)

  • 跟 Linear 一樣，只有 m 種 probing  sequence。(由一開始的 h(k) 決定)

  • 用這方法，可以讓 Clustering 稍為改善一點，但是還是有一種可能 ...
    就是一堆 key 剛好打到同個 h(k)，那就還是得一直找下去 (像 Linear 提到的極端例子)
    我們稱之為 Secondary Clustering

Double  hashing

  • 阿，人家 Quadratic Probing 都已經弄出後變二次式的變化了
    所以怎麼樣才可能讓 h(k) 加上一個特別的數，不會有 Secondary Clustering ?
    ... how about make another hashing function ?

  • 公式 : h(k, i) = (h1(k) + i*h2(k)) mod m 就此誕生 !

  • 舉例 : h1(k) = k % m, h2(k) = 1 + (k % (m-1))
    k = 123456, m = 701, h1(k) = 80, h2(k) = 257
    Sequence : T[80], T[80+257], T[80+2*257] ...

  • h2(k) 的設計通常會是 h2(k) = P - ( k % P )，P 是質數
    h2(k) 存在的意義就是 "offset"，探測的距離，畢竟之後要乘上 i，每次都會用這個基準跳

  • 即使 h1(k1) = h1(k2)，但總不會 h2(k1) 也等於 h2(k2) 吧 ? (機率比較小)
    因此 probing sequence 有 m^2 種

  • 此方法是最接近 Uniform hashing 的方法 (probing sequence 出現的機率是一樣的)

    • uniform 情況下，找失敗的機率是 1+ α + α^2 + α^3 + ... = 1/(1-α)
      因為 α 是 load factor，代表座位已占率，有這樣的機率會找到已經佔有的 slot
      成功 = (1/α)*ln( 1/(1-α) )
      • Cormen p.274~276
    • Worst case ? O(n)，全都填滿了

Chaining

  • 之前那些方法，插入還好，但如果是要 search ?
    尋找過程中，一直算 hash 一直找 ... 也許效率挺低落的
    於是提出另一個想法 : 在 Bucket 後面接 Linked List !
    • 想當然，同一條 Linked List 上面的每位，所計算得到的 h(k) 都是一樣的

Chaining

  • Worst  case : 全部都塞在同一個 Bucket 下面的 Linked List，O(n)
    • 不過 Linked List 可以改乘 BST，這樣就能 O(logn) 惹
  • 平均一個 chain 有 n/m 個 pair  ( α 個 pair )
    = 也是如果找不到的話， 平均需要比較的次數
  • 找不到 : 加上hash本身要花的時間，總共為 Θ( 1 + α )
  • 找的到 : 加上hash本身要花的時間，總共為 1+ α/2 - α/2n = 也是 Θ( 1 + α )
    • 原因我也不清楚，有興趣請找 Cormen p.260
  • n = data 的量，m = bucket 數量，由於 n = O(m)，α = n/m = O(m)/m = O(1)
    所以說如果 n 為 m 的某個比例，在 chain 裡面找的時間 = Θ( 1 + α ) = Constant time !

Rehashing

  • hashing again.

  • load factor 增加到某個 pre-defined value (default value of load factor is 0.75)
    也許就該考慮重新做 hashing function 了。

    • load factor 太大代表 bucket 使用量有點高，格子快滿了 !

  • array 大小會被增大 ... 通常是 double，然後把所有資料存到這個兩倍大的 array 之中。

  • 阿，不過這樣 ... 某個傢伙在被 insert 的時候剛好踩到某個探測值
    然後系統說要 rehashing ... 那不就要等超久 ?
    所以下個議題，Dynamic hashing !

Dynamic  hashing

  • 又稱 extendible hashing

  • 觀察 :  當 n/m 比較大以後,  O(1) 就開始崩壞 (往O(n)方向移動)

  • 如 Rehashing 部分所提，重建的時候實在花太久了。
    ... 哦，所以我先做一點就好，沒必要一次全部做完吧 ?

  • 假設我們有這些 data (只須看 k 與對應的 h(k) 就好)

  • 於是我們這樣看
    C5 對到 1，但是 1 overflow，所以 copy 兩倍，放在新的格子之中 (同樣也是 餘1 系列)

  • 或是想成他是個會想下延伸的 tree

  • 也就是說，其實舊的東西我們都不會碰到，只要處理(新增) overflow 的部份
    → 優化 : 那 buckets 都可以放硬碟了，反正 append 也是弄在記憶體

    • search 只要讀一次硬碟
    • insert 也只讀一次硬碟，沒 overflow 就寫 1 次，
      有 overflow 就在那個 node 下開兩格，把其中一格填進去
    • hash table 要變兩倍大的時候，改的是 memory 的 directory，不用碰硬碟

  • 兩個主要的問題 :

    • bits 的長度 影響 Access time
    • 如果 skewed distribution 就 GG 了

  • 如何避免 ?

    • To avoid the skewed distribution of identifiers, a hash function is used.
    • To avoid the long search down the trie, the trie is mapped to a directory.

  • A directory is a table of page pointer.

    • In case k bits are needed to distinguish the identifiers, the directory has 2 k entries indexed 0, 1, 2, 3, …, 2^k -1.

  • Directoryless Dynamic hashing (Horowitz p. 410-­‐416)

Ref

wiki
教材
SecondRound
C. Y. Tang and J. S. Roger Jang
Hyoung-Kee Choi
Michael Tsai PTT
TKB 筆記

End
-----------------------------------

2020.01.16
5