【Python】組み込みライブラリを使わずにHashMap（ハッシュマップ）を設計する方法

この記事では、Pythonの組み込みハッシュテーブルライブラリ（dictなど）に頼らず、ゼロからHashMap（ハッシュマップ）を設計する方法を解説します。ハッシュマップは「キーと値のペア」を効率的に管理するデータ構造であり、以下の3つの基本操作をサポートする必要があります。

実装すべき3つの基本メソッド

• put(key, value) ― 指定したキーに対応する値をハッシュマップに挿入します。同じキーが既に存在する場合は、値を新しいものに更新します。
• get(key) ― 指定したキーにマッピングされた値を返します。キーが存在しない場合は -1 を返します。
• remove(key) ― 指定したキーに対応するマッピングが存在すれば、それを削除します。

動作例

初期化後、次の順序でメソッドを呼び出した場合を考えてみましょう。

put(1, 1);
put(2, 2);
get(1);
get(3);
put(2, 1);
get(2);
remove(2);
get(2);

この場合の出力は、順に 1、-1（キー3は存在しないため）、1（キー2の値が更新されているため）、-1（キー2は削除済みのため）となります。

設計方針：連結リスト＋ハッシュ関数

ハッシュの衝突（異なるキーが同じハッシュ値になる現象）に対応するため、「チェイン法」と呼ばれる手法を採用します。各バケットに連結リストを持たせ、同じハッシュ値に属する要素をそこへ格納します。全体の構成は以下の通りです。

1. Nodeクラス（ノード）

• フィールドとして key、val、next を持ちます。next は初期状態で None です。

2. LinkedListクラス（連結リスト）

• __init__()：ダミーの先頭ノード（prehead）を key=None、val=None で生成します。
• search(key)：prehead.next から順に走査し、key が一致するノードを返します。見つからなければ None を返します。
• add(key, val)：search() で既存ノードを探し、あれば val を更新、なければ新ノードを先頭に挿入します。
• get(key)：search() の結果があればその val を、なければ None を返します。
• remove(key)：prev と cur の2つのポインタで走査し、一致するノードを見つけたらリンクをつなぎ替えて削除します。
• serialize()：リスト内のすべての [key, val] ペアを配列として返します（デバッグ用）。

3. MyHashMapクラス（本体）

• __init__()：バケット数 size を 1033（素数）とし、LinkedList の配列 arr を生成します。
• _hash(key)：key % size を計算してバケットのインデックスを求めます。
• put(key, value)：ハッシュ値 h を計算し、arr[h] の add() を呼び出します。
• get(key)：arr[h] の get() を呼び出し、結果が None なら -1 を返します。
• remove(key)：arr[h] の remove() を呼び出して該当エントリを削除します。

Pythonでの実装例

class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None


class LinkedList:
    def __init__(self):
        self.prehead = Node(None, None)

    def search(self, key):
        p = self.prehead.next
        while p:
            if p.key == key:
                return p
            p = p.next
        return None

    def add(self, key, val):
        p = self.search(key)
        if p:
            p.val = val
        else:
            node = Node(key, val)
            self.prehead.next, node.next = node, self.prehead.next

    def get(self, key):
        p = self.search(key)
        if p:
            return p.val
        else:
            return None

    def remove(self, key):
        prev = self.prehead
        cur = prev.next
        while cur:
            if cur.key == key:
                break
            prev, cur = cur, cur.next
        if cur:
            prev.next = cur.next

    def serialize(self):
        p = self.prehead.next
        ret = []
        while p:
            ret.append([p.key, p.val])
            p = p.next
        return ret


class MyHashMap:
    def __init__(self):
        self.size = 1033
        self.arr = [LinkedList() for _ in range(self.size)]

    def _hash(self, key):
        return key % self.size

    def put(self, key, value):
        h = self._hash(key)
        self.arr[h].add(key, value)

    def get(self, key):
        h = self._hash(key)
        ret = self.arr[h].get(key)
        if ret is not None:
            return ret
        else:
            return -1

    def remove(self, key):
        h = self._hash(key)
        self.arr[h].remove(key)


ob = MyHashMap()
ob.put(1, 1)
ob.put(2, 2)
print(ob.get(1))
print(ob.get(3))
ob.put(2, 1)
print(ob.get(2))
ob.remove(2)
print(ob.get(2))

入力

ob = MyHashMap()
ob.put(1, 1)
ob.put(2, 2)
print(ob.get(1))
print(ob.get(3))
ob.put(2, 1)
print(ob.get(2))
ob.remove(2)
print(ob.get(2))

出力

1
-1
1
-1

計算量について

平均的なケースでは、ハッシュ関数によって要素がバケットに均等に分散されるため、put・get・remove はいずれも O(1)（償却定数時間）で動作します。最悪の場合（すべてのキーが同一バケットに集中した場合）は、連結リストの走査が必要となり O(n) かかります。バケット数を素数（ここでは1033）に設定することで、剰余演算による偏りを抑え、衝突を減らすことができます。