分離連鎖法(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)
L :負荷率(キーの数/ハッシュ表のサイズ)
アルゴリズム
次のルールでインデックスを計算する手法である。
-
次式でインデックスを計算する。
index=keymod<hash table size> -
インデックスを用いてハッシュ表からリストの取り出し、目的の情報を検索する。
ハッシュ表のサイズ
ハッシュ表のサイズは、次式を使い 負荷率Lが5〜20になる素数 にする。
※負荷率Lが連結リストの平均の長さとなる。
ハッシュ表の再構築
連結リストが長くなると平均 O(1) の時間計算量を保証できなくなるため、
ある程度長くなったら表を再構築する必要がある。
チェイン法を採用しているRubyでは最大長が5を超えた時に再構築しているらしい。
時間計算量の算出
キーの数を n、ハッシュ表のサイズを B とすると、時間計算量は、
バケットの探索O(1)+連結リストの探索O(Bn)=O(1+Bn)=O(1+L)である。
従って、n に対して B が十分に大きければ時間計算量は O(1) となる。
🌏 Map
same layer | lower layer |
---|---|