Javaで学ぶアルゴリズム -ハッシュ法（オープンアドレス法）

ハッシュ法では衝突が起きる

ハッシュ探索（オープンアドレス法）

• ハッシュアルゴリズムにおいて、異なるデータから同じ格納位置が生成されてしまう状況を「衝突」と呼ぶ
• 衝突をうまくハンドリングするための方法の１つがオープンアドレス法（クローズドハッシュ法）
  • 衝突が発生した際に再ハッシュを行うことで、データを格納する空きのバケットを見つけ出す方法
  • ハッシュテーブルのバケットが埋まったらハッシュテーブル自体を再構成して拡張する必要がある

実行環境

• JUnit 5
• Java 8

テストコード

OpenHashTest.java

import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.Matchers.nullValue;
import static org.junit.jupiter.api.Assertions.assertThrows;

public class OpenHashTest {

	private OpenHash<String, Integer> openHash;

	@BeforeEach
	void setUp() {
		openHash = new OpenHash(5);
		openHash.add("apple", 1);
		openHash.add("banana", 2);
		openHash.add("orange", 3); // appleと衝突が起きる
		openHash.add("grape", 4); // bananaと衝突が起きる
		openHash.add("lemon", 5);
	}

	@DisplayName("サイズが0以下の場合、IllegalArgumentExceptionがスローされること")
	@Test
	void testInvalidInitializationThrowsException() {
		IllegalArgumentException exception = assertThrows(IllegalArgumentException.class, () -> {
			openHash = new OpenHash(0);
		});
	}

	@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(openHash.get(key), is(expected));
	}

	@DisplayName("キーと値が空のエントリに追加されていること")
	@Test
	void testAdd() {
		openHash.add("kiwi", 6);
		assertThat(openHash.get("kiwi"), is(6));
	}

	@DisplayName("同じキーに対する値の上書きが正しく行われること")
	@Test
	void testOverwriteValue() {
		openHash.add("apple", 8);
		assertThat(openHash.get("apple"), is(8));
	}

	@DisplayName("存在しないキーを取得するとnullが返ること")
	@Test
	void testGetNonExistentKey() {
		Integer actual = openHash.get("nonexistent");
		assertThat(actual, is(nullValue()));
	}

	@DisplayName("キーを削除した後にキーを取得するとnullが返ること")
	@Test
	void testRemove() {
		openHash.remove("orange");
		assertThat(openHash.get("orange"), is(nullValue()));
	}

	@DisplayName("エントリがいっぱいのときにリサイズが正しく行われること")
	@Test
	void testResize() {
		openHash.add("kiwi", 6);
		openHash.add("melon", 7);
		openHash.add("peach", 8);
		openHash.add("strawberry", 9);
		openHash.add("blueberry", 10);
		
		// アサーションルーレットなので避けたい書き方...。
        assertThat(openHash.get("kiwi"), is(6));
		assertThat(openHash.get("melon"), is(7));
		assertThat(openHash.get("peach"), is(8));
		assertThat(openHash.get("strawberry"), is(9));
		assertThat(openHash.get("blueberry"), is(10));
	}
}

ハッシュ探索（オープンアドレス法）アルゴリズム

※ データを追加する際にバケットがいっぱいだったら拡張する仕様を追加しています

OpenHash.java

public class OpenHash<K, V> {

	enum Status {
		OCCUPIED, // 格納済み
		EMPTY, // 空
		DELETED // 削除済み
	}

	private Entry<K, V>[] table; // ハッシュ表
	private int size; // ハッシュ表のサイズ

	public OpenHash(int size) {
		if (size <= 0) {
			throw new IllegalArgumentException("Size must be greater than zero.");
		}

		table = new Entry[size];
		for (int i = 0; i < size; i++) {
			table[i] = new Entry<K, V>();
		}
		this.size = size;
	}

	/**
	 * キーのハッシュ値を返すシンプルなハッシュ関数
	 * 負のインデックスを防ぐため、絶対値を取るようabsメソッドを使用
	 *
	 * @param キー
	 * @return ハッシュ値
	 */
	private int hash(Object key) {
		return Math.abs(key.hashCode()) % size;
	}

	/**
	 * キー値がkeyである要素を探索する
	 * 見つかった場合は値を返す
	 * @param key
	 * @return value
	 */
	public V get(K key) {
		Entry<K, V> entry = searchEntry(key);
		if (entry != null) {
			return entry.getValue();
		}
		return null;
	}

	/**
	 * キー値がkeyであるEntryを探索する
	 * @param key
	 * @return value
	 */
	private Entry<K, V> searchEntry(K key) {
		int hash = hash(key);
		Entry<K, V> entry = table[hash];

		for (int i = 0; i < size; i++) {
			if (entry.status == Status.EMPTY) {
				break;
			}
			if (entry.status == Status.OCCUPIED && entry.getKey().equals(key)) {
				return entry;
			}
			hash = (hash + 1) % size;
			entry = table[hash];
		}
		return null;
	}

	/**
	 * キー値がkeyである要素を追加する
	 * 空のエントリがあれば追加し、すでにキー値が存在する場合は上書きする
	 * ハッシュ表がいっぱいの場合はリサイズしてから追加する
	 * @param key
	 * @param value
	 */
	public void add(K key, V value) {
		int hash = hash(key);
		for (int i = 0; i < size; i++) {
			int idx = (hash + i) % size;
			if (table[idx].status == Status.EMPTY || table[idx].status == Status.DELETED) {
				table[idx].set(key, value, Status.OCCUPIED); // 追加
				return;
			} else if (table[idx].status == Status.OCCUPIED && table[idx].getKey().equals(key)) {
				table[idx].set(key, value, Status.OCCUPIED); // 上書き
				return;
			}
		}
		// ここに来た時点で表がいっぱいなのでリサイズし、追加する
		resize();
		add(key, value);
	}

	/**
	 * ハッシュ表をリサイズする
	 */
	private void resize() {
		Entry<K, V>[] oldTable = table;
		int newSize = oldTable.length * 2;
		table = new Entry[newSize];

		for (int i = 0; i < newSize; i++) {
			table[i] = new Entry<>();
		}
		size = newSize;

		for (Entry<K, V> entry : oldTable) {
			if (entry.status == Status.OCCUPIED) {
				int hash = hash(entry.getKey());
				for (int i = 0; i < size; i++) {
					int idx = (hash + i) % size;
					if (table[idx].status == Status.EMPTY) {
						table[idx].set(entry.getKey(), entry.getValue(), Status.OCCUPIED);
						break;
					}
				}
			}
		}
	}

	/**
	 * キー値がkeyである要素を削除する
	 * @param key
	 */
	public void remove(K key) {
		Entry<K, V> entry = searchEntry(key);
		if (entry != null) {
			entry.set(null, null, Status.DELETED);
		}
	}

	/**
	 * ハッシュ表をダンプする（デバッグ用）
	 */
	public void dump() {
		for (int i = 0; i < size; i++) {
			System.out.printf("%d: 【%s】", i, table[i].status);
			if (table[i].status == Status.OCCUPIED) {
				System.out.printf(" %s (%s)", table[i].getKey(), table[i].getValue());
			}
			System.out.println();
		}
	}

	/**
	 * キーと値を保持するEntryクラス
	 * @param <EntryKey>
	 * @param <EntryValue>
	 */
	private class Entry<EntryKey, EntryValue> {

		private EntryKey key;
		private EntryValue value;
		private Status status;

		public Entry() {
			status = Status.EMPTY;
		}

		void set(EntryKey key, EntryValue value, Status status) {
			this.key = key;
			this.value = value;
			this.status = status;
		}

		EntryKey getKey() {
			return key;
		}

		EntryValue getValue() {
			return value;
		}
	}
}

衝突の回避

テスト内で setUp() メソッドを実行（初期化）した直後のハッシュテーブルの状態は、テストコードに dump() メソッドを追加してやることで以下のようになっていることが分かります。

setUp() 実行後の状態

0: 【OCCUPIED】 apple (1)
1: 【OCCUPIED】 orange (3)
2: 【OCCUPIED】 banana (2)
3: 【OCCUPIED】 grape (4)
4: 【OCCUPIED】 lemon (5)

衝突がハンドリングされて、ハッシュ表にまんべんなく格納されてます。

キーバリューの追加

リサイズされて kiwi さんが入る余地が生まれました。

testAdd() でキー 'kiwi' を追加

0: 【OCCUPIED】 apple (1)
1: 【OCCUPIED】 orange (3)
2: 【EMPTY】
3: 【EMPTY】
4: 【EMPTY】
5: 【EMPTY】
6: 【OCCUPIED】 kiwi (6)
7: 【OCCUPIED】 banana (2)
8: 【OCCUPIED】 grape (4)
9: 【OCCUPIED】 lemon (5)

値の更新

testOverwriteValue() でキー 'apple' の値を更新

0: 【OCCUPIED】 apple (8)
1: 【OCCUPIED】 orange (3)
2: 【OCCUPIED】 banana (2)
3: 【OCCUPIED】 grape (4)
4: 【OCCUPIED】 lemon (5)

値の削除

testRemove() でキー 'orange' を削除

0: 【OCCUPIED】 apple (1)
1: 【DELETED】
2: 【OCCUPIED】 banana (2)
3: 【OCCUPIED】 grape (4)
4: 【OCCUPIED】 lemon (5)

ハッシュ表のリサイズ

testResize() でもともとのハッシュ表のサイズ以上にたくさん追加

0: 【OCCUPIED】 apple (1)
1: 【OCCUPIED】 orange (3)
2: 【OCCUPIED】 melon (7)
3: 【OCCUPIED】 peach (8)
4: 【OCCUPIED】 strawberry (9)
5: 【OCCUPIED】 blueberry (10)
6: 【OCCUPIED】 kiwi (6)
7: 【OCCUPIED】 banana (2)
8: 【OCCUPIED】 grape (4)
9: 【OCCUPIED】 lemon (5)