【Java】オープンアドレス法を用いたハッシュ法

この記事は、「新・明解Javaで学ぶアルゴリズムとデータ構造」を読んで学んだことを、個人的な備忘録目的でまとめています。

ただし、本を参考にして自分なりに構成やコードを変更しているためご注意ください。
アルゴリズムの詳細や解説は是非参考書をお手に取って読まれてください。

【リンク紹介】
・Javaで学ぶアルゴリズムとデータ構造
・これまで書いたシリーズ記事一覧

ハッシュ法

package chap03;

public class OpenHash<K, V> {
	
	//--- バケットの状態 ---//
	enum Status {
		OCCUPIED,    // データ格納
		EMPTY,       // 空
		DELETED      // 削除済み
	};
	
	//--- バケット ---//
	static class Bucket<K, V> {
		private K      key;     // キー値
		private V      data;    // データ
		private Status stat;    // 状態
		
		Bucket() {
			stat = Status.EMPTY;    // バケットは空
		}
	
		//--- 全フィールドに値を設定 ---//
		void set(K key, V data, Status stat) {
			this.key  = key;     // キー値
			this.data = data;    // データ
			this.stat = stat;    // 状態
		}
		
		//--- 状態を設定 ---//
		void setStat(Status stat) {
			this.stat = stat;
		}
		
		//--- キー値を返す ---//
		K getkey() {
			return key;
		}
		
		//--- データを返す ---//
		V getValue() {
			return data;
		}
		
		//--- キーのハッシュ値を返す ---//
		public int hashCode() {
			return key.hashCode();
		}
	}
	
	private int            size;     // ハッシュ表の容量
	private Bucket<K, V>[] table;    // ハッシュ表
	
	//--- コンストラクタ ---//
	public OpenHash(int size) {
		try {
			table = new Bucket[size];
			for (int i = 0; i < size; i++)
				table[i] = new Bucket<K, V>();
			this.size = size;
		} catch (OutOfMemoryError e) {
			this.size = 0;
		}
	}
	
	//--- ハッシュ値を求める ---//
	public int hashValue(Object key) {
		return key.hashCode() % size;
	}
	
	//--- 再ハッシュ値を求める ---//
	public int rehashValue(int hash) {
		return (hash + 1) % size;
	}
	
	//--- バケットの探索 ---//
	private Bucket<K, V> searchNode(K key) {
		int          hash = hashValue(key);    // 探索するデータのハッシュ値
		Bucket<K, V> p    = table[hash];       // 着目バケット
		
		for (int i = 0; p.stat != Status.EMPTY && i < size; i++) {
			if (p.stat == Status.OCCUPIED && p.getkey().equals(key))
				return p;
			hash = rehashValue(hash);
			p = table[hash];
		}
		return null;
	}
	
	//--- 要素の探索 ---//
	public V search(K key) {
		Bucket<K, V> p = searchNode(key);
		if (p != null)
			return p.getValue();
		else
			return null;
	}
	
	//--- 要素の追加 ---//
	public int add(K key, V data) {
		if (search(key) != null)
			return 1;
		
		int          hash = hashValue(key);
		Bucket<K, V> p    = table[hash];
		
		for (int i = 0; i < size; i++) {
			if (p.stat == Status.EMPTY || p.stat == Status.DELETED) {
				p.set(key, data, Status.OCCUPIED);
				return 0;
			}
			
			hash = rehashValue(hash);
			p = table[hash];
		}
		return 2;
	}
	
	//--- キー値がkeyの要素の削除 ---//
	public int remove(K key) {
		Bucket<K, V> p = searchNode(key);
		if (p == null)
			return 1;
		
		p.setStat(Status.DELETED);
		return 0;
	}
	
	//--- ハッシュ表をダンプ ---//
	public void dump() {
		for (int i = 0; i < size; i++) {
			System.out.printf("%02d ", i);
			switch (table[i].stat) {
			case OCCUPIED :
				System.out.printf("%s (%s)\n",
						          table[i].getkey(),
						          table[i].getValue());
				break;
				
			case EMPTY :
				System.out.println("-- 未登録 --");
				break;
				
			case DELETED :
				System.out.println("-- 削除済み --");
				break;
			}
		}
	}

}

学習内容まとめ

eclipse操作時に役立つショートカットまとめ
https://qiita.com/toshi0383/items/1d2a990392998789062c

$\bf{\textcolor{red}{記事が役に立った方は「いいね」を押していただけると、すごく喜びます \ 笑}}$
ご協力のほどよろしくお願いします。