Zenn
🐰

HashMap内の要素へのアクセスがO(1)になる理由と衝突が起こる理由

2024/05/18に公開
Go
ハッシュ
ハッシュマップ
tech

ハッシュマップ（Goではmap）のアクセスがO(1)になる理由は、ハッシュ関数を使用してキーから値へのアクセスを効率的に行うためです。ここでは、図と説明を用いてその仕組みとハッシュマップの衝突について説明します。

ハッシュマップの基本構造

  1. キーと値のペア:

    • ハッシュマップはキーと値のペアの集合です。
    • 各キーは一意で、対応する値があります。

  2. ハッシュ関数:

    • キーを入力として取り、そのキーに対するインデックス（バケット）を返します。
    • ハッシュ関数の目標は、異なるキーが可能な限り異なるインデックスを返すようにすることです。

ハッシュマップのアクセス方法

  1. キーからハッシュ値を計算:

    • キーに対してハッシュ関数を適用し、ハッシュ値を得ます。
    • このハッシュ値を使ってバケットのインデックスを決定します。

  2. バケットへのアクセス:

    • 計算されたインデックスを使って、直接バケットにアクセスします。
    • これにより、通常の条件下でアクセス時間はO(1)となります。

以下の図を参照してください：

 +-------------+
 |  Key: "cat" | ---> Hash Function ---> Index 3
 +-------------+

 +-------------+
 |  Key: "dog" | ---> Hash Function ---> Index 7
 +-------------+

 HashMap:
 Index: 0   1   2   3   4   5   6   7   8   9
         |   |   | "cat"|   |   |   | "dog"|   |

ハッシュマップの衝突

衝突の発生:

  • 複数の異なるキーが同じインデックスにマッピングされる場合、衝突が発生します。
  • 例えば、キー "bat" と "tab" が同じインデックス 3 にマッピングされるとします。

衝突を示す図：

 +-------------+      +-------------+
 |  Key: "bat" | ---> |  Key: "tab" |
 +-------------+      +-------------+
      |                    |
      |                    |
      v                    v
   Index 3              Index 3

 HashMap:
 Index: 0   1   2   3   4   5   6   7   8   9
         |   |   | "bat"|   |   |   | "dog"|   |
                     |
                     +--> "tab"

衝突解決方法:

  • チェイン法 (Separate Chaining):
    • 同じバケットにリストや別のデータ構造を用いて複数のキー-値ペアを格納します。
    • 各バケットはポインタを持ち、キー-値ペアのリストを指します。
  • オープンアドレス法 (Open Addressing):
    • 衝突が発生した場合、他の空いているバケットを探します。
    • リニアプロービング、二次プロービング、ダブルハッシュ法などの手法があります。

チェイン法の例:

 HashMap:
 Index: 0   1   2   3   4   5   6   7   8   9
         |   |   |   |   |   |   |   |   |   |
                     v
                   [("bat", value1), ("tab", value2)]

Go言語におけるハッシュマップの実装

Goのハッシュマップは上記のチェイン法に似た方法で実装されています。内部的には、キーに対してハッシュ関数を適用し、ハッシュ値をインデックスとして配列にアクセスします。衝突が発生した場合、リンクリストや他のデータ構造を用いて解決します。

package main

import "fmt"

func main() {
    // Goのマップの作成とアクセス
    m := make(map[string]int)
    m["cat"] = 1
    m["dog"] = 2
    
    // アクセスはO(1)
    fmt.Println(m["cat"]) // 1
    fmt.Println(m["dog"]) // 2
}

このように、ハッシュマップは効率的なアクセスを提供し、衝突を適切に処理することでパフォーマンスを維持します。

Discussion