6.1 ハッシュ表¶
ハッシュ表はハッシュマップとも呼ばれ、キーと値の間のマッピングを確立し、効率的な要素の取得を可能にするデータ構造です。具体的には、ハッシュ表にkeyを入力すると、\(O(1)\)の時間計算量で対応するvalueを取得できます。
下図に示すように、\(n\)人の学生がいて、各学生には「名前」と「学籍番号」の2つのデータフィールドがあるとします。学籍番号を入力として対応する名前を返すクエリ機能を実装したい場合、下図に示すハッシュ表を使用できます。
図 6-1 ハッシュ表の抽象的な表現
ハッシュ表に加えて、配列や連結リストもクエリ機能の実装に使用できますが、時間計算量が異なります。効率は以下の表で比較されています：
- 要素の挿入: 配列（または連結リスト）の末尾に要素を追加するだけです。この操作の時間計算量は\(O(1)\)です。
- 要素の検索: 配列（または連結リスト）がソートされていないため、要素を検索するにはすべての要素を走査する必要があります。この操作の時間計算量は\(O(n)\)です。
- 要素の削除: 要素を削除するには、まずその要素を見つけてから、配列（または連結リスト）から削除します。この操作の時間計算量は\(O(n)\)です。
表 6-1 一般的な操作の時間効率の比較
| 配列 | 連結リスト | ハッシュ表 | |
|---|---|---|---|
| 要素の検索 | \(O(n)\) | \(O(n)\) | \(O(1)\) |
| 要素の挿入 | \(O(1)\) | \(O(1)\) | \(O(1)\) |
| 要素の削除 | \(O(n)\) | \(O(n)\) | \(O(1)\) |
観察されるように、**ハッシュ表における操作（挿入、削除、検索、変更）の時間計算量は\(O(1)\)**で、非常に効率的です。
6.1.1 ハッシュ表の一般的な操作¶
ハッシュ表の一般的な操作には、初期化、クエリ、キー値ペアの追加、キー値ペアの削除があります。以下はコード例です：
hash_map.cpp
/* ハッシュ表を初期化 */
unordered_map<int, string> map;
/* 追加操作 */
// ハッシュ表にキー値ペア (key, value) を追加
map[12836] = "小哈";
map[15937] = "小啰";
map[16750] = "小算";
map[13276] = "小法";
map[10583] = "小鸭";
/* クエリ操作 */
// ハッシュ表にキーを入力し、値を取得
string name = map[15937];
/* 削除操作 */
// ハッシュ表からキー値ペア (key, value) を削除
map.erase(10583);
hash_map.java
/* ハッシュ表を初期化 */
Map<Integer, String> map = new HashMap<>();
/* 追加操作 */
// ハッシュ表にキー値ペア (key, value) を追加
map.put(12836, "小哈");
map.put(15937, "小啰");
map.put(16750, "小算");
map.put(13276, "小法");
map.put(10583, "小鸭");
/* クエリ操作 */
// ハッシュ表にキーを入力し、値を取得
String name = map.get(15937);
/* 削除操作 */
// ハッシュ表からキー値ペア (key, value) を削除
map.remove(10583);
hash_map.cs
/* ハッシュ表を初期化 */
Dictionary<int, string> map = new() {
/* 追加操作 */
// ハッシュ表にキー値ペア (key, value) を追加
{ 12836, "小哈" },
{ 15937, "小啰" },
{ 16750, "小算" },
{ 13276, "小法" },
{ 10583, "小鸭" }
};
/* クエリ操作 */
// ハッシュ表にキーを入力し、値を取得
string name = map[15937];
/* 削除操作 */
// ハッシュ表からキー値ペア (key, value) を削除
map.Remove(10583);
hash_map_test.go
/* ハッシュ表を初期化 */
hmap := make(map[int]string)
/* 追加操作 */
// ハッシュ表にキー値ペア (key, value) を追加
hmap[12836] = "小哈"
hmap[15937] = "小啰"
hmap[16750] = "小算"
hmap[13276] = "小法"
hmap[10583] = "小鸭"
/* クエリ操作 */
// ハッシュ表にキーを入力し、値を取得
name := hmap[15937]
/* 削除操作 */
// ハッシュ表からキー値ペア (key, value) を削除
delete(hmap, 10583)
hash_map.swift
/* ハッシュ表を初期化 */
var map: [Int: String] = [:]
/* 追加操作 */
// ハッシュ表にキー値ペア (key, value) を追加
map[12836] = "小哈"
map[15937] = "小啰"
map[16750] = "小算"
map[13276] = "小法"
map[10583] = "小鸭"
/* クエリ操作 */
// ハッシュ表にキーを入力し、値を取得
let name = map[15937]!
/* 削除操作 */
// ハッシュ表からキー値ペア (key, value) を削除
map.removeValue(forKey: 10583)
hash_map.js
/* ハッシュ表を初期化 */
const map = new Map();
/* 追加操作 */
// ハッシュ表にキー値ペア (key, value) を追加
map.set(12836, '小哈');
map.set(15937, '小啰');
map.set(16750, '小算');
map.set(13276, '小法');
map.set(10583, '小鸭');
/* クエリ操作 */
// ハッシュ表にキーを入力し、値を取得
let name = map.get(15937);
/* 削除操作 */
// ハッシュ表からキー値ペア (key, value) を削除
map.delete(10583);
hash_map.ts
/* ハッシュ表を初期化 */
const map = new Map<number, string>();
/* 追加操作 */
// ハッシュ表にキー値ペア (key, value) を追加
map.set(12836, '小哈');
map.set(15937, '小啰');
map.set(16750, '小算');
map.set(13276, '小法');
map.set(10583, '小鸭');
console.info('\n追加後、ハッシュ表は\nKey -> Value');
console.info(map);
/* クエリ操作 */
// ハッシュ表にキーを入力し、値を取得
let name = map.get(15937);
console.info('\n学籍番号15937を入力、名前を問い合わせ ' + name);
/* 削除操作 */
// ハッシュ表からキー値ペア (key, value) を削除
map.delete(10583);
console.info('\n10583を削除後、ハッシュ表は\nKey -> Value');
console.info(map);
hash_map.dart
/* ハッシュ表を初期化 */
Map<int, String> map = {};
/* 追加操作 */
// ハッシュ表にキー値ペア (key, value) を追加
map[12836] = "小哈";
map[15937] = "小啰";
map[16750] = "小算";
map[13276] = "小法";
map[10583] = "小鸭";
/* クエリ操作 */
// ハッシュ表にキーを入力し、値を取得
String name = map[15937];
/* 削除操作 */
// ハッシュ表からキー値ペア (key, value) を削除
map.remove(10583);
hash_map.rs
use std::collections::HashMap;
/* ハッシュ表を初期化 */
let mut map: HashMap<i32, String> = HashMap::new();
/* 追加操作 */
// ハッシュ表にキー値ペア (key, value) を追加
map.insert(12836, "小哈".to_string());
map.insert(15937, "小啰".to_string());
map.insert(16750, "小算".to_string());
map.insert(13279, "小法".to_string());
map.insert(10583, "小鸭".to_string());
/* クエリ操作 */
// ハッシュ表にキーを入力し、値を取得
let _name: Option<&String> = map.get(&15937);
/* 削除操作 */
// ハッシュ表からキー値ペア (key, value) を削除
let _removed_value: Option<String> = map.remove(&10583);
ハッシュ表を走査する一般的な方法は3つあります：キー値ペアの走査、キーの走査、値の走査。以下はコード例です：
hash_map.java
/* ハッシュ表を走査 */
// キー値ペア key->value を走査
for (Map.Entry<Integer, String> kv: map.entrySet()) {
System.out.println(kv.getKey() + " -> " + kv.getValue());
}
// キーのみを走査
for (int key: map.keySet()) {
System.out.println(key);
}
// 値のみを走査
for (String val: map.values()) {
System.out.println(val);
}
6.1.2 ハッシュ表の簡単な実装¶
まず、最も簡単なケースを考えてみましょう：配列のみを使ってハッシュ表を実装すること。ハッシュ表において、配列の各空きスロットはバケットと呼ばれ、各バケットはキー値ペアを格納できます。したがって、クエリ操作はkeyに対応するバケットを見つけ、そこからvalueを取得することになります。
では、keyに基づいて対応するバケットをどのように特定するのでしょうか？これはハッシュ関数によって実現されます。ハッシュ関数の役割は、より大きな入力空間をより小さな出力空間にマッピングすることです。ハッシュ表では、入力空間はすべてのキーで構成され、出力空間はすべてのバケット（配列インデックス）で構成されます。つまり、keyが与えられた場合、ハッシュ関数を使用して対応するキー値ペアの配列内の格納位置を決定できます。
与えられたkeyに対して、ハッシュ関数の計算は2つのステップで構成されます：
- 特定のハッシュアルゴリズム
hash()を使用してハッシュ値を計算します。 - ハッシュ値をバケット数（配列長）
capacityで剰余を取り、キーに対応する配列indexを取得します。
その後、indexを使用してハッシュ表内の対応するバケットにアクセスし、valueを取得できます。
配列長がcapacity = 100で、ハッシュアルゴリズムがhash(key) = keyとして定義されているとします。したがって、ハッシュ関数はkey % 100として表現できます。以下の図は、keyを学籍番号、valueを名前として、ハッシュ関数の動作原理を示しています。
図 6-2 ハッシュ関数の動作原理
以下のコードは簡単なハッシュ表を実装しています。ここでは、keyとvalueをPairクラスにカプセル化してキー値ペアを表現しています。
array_hash_map.py
class Pair:
"""キー値ペア"""
def __init__(self, key: int, val: str):
self.key = key
self.val = val
class ArrayHashMap:
"""配列実装に基づくハッシュテーブル"""
def __init__(self):
"""コンストラクタ"""
# 100個のバケットを含む配列を初期化
self.buckets: list[Pair | None] = [None] * 100
def hash_func(self, key: int) -> int:
"""ハッシュ関数"""
index = key % 100
return index
def get(self, key: int) -> str:
"""照会操作"""
index: int = self.hash_func(key)
pair: Pair = self.buckets[index]
if pair is None:
return None
return pair.val
def put(self, key: int, val: str):
"""追加操作"""
pair = Pair(key, val)
index: int = self.hash_func(key)
self.buckets[index] = pair
def remove(self, key: int):
"""削除操作"""
index: int = self.hash_func(key)
# None に設定し、削除を表現
self.buckets[index] = None
def entry_set(self) -> list[Pair]:
"""すべてのキー値ペアを取得"""
result: list[Pair] = []
for pair in self.buckets:
if pair is not None:
result.append(pair)
return result
def key_set(self) -> list[int]:
"""すべてのキーを取得"""
result = []
for pair in self.buckets:
if pair is not None:
result.append(pair.key)
return result
def value_set(self) -> list[str]:
"""すべての値を取得"""
result = []
for pair in self.buckets:
if pair is not None:
result.append(pair.val)
return result
def print(self):
"""ハッシュテーブルを出力"""
for pair in self.buckets:
if pair is not None:
print(pair.key, "->", pair.val)
array_hash_map.cpp
/* キー値ペア */
struct Pair {
public:
int key;
string val;
Pair(int key, string val) {
this->key = key;
this->val = val;
}
};
/* 配列実装に基づくハッシュテーブル */
class ArrayHashMap {
private:
vector<Pair *> buckets;
public:
ArrayHashMap() {
// 配列を初期化、100個のバケットを含む
buckets = vector<Pair *>(100);
}
~ArrayHashMap() {
// メモリを解放
for (const auto &bucket : buckets) {
delete bucket;
}
buckets.clear();
}
/* ハッシュ関数 */
int hashFunc(int key) {
int index = key % 100;
return index;
}
/* クエリ操作 */
string get(int key) {
int index = hashFunc(key);
Pair *pair = buckets[index];
if (pair == nullptr)
return "";
return pair->val;
}
/* 追加操作 */
void put(int key, string val) {
Pair *pair = new Pair(key, val);
int index = hashFunc(key);
buckets[index] = pair;
}
/* 削除操作 */
void remove(int key) {
int index = hashFunc(key);
// メモリを解放してnullptrに設定
delete buckets[index];
buckets[index] = nullptr;
}
/* すべてのキー値ペアを取得 */
vector<Pair *> pairSet() {
vector<Pair *> pairSet;
for (Pair *pair : buckets) {
if (pair != nullptr) {
pairSet.push_back(pair);
}
}
return pairSet;
}
/* すべてのキーを取得 */
vector<int> keySet() {
vector<int> keySet;
for (Pair *pair : buckets) {
if (pair != nullptr) {
keySet.push_back(pair->key);
}
}
return keySet;
}
/* すべての値を取得 */
vector<string> valueSet() {
vector<string> valueSet;
for (Pair *pair : buckets) {
if (pair != nullptr) {
valueSet.push_back(pair->val);
}
}
return valueSet;
}
/* ハッシュテーブルを印刷 */
void print() {
for (Pair *kv : pairSet()) {
cout << kv->key << " -> " << kv->val << endl;
}
}
};
array_hash_map.java
/* キー値ペア */
class Pair {
public int key;
public String val;
public Pair(int key, String val) {
this.key = key;
this.val = val;
}
}
/* 配列実装に基づくハッシュテーブル */
class ArrayHashMap {
private List<Pair> buckets;
public ArrayHashMap() {
// 100個のバケットを含む配列を初期化
buckets = new ArrayList<>();
for (int i = 0; i < 100; i++) {
buckets.add(null);
}
}
/* ハッシュ関数 */
private int hashFunc(int key) {
int index = key % 100;
return index;
}
/* クエリ操作 */
public String get(int key) {
int index = hashFunc(key);
Pair pair = buckets.get(index);
if (pair == null)
return null;
return pair.val;
}
/* 追加操作 */
public void put(int key, String val) {
Pair pair = new Pair(key, val);
int index = hashFunc(key);
buckets.set(index, pair);
}
/* 削除操作 */
public void remove(int key) {
int index = hashFunc(key);
// nullに設定して削除を示す
buckets.set(index, null);
}
/* すべてのキー値ペアを取得 */
public List<Pair> pairSet() {
List<Pair> pairSet = new ArrayList<>();
for (Pair pair : buckets) {
if (pair != null)
pairSet.add(pair);
}
return pairSet;
}
/* すべてのキーを取得 */
public List<Integer> keySet() {
List<Integer> keySet = new ArrayList<>();
for (Pair pair : buckets) {
if (pair != null)
keySet.add(pair.key);
}
return keySet;
}
/* すべての値を取得 */
public List<String> valueSet() {
List<String> valueSet = new ArrayList<>();
for (Pair pair : buckets) {
if (pair != null)
valueSet.add(pair.val);
}
return valueSet;
}
/* ハッシュテーブルを印刷 */
public void print() {
for (Pair kv : pairSet()) {
System.out.println(kv.key + " -> " + kv.val);
}
}
}
6.1.3 ハッシュ衝突とリサイズ¶
本質的に、ハッシュ関数の役割は、すべてのキーの入力空間全体を、すべての配列インデックスの出力空間にマッピングすることです。しかし、入力空間は出力空間よりもはるかに大きいことがよくあります。したがって、理論的には、「複数の入力が同じ出力に対応する」ケースが常に存在します。
上記の例では、与えられたハッシュ関数で、入力keyの下二桁が同じ場合、ハッシュ関数は同じ出力を生成します。例えば、学籍番号12836と20336の2人の学生をクエリすると、以下のことがわかります：
下図に示すように、両方の学籍番号が同じ名前を指しており、これは明らかに間違っています。この複数の入力が同じ出力に対応する状況をハッシュ衝突と呼びます。
図 6-3 ハッシュ衝突の例
ハッシュ表の容量\(n\)が増加するにつれて、複数のキーが同じバケットに割り当てられる確率が減少し、衝突が少なくなることは理解しやすいです。したがって、ハッシュ表をリサイズすることでハッシュ衝突を減らすことができます。
下図に示すように、リサイズ前は、キー値ペア(136, A)と(236, D)が衝突していました。しかし、リサイズ後は衝突が解決されています。
図 6-4 ハッシュ表のリサイズ
配列の拡張と同様に、ハッシュ表のリサイズにはすべてのキー値ペアを元のハッシュ表から新しいものに移行する必要があり、時間がかかります。さらに、ハッシュ表のcapacityが変更されるため、ハッシュ関数を使用してすべてのキー値ペアの格納位置を再計算する必要があり、リサイズプロセスの計算オーバーヘッドがさらに増加します。したがって、プログラミング言語は頻繁なリサイズを防ぐために、ハッシュ表に十分大きな容量を割り当てることがよくあります。
負荷率はハッシュ表の重要な概念です。ハッシュ表内の要素数とバケット数の比率として定義されます。ハッシュ衝突の深刻度を測定するために使用され、しばしばハッシュ表のリサイズのトリガーとしても機能します。例えば、Javaでは、負荷率が\(0.75\)を超えると、システムはハッシュ表を元のサイズの2倍にリサイズします。