概要
概要
平均的には高速に探索できますが、衝突が起きると工夫が必要です。教材では衝突解決の考え方まで見せます。
探索 / Hash Table（ハッシュテーブル）
平均的には高速に探索できますが、衝突が起きると工夫が必要です。教材では衝突解決の考え方まで見せます。
目次
このページでわかること
概要
平均的には高速に探索できますが、衝突が起きると工夫が必要です。教材では衝突解決の考え方まで見せます。
考え方
index = hash(key) % tableSize
if bucket occupied then resolve collision
store or search in bucket要点
O(1)
O(n)
良いハッシュ
衝突
補足
狙ったバケットへ直接飛べるからです。
同じ場所に複数キーが来ると連鎖や再配置が必要です。
衝突前後の見た目の変化を出すと理解しやすいです。
動きで確認
ここでは「何を比較するか」を見ながら、上で読んだ内容を動きと結びつけます。
次に見る
比較すると違いがわかりやすいページを先に置いています。