ハッシュ探索
- 探索対象のデータを一定の規則に従い一時配列（ハッシュ表）に格納し、この値を使ってデータの探索を行う
- データ数が多かったとしても対象の要素がある場所を1回の計算で導くことができるので探索が非常に高速
- ハッシュ関数を使って、キーを一定の範囲の数値（ハッシュ値）に変換する
- このハッシュ値を利用して、データをハッシュテーブル内の特定の位置に格納
- データを操作するためのインデックスを求めることで、探索だけでなく追加、削除も効率よく実行できる
実行環境
- JUnit 5
- Java 8
テストコード
※ テストを実行させると「衝突」が起きます
HashTableTest.java
import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.Matchers.nullValue;
public class HashTableTest {
private HashTable<String, Integer> hashTable;
@BeforeEach
void setUp() {
hashTable = new HashTable<>();
hashTable.put("apple", 1);
hashTable.put("banana", 2);
hashTable.put("orange", 3);
hashTable.put("grape", 4);
hashTable.put("lemon", 5);
}
@DisplayName("既に追加されている値を取得できること")
@ParameterizedTest(name = "No.{index}: キー {0} を探すとインデックス {1} を返す")
@CsvSource(value = {
"apple, 1",
"banana, 2",
"orange, 3",
"grape, 4",
"lemon, 5"
})
void testGet(String key, Integer expected) {
assertThat(hashTable.get(key), is(expected));
}
@DisplayName("値が追加されていること")
@Test
void testPut() {
hashTable.put("kiwi", 6);
assertThat(hashTable.get("kiwi"), is(6));
}
@DisplayName("存在しないキーを取得するとnullが返ること")
@Test
void testGetNonExistentKey() {
Integer actual = hashTable.get("nonexistent");
assertThat(actual, is(nullValue()));
}
@DisplayName("同じキーに対する値の上書きが正しく行われること")
@Test
void testOverwriteValue() {
hashTable.put("apple", 10);
assertThat(hashTable.get("apple"), is(10));
}
}
ハッシュ探索アルゴリズム
※ この実装では「衝突」が起きます
HashTable.java
class HashTable<K, V> {
/**
* ハッシュ表（ハッシュ値がインデックスとなるようにキー値を格納した配列）
*/
private HashNode<K, V>[] buckets;
/**
* ハッシュ表のサイズ
* ハッシュ表を大きくすれば衝突する確率は低くなる。
* 一方で、バケット数を大きくするとメモリ使用量が増加する。
*/
private final int numBuckets = 10;
@SuppressWarnings("unchecked")
public HashTable() {
buckets = new HashNode[numBuckets];
}
/**
* キーのハッシュ値を返すシンプルなハッシュ関数
* 負のインデックスを防ぐため、絶対値を取るようabsメソッドを使用
* ※ 異なるキーでも同じハッシュ値を得る（衝突が起きる）可能性がある
*
* @param キー
* @return ハッシュ値
*/
private int hash(K key) {
return Math.abs(key.hashCode()) % numBuckets;
}
/**
* ハッシュ表にノードを追加する
* ※ 今の実装では、衝突が発生した場合に既存の値が上書きされる
* @param key
* @param value
*/
public void put(K key, V value) {
int bucketIndex = hash(key);
buckets[bucketIndex] = new HashNode<>(key, value);
}
/**
* 計算したキーのハッシュ値をインデックスとしてハッシュ表からノードを取得
* ノードが存在し、キーが一致する場合はその値を返す
* ノードが存在しない、またはキーが不一致の場合はnullを返す
* @param key
* @return value
*/
public V get(K key) {
int bucketIndex = hash(key);
// デバッグ用（後述）
System.out.println(key + " のbucketIndexは " + Math.abs(bucketIndex));
HashNode<K, V> node = buckets[bucketIndex];
if (node != null && node.key.equals(key)) {
return node.value;
}
return null;
}
}
HashNode.java
/**
* ハッシュテーブル内でキーと値のペアを格納するための基本単位
* ジェネリッククラスとして実装されており、様々な型のキーと値を扱うことができる
*
* @param <K> キーの型
* @param <V> 値の型
*/
class HashNode<K, V> {
K key;
V value;
public HashNode(K key, V value) {
this.key = key;
this.value = value;
}
}
衝突
ハッシュアルゴリズムにおいて、異なるデータから同じ格納位置が生成されてしまう状況を「衝突」と呼びます。
今回のサンプルコードでいくと、バケットのサイズを以下のように宣言していました。
HashTable.java
/**
* ハッシュ表のサイズ
* ハッシュ表を大きくすれば衝突する確率は低くなる。
* 一方で、バケット数を大きくするとメモリ使用量が増加する。
*/
private final int numBuckets = 10;
サンプルとして実装しているhash() メソッドでは、hashCode() メソッドによる戻り値をバケットサイズである 10（numBuckets）で割ることでバケットの格納位置を決定しています。決定される格納位置は 0 ~ 9 の10通りなので、異なるキーでもワンチャン被ります。被った場合は、元の値は上書きされてしまいます。
実際に @ParameterizedTest した結果、get(key) した際に apple と banana はすでに上書きされてしまっていました。
HashTableTest.java
@DisplayName("既に追加されている値を取得できること")
@ParameterizedTest(name = "No.{index}: キー {0} を探すとインデックス {1} を返す")
@CsvSource(value = {
"apple, 1",
"banana, 2",
"orange, 3",
"grape, 4",
"lemon, 5"
})
void testGet(String key, Integer expected) {
assertThat(hashTable.get(key), is(expected));
}
HashTableTest.java の testGet() した際に仕込んだ bucketIndex の値
apple のbucketIndexは 0
banana のbucketIndexは 7
orange のbucketIndexは 0
grape のbucketIndexは 7
lemon のbucketIndexは 9
上記より、apple と banana が上書きされているので、5 つのパラメータでテストしたうちの 2 つは落ちてます。
衝突を回避する
変数 numBuckets にもコメントアウトで残していますが、ハッシュ表のサイズとメモリはトレードオフな関係（サイズを大きくすれば格納位置が被る可能性は低くなるけどメモリを食う）なので、ハッシュアルゴリズムのパフォーマンスを最大化するためには衝突の管理が大切になります。
衝突管理の手法には代表的なもので「チェイン法」と「オープンアドレス法」の２つがあります。
参考