🧩

【Java】チェイン法を用いたハッシュ法

2024/11/20に公開

Java

この記事は、「新・明解Javaで学ぶアルゴリズムとデータ構造」を読んで学んだことを、個人的な備忘録目的でまとめています。
ただし、本を参考にして自分なりに構成やコードを変更しているためご注意ください。

アルゴリズムの詳細や解説は是非参考書をお手に取って読まれてください。
【リンク紹介】

・Javaで学ぶアルゴリズムとデータ構造

・これまで書いたシリーズ記事一覧

 ハッシュ法
package chap03;

//--- チェイン法によるハッシュ ---//

public class ChainHash<K, V> {
	
	//--- ハッシュを構成するノード ---//
	class Node<K, V> {
		private K key;              // キー値
		private V data;             // データ
		private Node<K, V> next;    // 後続ポインタ
		
		//--- Node<K, V>のコンストラクタ ---//
		Node(K key, V data, Node<K, V> next) {
			this.key  = key;
			this.data = data;
			this.next = next;
		}
		
		//--- キー値を返す ---//
		K getKey() {
			return key;
		}
		
		//--- データを返す ---//
		V getValue() {
			return data;
		}
		
		//--- キーのハッシュ値を返す ---//
		public int hashCode() {
			return key.hashCode();
		}
	}
	
	private int          size;     // ハッシュ表の容量
	private Node<K, V>[] table;    // ハッシュ表を格納する配列
	
	//--- コンストラクタ ---//
	public ChainHash(int capacity) {
		try {
			table     = new Node[capacity];
			this.size = capacity;
		} catch (OutOfMemoryError e) {    // 表を作成できなかった
			this.size = 0;
		}
	}
	
	
	//--- ハッシュ値を求める ---//
	public int hashValue(Object key) {
		return key.hashCode() % size;
	}
	
	
	//--- 要素の探索 ---//
	public V search(K key) {
		int        hash = hashValue(key);    // 探索するデータのハッシュ値
		Node<K, V> p    = table[hash];       // 着目ノード
		
		while (p != null) {
			if (p.getKey().equals(key))
				return p.getValue();         // 探索成功
			p = p.next;                      // 後続ノードに着目
		}
		return null;                         // 探索失敗
	}
	
	
	//--- 要素の追加 ---//
	public int add(K key, V data) {
		int        hash = hashValue(key);    // 追加するデータのハッシュ値
		Node<K, V> p    = table[hash];       // 着目ノード
		
		while (p != null) {
			if (p.getKey().equals(key))      // このキー値は登録済み
				return 1;
			p = p.next;                      // 後続ノードの着目
		}
		
		Node<K, V> temp = new Node<K, V>(key, data, table[hash]);
		table[hash] = temp;                  // ノードを挿入
		return 0;
	}
	
	
	//--- 要素の削除 ---//
	public int remove(K key) {
		int        hash = hashValue(key);    // 削除するデータのハッシュ値
		Node<K, V> p    = table[hash];       // 着目ノード
		Node<K, V> pp   = null;              // 前回の着目ノード
		
		while (p != null) {                  // 見つけたら
			if (p.getKey().equals(key)) {
				if (pp == null)
					table[hash] = p.next;
				else
					pp.next = p.next;
				return 0;
			}
			pp = p;
			p  = p.next;                     // 後続ノードに着目
		}
		return 1;                            // そのキー値は存在しない	
	}
	
	
	//--- ハッシュ表をダンプ(表示) ---//
	public void dump() {
		for (int i = 0; i < size; i++) {
			
			Node<K, V> p = table[i];
			System.out.printf("%02d   ", i);
			
			while (p != null) {
				System.out.printf("→ %s (%s)   ", p.getKey(), p.getValue());
				p = p.next;
			}
			System.out.println();
		}
	}

}


 学習内容まとめeclipse操作時に役立つショートカットまとめ

https://qiita.com/toshi0383/items/1d2a990392998789062c
・インナークラス

・hashCodeについて
\bf{\textcolor{red}{記事が役に立った方は「いいね」を押していただけると、すごく喜びます \ 笑}}

ご協力のほどよろしくお願いします。

ハッシュ法

学習内容まとめ

Discussion