🧩
【Java】ハッシュ表探索
この記事は、「新・明解Javaで学ぶアルゴリズムとデータ構造」を読んで学んだことを、個人的な備忘録目的でまとめています。
ただし、本を参考にして自分なりに構成やコードを変更しているためご注意ください。
アルゴリズムの詳細や解説は是非参考書をお手に取って読まれてください。
【リンク紹介】
・Javaで学ぶアルゴリズムとデータ構造
・これまで書いたシリーズ記事一覧
この記事は探索アルゴリズムのハッシュ表探索についてまとめました。
ハッシュ表探索
ハッシュ表探索の定義を述べる前に、必要な用語の定義を以下に記します。
ハッシュ関数
配列の各要素の値を別の値に変換する手続きをハッシュ関数(hash function)という。このとき、配列の各要素の値をキー値、ハッシュ関数によって変換された値をハッシュ値という。
衝突
異なるキー値に対して同じハッシュ値を得ることを衝突(collision)という。
衝突を考慮した２種類の手法
暗号数理的性質を持つ暗号学的ハッシュ関数では衝突が起きる可能性は極めて低いが、衝突を考慮せずにハッシュ関数を定めた場合、衝突が起こる可能性は珍しくはない。この記事では、ハッシュ表に用いるハッシュ関数をキー値を配列の要素数で割った剰余をハッシュ値とする関数と定めるが、この場合、衝突の可能性は十分に考えられるため、衝突時の対処方法を検討する必要がある。その対処方法としてチェイン法とオープンアドレス法などがあるが、この記事ではチェイン法を取り上げることとする。
ハッシュ表
ハッシュ値がインデックスとなるようにキー値を格納した配列（表）をハッシュ表という。ハッシュ表の各要素のことをバケット(bucket)という。
ハッシュ表探索
ハッシュ表において、ハッシュ表を作成したハッシュ関数を用いて目的とする値を持った要素を探し出すアルゴリズムをハッシュ表探索という。
チェイン法
同一のハッシュ値を持つ要素を線形リストで管理する手法。
チェイン法を用いた実装
ハッシュ関数による探索だけでなく、ハッシュ表の作成、データの追加、削除、表示（ダンプ）も定義したクラスを実装する
Java
//--- チェイン法 ---//
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();
}
}
}
利用例
Java
import java.util.Scanner;
public class ChainHashTester {
static Scanner stdIn = new Scanner(System.in);
//--- データ（会員番号＋氏名） ---//
static class Data {
// 定数宣言
static final int NO = 1; // 会員番号
static final int NAME = 2; // 氏名
// 変数宣言
private Integer no; // 会員番号
private String name; // 氏名
//--- キー値 ---//
Integer keyCode() {
return no;
}
//--- 文字列表現を返す ---//
public String toString() {
return name;
}
//--- データの読込み ---//
void scanData(String guide, int sw) {
System.out.println(guide + "するデータを入力してください");
if ((sw & NO) == NO) {
System.out.print("番号：");
no = stdIn.nextInt();
}
if ((sw & NAME) == NAME) {
System.out.print("氏名：");
name = stdIn.next();
}
}
}
//--- メニュー列挙型を定義 ---//
enum Menu {
ADD( "追加"),
REMOVE( "削除"),
SEARCH( "探索"),
DUMP( "表示"),
TERMINATE("終了");
private final String message; // 表示用文字列
static Menu MenuAt(int idx) {
for (Menu m : Menu.values()) {
if (m.ordinal() == idx) {
return m;
}
}
return null;
}
//--- コンストラクタ ---//
Menu(String string) {
message = string;
}
//--- 表示用文字列を返す ---//
String getMessage() {
return message;
}
}
//--- メニュー選択 ---//
static Menu SelectMenu() {
int key;
do {
for (Menu m : Menu.values()) {
System.out.printf("(%d) %s ", m.ordinal(), m.getMessage());
}
System.out.print("：");
key = stdIn.nextInt();
} while (key < Menu.ADD.ordinal() || key > Menu.TERMINATE.ordinal());
return Menu.MenuAt(key);
}
public static void main(String[] args) {
Menu menu; // メニュー
Data data; // 追加用データ参照
Data temp = new Data(); // 読込み用データ
ChainHash<Integer, Data> hash = new ChainHash<Integer, Data>(13);
System.out.println("【ハッシュ表探索】");
do {
switch (menu = SelectMenu()) {
// 追加
case ADD :
data = new Data();
data.scanData("追加", Data.NO | Data.NAME);
hash.add(data.keyCode(), data);
break;
// 削除
case REMOVE :
temp.scanData("削除", Data.NO);
hash.remove(temp.keyCode());
break;
// 探索
case SEARCH :
temp.scanData("探索", Data.NO);
Data t = hash.search(temp.keyCode());
if (t != null) {
System.out.println("そのキーをもつデータは" + t + "です");
} else {
System.out.println("該当するデータはありません。");
}
break;
// 表示
case DUMP :
hash.dump();
break;
}
} while (menu != Menu.TERMINATE);
}
}
実行結果
【ハッシュ表探索】
(0) 追加 (1) 削除 (2) 探索 (3) 表示 (4) 終了 ：0
追加するデータを入力してください
番号：14
氏名：Aさん(mod1)
(0) 追加 (1) 削除 (2) 探索 (3) 表示 (4) 終了 ：0
追加するデータを入力してください
番号：5
氏名：Bさん(mod5)
(0) 追加 (1) 削除 (2) 探索 (3) 表示 (4) 終了 ：0
追加するデータを入力してください
番号：10
氏名：Cさん(mod10)
(0) 追加 (1) 削除 (2) 探索 (3) 表示 (4) 終了 ：0
追加するデータを入力してください
番号：12
氏名：Dさん(mod12)
(0) 追加 (1) 削除 (2) 探索 (3) 表示 (4) 終了 ：0
追加するデータを入力してください
番号：1
氏名：Eさん(mod1)
(0) 追加 (1) 削除 (2) 探索 (3) 表示 (4) 終了 ：2
探索するデータを入力してください
番号：14
そのキーをもつデータはAさん(mod1)です
(0) 追加 (1) 削除 (2) 探索 (3) 表示 (4) 終了 ：3
00
01 → 1 (Eさん(mod1)) → 14 (Aさん(mod1))
02
03
04
05 → 5 (Bさん(mod5))
06
07
08
09
10 → 10 (Cさん(mod10))
11
12 → 12 (Dさん(mod12))
(0) 追加 (1) 削除 (2) 探索 (3) 表示 (4) 終了 ：4
ご協力のほどよろしくお願いします。
Discussion