エンジニア実践的基礎: ハッシュマップ/セット

yoshi

背景

このシリーズでは、エンジニアとして7年目を迎える節目に、これまで蓄積した知識を整理し、共有します。すべての記事を読めば、ミドルエンジニアとしてのスキルを身につけることができます。コンピュータサイエンスの理論よりも、実践的なソフトウェアエンジニアリングの知識に焦点を当てています。コーディングインタビューにも役立つ内容です。データ構造とアルゴリズムから設計、要件定義、バージョン管理、アジャイルなチーム開発、データベース、ネットワークなど、幅広いテーマを扱います。要するに、仕事に困らないレベルの知識を網羅します。

ハッシュマップとは

ハッシュマップ（HashMap）は、キーと値のペアを効率的に管理するためのデータ構造です。特定のキーに対応する値を素早く見つけることができるため、大量のデータを扱う場面で非常に便利です。

セットとは

セットは全ての値がユニークなデータ構造です。配列は複数の値を持てるデータ構造ですが、重複を許します。

array = [1, 1, 2] # 重複を持てる

セットは一意な値だけを持ちます。セットの実態は重複を許さないハッシュマップです。

ハッシュ化とは？

ハッシュ化は、任意のデータ（キー）を固定サイズの値（ハッシュ値）に変換するプロセスです。このハッシュ値を使って、データを効率的に格納する場所を決定します。

ハッシュマップは配列を使う

ハッシュマップは内部的に配列を使用して実装されることが多いです。これは、配列が特定のインデックスに直接アクセスできるデータ構造だからです。配列は、任意のインデックスに対して一定時間（O(1)）でアクセスできます。ハッシュマップでは、ハッシュ関数を使ってキーをインデックスに変換し、そのインデックスを使って配列にデータを格納します。

つまり、ハッシュマップのハッシュ値は配列のインデックスに対応します。これにより、キーに基づいてデータを効率よく格納し、取り出すことが可能になります。ハッシュマップが配列を使うのは、このように効率的にデータを管理できるためです。

ハッシュマップの例

ハッシュ化を図書館に例えてみましょう。

  • 本: ハッシュマップのキーに相当します。

  • 本棚の棚番号: 本を置く場所を示すインデックス、これがハッシュ値に相当します。

図書館では、本を効率よく管理するために、各本に棚番号を割り当て、その番号に従って本を配置します。ハッシュマップでも同様に、キーを使ってデータを格納する場所（インデックス）を決定します。

ハッシュ関数

今回のハッシュマップ実装では、キー（文字列）をインデックスに変換するために、各文字の文字コード（ASCIIコード）を合計するシンプルなハッシュ関数を使用します。

ハッシュ関数の実装

def hash(self, key):
    index = 0
    for c in key:
        index += ord(c)  # 文字をそのASCIIコードに変換して加算
    return index % self.capacity  # 合計をハッシュマップの容量で割ってインデックスを決定

ハッシュ関数の詳細な説明

  1. `index = 0`:

    • `index` はハッシュ値を保持するための変数です。

  2. `for c in key:`:

    • キーが文字列の場合、その文字列の各文字 `c` を順番に処理します。

  3. `index += ord(c)`:

    • `ord(c)` は、文字 `c` のASCIIコードを返します。例えば、`'A'` は 65、`'a'` は 97 です。このASCIIコードを `index` に加算していきます。これにより、キー全体に対する一意な数値が生成されます。

  4. `return index % self.capacity`:

    • 最後に、計算された `index` をハッシュマップの容量（`self.capacity`）で割った余りを返します。これにより、ハッシュ値がハッシュマップのサイズに収まるようになります。

衝突とは？

ハッシュマップでは、異なるキーが同じインデックス（ハッシュ値）にマッピングされることがあります。これを「衝突」と呼びます。

図書館の例での衝突

図書館に例えると、同じ棚番号に複数の本が割り当てられることがあります。例えば、「Alice in Wonderland」と「A Brief History of Time」が両方とも棚番号5に割り当てられる場合です。このような状況では、図書館員はどのようにして両方の本を効率よく管理するかを考える必要があります。

衝突の解決方法

衝突を解決するために、ハッシュマップにはいくつかの方法があります。代表的なものとして、オープンアドレッシングとチェーン法があります。

1. オープンアドレッシングによる衝突解決

オープンアドレッシングでは、衝突が発生した場合、次の空いている場所を探してデータを格納します。図書館では、予定していた棚がすでに埋まっている場合に、隣の空いた棚に本を置くイメージです。

再配置について

オープンアドレッシング方式では、ハッシュマップで衝突が発生したときに、データを別の空いている場所に再配置して管理します。再配置は、特定のキーが削除されたときに行われ、ハッシュマップの整合性を保つために重要な役割を果たします。

再配置が必要な理由は、削除された場所が空になった結果、その場所の後に続く他の要素が正しい位置から外れてしまうことを防ぐためです。正しい再配置を行わないと、後続の要素が誤って検索できなくなる可能性があります。

再配置の詳細な例（再配置が必要な場合）

以下の例で、オープンアドレッシングにおける再配置のプロセスを説明します。

初期状態

  • ハッシュマップ容量（capacity）：5

  • 格納されたデータ：`[("A", 1), ("B", 2), ("C", 3), ("D", 4), None]`

  • キーに対するハッシュ値は次のように計算されます。

    • `A` -> 0

    • `B` -> 1

    • `C` -> 2

    • `D` -> 3

# 現在のハッシュマップの状態
# インデックス:  0       1       2       3      4
# データ       [("A", 1), ("B", 2), ("C", 3), ("D", 4), None]

削除操作と再配置

  1. `B` を削除する:

    • `B` を削除すると、インデックス1が空になります。

# インデックス:  0       1       2       3      4
# データ       [("A", 1), None, ("C", 3), ("D", 4), None]

  1. 再配置の開始:

    • インデックス2（`current_index`）にある`C` を確認します。`C` の正しいインデックスは2（`correct_index`）ですが、`B` が削除されてインデックス1が空いたことで、再配置が必要になる可能性があります。

    • ここでは、インデックス2にある`C`は、削除されたインデックス1に移動する必要があります。

  2. インデックス1への再配置:

    • `C` をインデックス1に移動し、インデックス2を空にします。

# インデックス:  0       1       2       3      4
# データ       [("A", 1), ("C", 3), None, ("D", 4), None]

  1. 次のインデックスの確認:

    • 次にインデックス3にある `D` を確認します。`D` の正しいインデックスは3（`correct_index`）なので、再配置は不要です。

# インデックス:  0       1       2       3      4
# データ       [("A", 1), ("C", 3), None, ("D", 4), None]

このように、`B` の削除に伴って `C` を正しいインデックスに再配置することで、削除された場所に続く要素が正しく配置されていることを確認します。再配置が適切に行われることで、ハッシュマップの検索機能が削除後も正しく機能します。

この例では、`B` の削除後にインデックス1が空いたため、`C` を再配置する必要がありました。再配置を適切に行うことで、ハッシュマップの整合性が保たれ、検索操作が正しく機能し続けます。

リサイズとは？

ハッシュマップは、特定の容量（capacity）で初期化されます。しかし、データが増えると、ハッシュマップの容量が不足して、衝突が増え、パフォーマンスが低下する可能性があります。このような場合、ハッシュマップは「リサイズ」を行い、内部の配列をより大きなサイズに拡張します。リサイズによって、ハッシュマップの容量が増え、衝突の発生を減らし、データの格納と検索の効率を改善します。

リサイズの仕組み

  1. 容量の増加: リサイズでは、通常、ハッシュマップの容量を倍増させます。例えば、容量が10であった場合、リサイズ後は容量が20になります。

  2. 再ハッシュ: 新しい容量に合わせて、すべての既存のキーを再ハッシュし、新しいインデックスに再配置します。これにより、衝突が減り、データの分布が改善されます。

リサイズのトリガー

リサイズは、ハッシュマップの負荷率（load factor）によってトリガーされることが一般的です。負荷率とは、ハッシュマップの使用済みバケットの割合を指します。今回は半分埋まったらリサイズします。

オープンアドレッシングの実装例

class Pair:
    def __init__(self, key, val):
        self.key = key
        self.val = val

class HashMap:
    def __init__(self):
        self.size = 0
        self.capacity = 2
        self.map = [None, None]

    def hash(self, key):
        index = 0
        for c in key:
            index += ord(c)
        return index % self.capacity

    def get(self, key):
        index = self.hash(key)
        
        while self.map[index] != None:
            if self.map[index].key == key:
                return self.map[index].val
            index += 1
            index = index % self.capacity
        return None
    
    def put(self, key, val):
        index = self.hash(key)

        while True:
            if self.map[index] == None:
                self.map[index] = Pair(key, val)
                self.size += 1
                if self.size >= self.capacity // 2:
                    self.rehash()
                return
            elif self.map[index].key == key:
                self.map[index].val = val
                return
            
            index += 1
            index = index % self.capacity

    def remove(self, key):
        if not self.get(key):
            return
        
        empty_index = self.hash(key)
        
        while True:
            if self.map[empty_index].key == key:
                self.map[empty_index] = None
                self.size -= 1
                
                # 削除した位置の次のインデックスから再配置を開始
                current_index = (empty_index + 1) % self.capacity
                while self.map[current_index] is not None:
                    # 現在の要素の本来の位置を計算
                    correct_index = self.hash(self.map[current_index].key)
                    
                    # 要素の再配置が必要か確認
                    if (correct_index == empty_index or             # 条件1
                    correct_index < empty_index < current_index or  # 条件2
                    current_index < correct_index < empty_index or  # 条件3
                    empty_index < current_index < correct_index):   # 条件4

                        # 条件1: 現在の要素が本来配置されるべきインデックス（correct_index）が削除されたインデックス（empty_index）と同じ場合。
                        # 
                        # 条件2, 3, 4 は、ターンアラウンドを考慮して correct_index と current_index の間に empty_index がある場合を考慮している。
                        # correct_index と current_index の間に empty_index があると検索が削除されたインデックス（empty_index）で止まる可能性がある。
                        #
                        # 条件2: ターンアラウンドが発生していない場合。
                        # 条件3: current_index がターンアラウンドしている場合。
                        # 条件4: empty_index がターンアラウンドしている場合。

                        self.map[empty_index] = self.map[current_index]
                        self.map[current_index] = None
                        empty_index = current_index  # 空のインデックスを更新

                    # 次のインデックスを確認するために current_index を更新
                    current_index = (current_index + 1) % self.capacity
                
                # すべての再配置が完了したら削除処理を終了
                return
            
            # キーが見つからない場合、次のインデックスを確認
            empty_index += 1
            empty_index = empty_index % self.capacity

    def rehash(self):
        self.capacity = 2 * self.capacity
        newMap = []
        for i in range(self.capacity):
            newMap.append(None)

        oldMap = self.map
        self.map = newMap
        self.size = 0
        for pair in oldMap:
            if pair:
                self.put(pair.key, pair.val)

2. チェーン法による衝突解決

チェーン法では、同じインデックスに複数のキーが衝突した場合、そのインデックスにリスト（チェーン）を作成し、すべてのキーと値のペアをそのリストに追加します。図書館では、同じ棚番号に複数の本をまとめて置くイメージです。

実装

class Pair:
    def __init__(self, key, val):
        self.key = key
        self.val = val

class HashMap:
    def __init__(self):
        self.size = 0
        self.capacity = 2
        self.map = [[] for _ in range(self.capacity)]

    def hash(self, key):
        index = 0
        for c in key:
            index += ord(c)
        return index % self.capacity

    def get(self, key):
        index = self.hash(key)
        for pair in self.map[index]:
            if pair.key == key:
                return pair.val
        return None
    
    def put(self, key, val):
        index = self.hash(key)
        for pair in self.map[index]:
            if pair.key == key:
                pair.val = val
                return
        # 新しいキーの場合
        self.map[index].append(Pair(key, val))
        self.size += 1

        # サイズが容量の半分を超えたらリサイズ
        if self.size >= self.capacity // 2:
            self.rehash()

    def remove(self, key):
        index = self.hash(key)
        for i, pair in enumerate(self.map[index]):
            if pair.key == key:
                del self.map[index][i]
                self.size -= 1
                return

    def rehash(self):
        old_map = self.map
        self.capacity *= 2
        self.map = [[] for _ in range(self.capacity)]
        self.size = 0
        for chain in old_map:
            for pair in chain:
                self.put(pair.key, pair.val)

セットの実装

セットの実態は重複を許さないハッシュマップなので、ハッシュマップの実装を少し変更します。オープンアドレス・チェーン法のどちらでも実装できますが、簡単なチェーン法を使います。

class Set:
    def __init__(self):
        self.size = 0
        self.capacity = 2
        self.map = [[] for _ in range(self.capacity)]

    def _hash(self, key):
        """キーをハッシュ化してインデックスを計算"""
        index = 0
        for c in key:
            index += ord(c)
        return index % self.capacity

    def add(self, value):
        """Setに値を追加。すでに存在する場合は無視"""
        if not self.contains(value):
            index = self._hash(value)
            self.map[index].append(value)
            self.size += 1

            # サイズが容量の半分を超えたらリサイズ
            if self.size >= self.capacity // 2:
                self._rehash()

    def remove(self, value):
        """Setから値を削除"""
        index = self._hash(value)
        if value in self.map[index]:
            self.map[index].remove(value)
            self.size -= 1

    def contains(self, value):
        """Setに値が存在するか確認"""
        index = self._hash(value)
        return value in self.map[index]

    def _rehash(self):
        """Setを再ハッシュして容量を増やす"""
        old_map = self.map
        self.capacity *= 2
        self.map = [[] for _ in range(self.capacity)]
        self.size = 0
        for chain in old_map:
            for value in chain:
                self.add(value)

    def get_size(self):
        """Setの要素数を取得"""
        return self.size

オペレーション別の時間・空間計算量

ハッシュマップの各オペレーション（挿入、検索、削除）の時間・空間計算量を以下にまとめます。

  • 挿入 (`put`):

    • 時間計算量: 平均 O(1)

    • 空間計算量: O(1)（既存のハッシュマップが満たされている場合はリサイズが必要）

  • 検索 (`get`):

    • 時間計算量: 平均 O(1)

    • 空間計算量: O(1)

  • 削除 (`remove`):

    • 時間計算量: 平均 O(1)

    • 空間計算量: O(1)

まとめ

ハッシュマップは、キーと値を効率的に管理するためのデータ構造です。ハッシュ化を行うことで、データの格納と検索が高速に行えるようになります。しかし、ハッシュ化には「衝突」という問題が伴います。オープンアドレッシングとチェーン法は、この衝突を解決するための2つの方法です。さらに、オープンアドレッシングでは再配置が重要な役割を果たし、削除後もハッシュマップの整合性を保ちます。

いいなと思ったら応援しよう！