ハッシュテーブル

キーと値のペアを高速に検索・挿入・削除するデータ構造。

ハッシュテーブル
キーと値のペアを格納するデータ構造。ハッシュ関数を使用してキーを配列のインデックスにマッピングする。
ハッシュ関数
キーを配列のインデックスに変換する関数。
衝突
異なるキーが同じハッシュ値を持つ現象。
チェイン法
衝突を解決する方法の1つ。同じインデックスに複数の要素をチェイン状に格納する。
オープンアドレッシング
衝突を解決する方法の1つ。衝突した場合、次の空いているスロットを探す。
負荷係数
ハッシュテーブルの満た度を表す指標。要素数 / 配列サイズで計算される。

ハッシュテーブル

図書館の索引

ハッシュテーブルは「図書館の索引」のようなもの。索引には、本のタイトルと棚番号が記載されています。ある本を探すとき、索引で棚番号を確認して、すぐに本棚へ移動します。ただし、異なるタイトルが同じ棚番号になる場合（衝突）、同じ棚に複数の本を並べる必要があります。

なぜハッシュテーブルが必要か？

ハッシュテーブルは、キーと値のペアを格納するためのデータ構造です。高速な検索、挿入、削除が可能で、平均的な計算量はO(1)です。特に、大量のデータを高速に検索する必要がある場合に適しています。

いつ使うか？

  • キーに基づいた高速な検索が必要な場合
  • データの挿入・削除が頻繁な場合
  • 重複排除が必要な場合
  • キャッシュの実装が必要な場合

実践テクニック

良いハッシュ関数を選ぶ

ハッシュ関数の品質は、ハッシュテーブルのパフォーマンスに大きく影響します。良いハッシュ関数は、キーを均等に分散させ、衝突を最小化します。Pythonの組み込み `hash()` 関数は、多くのケースで適切に動作しますが、カスタムハッシュ関数を使う場合は、これらの特性を考慮する必要があります。

負荷係数を管理する

負荷係数が高くなると、衝突の頻度が増加し、パフォーマンスが低下します。一般的に、負荷係数が0.7を超えたら、ハッシュテーブルのサイズを拡張することを検討してください。Pythonの `dict` は、自動的にサイズを調整しますが、カスタム実装ではこの管理が必要です。

衝突解決戦略を選ぶ

衝突の解決には、主に2つの戦略があります。チェイン法は、同じインデックスに複数の要素をチェイン状に格納します。オープンアドレッシングは、次の空いているスロットを探します。チェイン法は実装が簡単で、オープンアドレッシングはメモリ効率が良い傾向があります。

イミュータブルキーを避ける

イミュータブル（変更可能）なオブジェクトをキーとして使うと、ハッシュ値が変わる可能性があります。これは、データが見つからなくなる原因になります。キーには、イミュータブルなオブジェクト（文字列、数値、タプルなど）を使うことを推奨します。

Hash Table Operations
# ハッシュテーブルの基本操作
hash_table = {}


# 要素の追加
hash_table["apple"] = 1
hash_table["banana"] = 2
hash_table["orange"] = 3


# 要素の取得
print(hash_table["apple"])  # 1


# 要素の削除
del hash_table["banana"]


# キーの存在確認
if "apple" in hash_table:
    print("Found")

ハッシュ関数

ハッシュ関数は、キーを配列のインデックスに変換する関数です。

Hash Function Example
# ハッシュ関数の例
def simple_hash(key):
    hash_value = 0
    for char in key:
        hash_value += ord(char)
    return hash_value % 10


# 使用例
print(simple_hash("apple"))  # 5
print(simple_hash("banana"))  # 8

衝突

衝突は、異なるキーが同じハッシュ値を持つ現象です。

Collision Example
# 衝突の例
hash_table = {}


# 衝突が発生する場合
hash_table["apple"] = 1
hash_table["banana"] = 2


# 衝突の解決（チェイン法）
# （Pythonのdictは自動的に衝突を解決します）

走査

ハッシュテーブルの走査方法を理解する。

Iteration Example
# ハッシュテーブルの走査
hash_table = {"apple": 1, "banana": 2, "orange": 3}


# キーの走査
for key in hash_table:
    print(f"Key: {key}, Value: {hash_table[key]}")


# 値の走査
for value in hash_table.values():
    print(f"Value: {value}")


# キーと値の走査
for key, value in hash_table.items():
    print(f"Key: {key}, Value: {value}")

計算量

ハッシュテーブルの操作の計算量を理解する。

Complexity Example
# ハッシュテーブルの計算量
hash_table = {}


# 要素の追加: 平均O(1)
hash_table["apple"] = 1


# 要素の取得: 平均O(1)
print(hash_table["apple"])


# 要素の削除: 平均O(1)
del hash_table["apple"]


# 要素の検索: 平均O(1)
if "apple" in hash_table:
    print("Found")

使用例

ハッシュテーブルの実際の使用例を確認する。

Use Cases Example
# ハッシュテーブルの使用例
# キャッシュの実装
cache = {}


def get_data(key):
    if key in cache:
        return cache[key]
    data = fetch_from_database(key)
    cache[key] = data
    return data


# 重複排除
seen = set()


def process_item(item):
    if item in seen:
        return
    seen.add(item)
    # 処理を行う
    process(item)


# データのグループ化
groups = {}
for item in items:
    key = item.category
    if key not in groups:
        groups[key] = []
    groups[key].append(item)

合格ライン

☐ ハッシュテーブルの基本操作ができる
☐ ハッシュ関数の仕組みを理解している
☐ 衝突とその解決方法を理解している
☐ ハッシュテーブルの計算量を理解している
☐ ハッシュテーブルの使い分けができる

演習課題

課題1: ハッシュテーブルの基本操作
ハッシュテーブルを作成し、要素を追加・削除・検索するコードを書いてください。
課題2: ハッシュ関数の実装
文字列をキーとするハッシュ関数を実装してください。
課題3: 衝突の解決
衝突が発生した場合の解決戦略を実装してください。

参考文献

この記事は以下の公的ガイドライン/標準に基づいています。