分離連鎖法(separate chaining) external_link

別名:チェイン法、オープンハッシュ法(open hashing)


単一連結リスト(チェイン)を用いることで衝突を許容する手法である。

7Vrfc6M2EP5r/NgMv8GPiZPczfQ605l0pnePMpKN7jByQY5x//oKIwFCIsYY7GSaPDhoJYTY3e/b1YqZvdjkX1Kwjf4gEMUzy4D5zH6cWZZvu+y3EByEYF4K1imGpcisBS/4X8SFBpfuMESZNJASElO8lYUhSRIUUkkG0pTs5WErEstP3YI1UgQvIYhV6d8Y0qiUBpZfy78ivI7Ek02Pv98GiMH8TbIIQLJviOynmb1ICaHl1SZfoLjQndBLed9zR2+1sBQltM8NAV/HK4h3/OW+4eQXgkwW44zyVdKDePWU7BKIirvNmf2wjzBFL1sQFr17Zmsmi+gm5t0ZTcmvSkWFZEUS+sJnq9qlfdlK7YdXlFLMFH0f43XChJQUU65wHC9ITNLjGuzVamWFYTV/owd6S8/1+LwN+WJhsD8mV/XDVVY8GOUNEdfXF0Q2iKYHNoT3usJ23HlN0d7XruAYXBY13MD2uBBw91tXc9cWYhfcSB0WNhWDzSwvpvydJWN5/+yI6PgtO2r5ng0w3W1+VIXoZ1fr4j+AMEVZJuZjSymnLHvfcAVjsCuUpjddxTUut5PdspOtsZPpaezkjGAm31XUhSDjEN4kKY3ImiQgfqqlD7JC6zHfSIGCo9J+IkoPXGtgR4msZKas9PCd339s/Cgad65oPubNzsdD1YL3BS2yZhiDLMNhKXzGsZg63KWvFew7rZORXRoKkgw4M4N0jagg+lJW6OJNG6YoBhS/ynx7EW6C/wNujAlwU8WIq+DGG4AbyTffM4h64UaoX8KNcSvcWGqC8ImbfvHGuyJuHI2VLlFfM+NKSIKUZIsLL9GblC9Noxb3A6olr1xFl1dOo6chrHsx0eoA2cjZDYPn7DKU7b486qs0Or8Vi/qdJLqs6W4AqyqU+js6dNJpJV52UuwpUo3AtujZ5OtiX3+3BCzK3UES7jZHS7Q3ahCgYKXdqHlhgJar84zbHzuBzMSuhogtDZKCEZAUfCwkSakTyjH9Xuc6rPWj0VOnPUXjjKxnaELVC+VzFeViizwezPmtfxJ8xGZXwG/7T7koflftQkxf4NAYti0GZN3PMZ3Wcxyj5ZHljLV/Vu/Yy2Xn42R4ChedoLhS9hVkEZvheZeEFJPkLPKaPG0ciY5a9rM0gd3SFYzG4CPHGUBI72ND1cViPShnYMogmKPJJnZwq6TB1GWvLUhx+PwFlsxwfSI8c1kqmwfwUmvINIOYrpUa7AZDWMYpxCB/fFJpIE5cbF73YeY+FnMx42c8EHXlxu1gNQLAbNeVEGb6KsLmGoBZIwDM7JHbYQag/IOapwuFI5it2g23AlvTbO5EZrNHqgd2Rr1sC5K3At8xU2cvwjoNCCg4Hfl0M16jZjJijcRtWVxbW9Sl5qPUFucfNhROF/IcWw153s1CnljNaAWb6V3aC0679FQe7U1NYm+m7ucz2LVz9/PLESM4hH9LjvN0m7n3DaDghgASeeJnFnDLLMDRbIinywJ0H1C8b321Q4xOX5OpSxeRPxFy7Tz5qggZUsMeN0+GIIvqsvRIB+s+L4VNXRdWAlp7v9pRFx5QuvXHPve9Qb58TTLT1Wrarq7ztuYWjh+SiOvGBq7zkERy536+2vcM40SpRMgudGnPl42mHHWUa1dc+iQ2nOmwYU6Ljfb+YryTf+UDLB356z4kGXJgwJr118allutPtu2n/wA=

時間計算量

  • 登録、探索、削除の平均時間計算量: O(1+L)O(1+L)

LL :負荷率(キーの数/ハッシュ表のサイズ)

アルゴリズム

次のルールでインデックスを計算する手法である。

  1. 次式でインデックスを計算する。
    index=keymod<hash table size>index = key \mod \lt \text{hash table size} \gt

  2. インデックスを用いてハッシュ表からリストの取り出し、目的の情報を検索する。

ハッシュ表のサイズ

ハッシュ表のサイズは、次式を使い 負荷率Lが5〜20になる素数 にする。
※負荷率Lが連結リストの平均の長さとなる。

hash table size=nLwheren=the number of entries,L=Load factor.\begin{aligned} \text{hash table size} &= \frac{n}{L}\\ where&\\ n &= \text{the number of entries},\\ L &= \text{Load factor}.\\ \end{aligned}

ハッシュ表の再構築

連結リストが長くなると平均 O(1)O(1) の時間計算量を保証できなくなるため、
ある程度長くなったら表を再構築する必要がある。
チェイン法を採用しているRubyでは最大長が5を超えた時に再構築しているらしい。

時間計算量の算出

キーの数を nn、ハッシュ表のサイズを BB とすると、時間計算量は、

バケットの探索O(1)+連結リストの探索O(nB)=O(1+nB)=O(1+L)\begin{aligned} &\text{バケットの探索} O(1) + \text{連結リストの探索} O(\frac{n}{B})\\ &= O(1+\frac{n}{B})\\ &= O(1+L)\\ \end{aligned}

である。
従って、nn に対して BB が十分に大きければ時間計算量は O(1)O(1) となる。

🌏 Map

same layerlower layer