Javaで学ぶアルゴリズム -ハッシュ法（チェイン法）

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

ハッシュ探索（チェイン法）

• ハッシュアルゴリズムにおいて、異なるデータから同じ格納位置が生成されてしまう状況を「衝突」と呼ぶ
• 衝突をうまくハンドリングするための方法の１つがチェイン法（オープンハッシュ法）
• 同一ハッシュ値を持つデータを線形リストとして鎖状につなぐことでデータを保持しておく

実行環境

• JUnit 5
• Java 8

テストコード

ChainHashTest.java

import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.Matchers.nullValue;

public class ChainHashTest {

	private ChainHash<String, Integer> chainHash;

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

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

	@DisplayName("衝突をハンドリングして、既に追加されている値を取得できること")
	@ParameterizedTest(name = "No.{index}: キー {0} を探すと値 {1} を返す")
	@CsvSource(value = {
			"apple, 1",
			"banana, 2",
			"orange, 3",
			"grape, 4",
			"lemon, 5"
	})
	void testSearch(String key, Integer expected) {
		assertThat(chainHash.search(key), is(expected));
	}

	@DisplayName("キーと値が追加されていること")
	@Test
	void testAdd() {
		chainHash.add("kiwi", 6);
		assertThat(chainHash.search("kiwi"), is(6));
	}

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

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

	@DisplayName("キーと値が削除されていること")
	@Test
	void testRemove() {
		chainHash.remove("orange");
		assertThat(chainHash.search("orange"), is(nullValue()));
	}
}

ハッシュ探索（チェイン法）アルゴリズム

public class ChainHash<K, V> {

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

	public ChainHash(int capacity) {
        if (capacity <= 0) {
			throw new IllegalArgumentException("Size must be greater than zero.");
		}
		buckets = new Node[capacity];
		this.size = capacity;
	}

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

	/**
	 * キー値がKeyである要素を探索し、値を返す
	 * 存在しない場合は null を返す
	 * @param key
	 * @return value
	 */
	public V search(K key) {
		int hash = hash(key);

		Node<K, V> p = buckets[hash];
		while (p != null) {
			if (key.equals(p.getKey())) {
				return p.getValue();
			}
			p = p.next;
		}
		return null;
	}

	/**
	 * キー値がKeyで値がvalueである要素を追加する
	 * 既に同一のキーが存在している場合は値を上書きする
	 * @param key
	 * @param value
	 */
	public void add(K key, V value) {
		int hash = hash(key);
		Node<K, V> p = buckets[hash];

		while (p != null) {
			if (key.equals(p.getKey())) {
				p.value = value;
				return;
			}
			p = p.next;
		}

		Node<K, V> temp = new Node(key, value, buckets[hash]);
		buckets[hash] = temp;
	}

	/**
	 * キー値がKeyである要素を削除する
	 * @param key
	 */
	public void remove(K key) {
		int hash = hash(key);
		Node<K, V> p = buckets[hash];
		Node<K, V> pp = null;

		while (p != null) {
			if (key.equals(p.getKey())) {
				if (pp == null) {
					buckets[hash] = p.next;
				} else {
					pp.next = p.next;
				}
			}
			pp = p;
			p = p.next;
		}
	}

	/**
	 * ハッシュ表をダンプする（デバッグ用）
	 */
	public void dump() {
		for (int i = 0; i < size; i++) {
			Node<K, V> p = buckets[i];
			System.out.printf("%02d  ", i);
			while (p != null) {
				System.out.printf("-> %s (%s)  ", p.getKey(), p.getValue());
				p = p.next;
			}
			System.out.println();
		}
	}

	/**
	 * ハッシュ表内でキーと値のペアを格納するための基本単位
	 * @param <NodeKey>
	 * @param <NodeValue>
	 */
	private class Node<NodeKey, NodeValue> {

		private NodeKey key;
		private NodeValue value;
		private Node next; // ポインタ

		public Node(NodeKey key, NodeValue value, Node<NodeKey, NodeValue> next) {
			this.key = key;
			this.value = value;
			this.next = next;
		}

		NodeKey getKey() {
			return key;
		}

		NodeValue getValue() {
			return value;
		}
	}
}

衝突の回避

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

setUp() 実行後の状態

00  -> orange (3)  -> apple (1)  
01  
02  
03  
04  
05  
06  
07  -> grape (4)  -> banana (2)  
08  
09  -> lemon (5)  

衝突がハンドリングされて、同じインデックスに複数のキーバリューが同居できてます。

キーバリューの追加

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

00  -> orange (3)  -> apple (1)  
01  
02  
03  
04  
05  
06  -> kiwi (6)  
07  -> grape (4)  -> banana (2)  
08  
09  -> lemon (5)  

値の更新

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

00  -> orange (3)  -> apple (8)  
01  
02  
03  
04  
05  
06  
07  -> grape (4)  -> banana (2)  
08  
09  -> lemon (5)  

値の削除

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

00  -> apple (1)  
01  
02  
03  
04  
05  
06  
07  -> grape (4)  -> banana (2)  
08  
09  -> lemon (5)