ハッシュマップをPythonで実装する　#446

こちらの続きで、ハッシュテーブルの1種であるハッシュマップをPythonで実装してみます。

本題に入る前に、まずはハッシュテーブルについて理解を深めたいと思います。

ハッシュテーブルの長所と短所

長所

高速な検索、挿入、削除:
平均的な状況下で、ハッシュテーブルはO(1)の時間複雑度で検索・挿入・削除を行うことができます。これは、キーに対応する値を直接アクセスすることができるためです。

効率的なメモリ利用:
ハッシュテーブルは、データを格納するために必要なメモリ空間を効率的に使用します。特に動的なハッシュテーブルは、使用されていないメモリを最小限に抑えるためにサイズ調整ができます。

柔軟性:
ハッシュテーブルは、異なるタイプのキーに対して値を保存でき、柔軟に使用することができます。

データ構造の簡素化:
キーと値のペアを使用してデータを格納することで、データ構造を簡素化して開発プロセスを効率化することができます。

短所

衝突の可能性:
二つ以上のキーが同じハッシュ値にマッピングされる場合、衝突が発生します。衝突を適切に処理するアルゴリズムが必要ですが、これが複雑になることがあります（前回の記事ではチェーン法でこれを回避しました）。

ハッシュ関数の選択:
効率的なハッシュテーブルの使用には、適切なハッシュ関数の選択が不可欠です。例えばハッシュ値が単純な1文字の小文字アルファベットだった場合、そのパターンは26文字です。仮にデータを振り分けるバケットが100個あったとしたら、26個にデータが振り分けられ、残りの74個は空っぽということになり、十分に効率を高められません。
良いハッシュ関数は均等なハッシュ値の分布を提供し、衝突の可能性を最小限に抑えます。

あいまい検索ができない(常に全スキャンになる):
これがハッシュテーブル関連の大きな弱点です。キーを元にハッシュ値を生成して分散させるため、完全一致の検索以外だとバケットを特定できず、常に全スキャンして検索することになります。
つまりハッシュは完全一致できる検索でしか使ってはならない仕組みともいえます。

順序性の欠如:
ハッシュテーブルはキーの順序を保持しません。つまりキーの順序が重要な場合、ハッシュテーブルは適切な選択ではありません。

メモリのオーバーヘッド:
ハッシュテーブルが大きくなると、未使用のエントリによるメモリのオーバーヘッドが問題になることがあります。

ハッシュマップとは

ハッシュマップは、キーと値のペアを格納するために使用されるデータ構造で、ハッシュテーブルの一種と見なすことができます。キーをハッシュ関数に通してデータを格納します。

具体的なコード例

ハッシュマップは以下のように実装できます。
keyとvalueを使っているので一見辞書型っぽいですが、実際はタプルで実装しています。

class MyHashMap:

    def __init__(self, capacity=1000):
        self.capacity = capacity
        self.buckets = [[] for _ in range(capacity)]

    def hash(self, key):
        return key % self.capacity

    def put(self, key: int, value: int) -> None:
        bucket_index = self.hash(key)
        for i, (k, v) in enumerate(self.buckets[bucket_index]):
            if key == k:
                self.buckets[bucket_index][i] = (key, value)
                return
        self.buckets[bucket_index].append((key, value))
            
    def get(self, key: int) -> int:        
        bucket_index = self.hash(key)
        for i, (k, v) in enumerate(self.buckets[bucket_index]):
            if key == k:
                return v
        return -1

    def remove(self, key: int) -> None:
        bucket_index = self.hash(key)
        for i, (k, v) in enumerate(self.buckets[bucket_index]):
            if key == k:
                del self.buckets[bucket_index][i]
                return

ハッシュ値ごとに特定のbucketにタプルを格納していくので、keyの検索範囲が1つのbucketに限定され、高速に処理できます。

格納していった値を常にフルスキャンする場合と比べて圧倒的に効率的です。

ここまでお読みいただきありがとうございました！