女性向けエンジニアスクール
3秒でわかる
キーを計算して置き場所を直接割り出すデータ構造。件数が増えても取り出す速さがほぼ変わらず、辞書型や連想配列の内部で使われています。
もう少し詳しく
どういうものか
ハッシュテーブルは、キーをハッシュ関数に通して得た数値を配列の添字として使い、その位置に値を置くデータ構造です。探すときも同じ計算をして位置を割り出すので、先頭から順に見ていく必要がありません。平均的な計算量は追加も取得も O(1) で、要素が 10 件でも 100 万件でも所要時間はほぼ変わりません。
Python の dict、Java の HashMap、JavaScript の Map と Object は、いずれもこの構造を土台にしています。普段何気なく使っている辞書型の速さは、この仕組みによるものです。
なぜ必要か
配列から特定の値を探すには先頭から順に比べるしかなく、件数に比例して時間がかかります。会員 100 万人から ID で 1 人を引くたびに 100 万回の比較が走るのでは、実用になりません。ハッシュテーブルは、比較の回数を件数と切り離します。
具体例
stock = {}
stock["apple"] = 12
stock["banana"] = 5
print(stock["apple"]) # 12
print("melon" in stock) # False
print(stock.get("melon", 0)) # 0
# ハッシュ値そのものを見てみる
print(hash("apple") % 8) # 配置先の候補になる添字キーには変更できない値しか使えません。リストをキーにしようとすると TypeError になります。途中で中身が変わると、置いた場所と探しに行く場所がずれるためです。
つまずきやすいところ
異なるキーが同じ添字に割り当てられることがあり、これを衝突と呼びます。衝突は避けられないので、同じ位置に連結リストを持たせる方式などで対処します。衝突が極端に多いと、全部が 1 か所に集まって線形探索と変わらない速さまで落ちます。
もう 1 つは、格納の順序に意味を求めてしまうことです。位置は計算結果で決まるため、追加した順や大小の順にはなりません。Python 3.7 以降の dict は挿入順を保ちますが、これは実装上の保証であって、ハッシュテーブル一般の性質ではありません。順序が必要なら、取り出してから並べ替えます。
似た用語との違い
| 構造 | 取得 | 順序 |
|---|---|---|
| 配列 | 添字なら O(1)、値の検索は O(n) | 並び順を保つ |
| ハッシュテーブル | 平均 O(1) | 保証しない |
| 二分探索木 | O(log n) | 大小の順に並ぶ |
範囲指定で取り出したい場合は、ハッシュテーブルより木構造が向きます。
覚え方
図書館の書架番号を、本の題名から計算で出すようなものです。目録を端から読む必要がなくなります。
