Javaでハッシュテーブルを実装する

基本情報技術者試験に向けてアルゴリズムを勉強しています。今回はハッシュテーブルについてまとめます。

ハッシュテーブルとは

ハッシュテーブルはキーと値の組を記録したテーブル(表)です。以下のような表を想像してください。

Index キー
0
1 456 def
2
3 123 abc
4 789 ghi

ハッシュテーブルはキーに対する値の格納位置(Index)を工夫することにより、高速に検索が行えるようになっています。キー「123」であれば、Index3にあるとすぐに判断でき、値の取得が行えます。ハッシュテーブルは検索を高速化したい場合に用いられます。

上記の例ではIndex1にキー456、値defが、Index3にキー123、値abcが登録されています。このキーとIndexの対応は以下の計算式により求められています。

Index = キー % 5

ハッシュテーブルの実体は配列です。ただし、通常の配列と異なり、データの格納場所として添え字を直接指定するのではなく、キーを指定し、キーから計算された値を添え字とし、値を格納します。このキーから計算される値をハッシュ値、ハッシュ値を計算する関数をハッシュ関数と言います。

ハッシュ値の衝突と対策

先ほどのハッシュテーブルにキーが321の値を格納することを考えましょう。

Index キー
0
1 456 def
2
3 123 abc
4 789 ghi

キー321のハッシュ値は以下となります。

キー321のハッシュ値 = 321 % 5 = 1

1と計算されましたが、Index1にはすでにキー456が登録されています。このように、異なるキーが同じハッシュ値になることを「衝突」と言います。また、同じハッシュ値になるキーを「シノニム」と言います。

衝突が発生した場合は、以下の2つの解決方法があります。

  • オープンアドレス法
  • 連鎖法

オープンアドレス法

オープンアドレス法は衝突が発生した場合に値を格納できる別の場所を探す手法です。

例えば先ほどの例だとキー321に対する値を格納しようとしてもIndex1はすでに埋まっていますが、次のIndex2は空いています。そこで、Index1の代わりにIndex2に値を格納しようというのがオープンアドレス法のアイデアです。

52102

なお、次にキー567の値を格納しようとするとIndex2はすでに埋まっているので3→4→0と空きを探し、Index0が使われることになります。

さらに値を格納しようとするとIndex0~4はすべて埋まっているので追加することができません。このような場合、実装に利用している配列を拡張し、他の値が入るようにします。各キーが拡張後の配列のどのIndexになるかはそれぞれ計算し直す必要があります。この処理をリハッシュと言います。

連鎖法

連鎖法は衝突したキーをリストで接続する手法です。連鎖法のイメージは以下のようになります。

52104

ハッシュ値が1となるキー、456、321、876がリストで接続されています。リストを利用するため、オープンアドレス法のように満杯になるということはありません。

「キーを接続する」というのはキーになるオブジェクトに、リンクフィールドを持たせ、次のキーへの参照を保存しているということです。どうしてもイメージが湧きにくい場合は、以下のリストのアルゴリズムを参照してみてください。

Javaでリストを実装する

整数以外もキーに指定できる

ここまではキーとして整数を想定してきました。しかし、ハッシュ値を計算できればキーには整数以外を使うことも可能です。

例えば、文字列をキーとする場合、Javaでは以下のようなプログラムで文字列に対応する数値を計算できます。

String s = "abc";
int sum = 0;
for (int i = 0; i < s.length(); i++) {
    sum += s.charAt(i);
}
System.out.println(sum); 

charAtはi番目の文字を取得するメソッドです。文字には文字コードという数値が割り当てられているため、上記のプログラムでは、97(aの文字コード) + 98(bの文字コード) + 99(cの文字コード)が計算され、294という結果になります。

実装する

java.utilパッケージのHashtableクラスを参考にして実装していきます。今回は連鎖法を使います。
今回、主に実装するのは以下の2つのメソッドです。

  • void put(int key, Object value):ハッシュテーブルへデータを格納する
  • Object get(int key):ハッシュテーブルからデータを取得する

まずは、ハッシュテーブルのデータ構造を作ります。HashTableクラスを作成し、以下の内容を記述してください。

class Slot {
    int key;
    Object value;
    Slot next;
}

public class HashTable {
    private Slot[] slots;
    
    public HashTable(int size) {
        slots = new Slot[size];
    }
}

Slotはリストの各エントリを表します。このクラスにはキー(key)、値(value)、次の要素への参照(next)を含みます。

HashTableクラスはSlotクラスを配列として持ちます。これにより、ハッシュ値に対応するリストを実現します。(配列のひとつひとつがリストへの参照になります)

hashメソッドを実装する(ハッシュ値を計算する)

次にハッシュ値を計算するメソッドを実装します。HashTableクラスに以下のメソッドを追記してください。今回は単純にキーの整数値を配列の大きさで割った余りを利用します。

private int hash(int key) {
    return key % slots.length;
} 

putメソッドを実装する(ハッシュテーブルへデータを格納する)

ハッシュテーブルへデータの格納を行うputメソッドを実装します。HashTableクラスに以下のメソッドを追記してください。

public void put(int key, Object value) {
    int hash = hash(key);

    // キーが登録されているか確認
    Slot current = slots[hash];
    while (current != null) {
        // キーが登録されている場合は置き換え
        if (current.key == key) {
            current.value = value;
            return;
        }
        current = current.next;
    }

    // キーが登録されていなかった場合はリストの先頭に追加(新規リスト作成含む)
    Slot newSlot = new Slot();
    newSlot.key = key;
    newSlot.value = value;
    newSlot.next = slots[hash];
    slots[hash] = newSlot;
}

まず、hashメソッドを呼び出してハッシュ値を計算します。次に、while文でキーが既に登録されているか調べます。キーが既に登録されていれば、if文を実行し、該当するデータを書き換えてからメソッドを終了します。最後まで調べてもキーが登録されていない場合はwhile文を抜けた後に、データの追加処理に移行します。

データの追加処理では、キーが登録されていなかった場合はリストの先頭にデータを追加します。
newSlot.next = slots[hash];では、「現在リストの先頭に格納されているエントリ」と「今から追加するエントリ」を入れ替えるために、nextにリストの先頭要素への参照を格納します。
slots[hash] = newSlot;では、リストの先頭に新しく追加するデータを格納します。

getメソッドを実装する(ハッシュテーブルからデータを取得する)

探索処理を行うgetメソッドを実装します。HashTableクラスに以下のメソッドを追記してください。

public Object get(int key) {
    int hash = hash(key);
    // ハッシュ値が同じになるキーのリストを探索
    Slot current = slots[hash];
    while (current != null) {
        if (current.key == key) {
            return current.value;
        }
        current = current.next;
    }
    // キーがなかったらnullを返す
    return null;
}

まずハッシュ値を計算し、リストを探索します。キーが一致するものがあればそれを返し、リストを最後まで探索した結果、一致するものが見つからない場合はwhile文を抜けnullを返します。

toStringメソッドを実装する

動作確認のためにtoStringメソッドを実装します(System.out.println()の内容を調整します)。HashTableクラスに以下のメソッドを追記してください。

public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append('{');
    for (int i = 0; i < slots.length; i++) {
        Slot current = slots[i];
        while (current != null) {
            sb.append(current.key).append('=').append(current.value);
            sb.append(", ");
            current = current.next;
        }
    }
    sb.append('}');
    return sb.toString();
}

Slot配列のそれぞれについて、リストをたどり文字列化を行っています。
今までと異なり、最後の要素には「, 」を付けない処理は行っていません。今回の場合、一回のループではこれ以上要素がないということが判断できないため、不格好になりますが末尾処理は省略しています。

動作確認

新たに動作確認用のクラスを作成し、mainメソッドに以下のように記述します。

public static void main(String[] args) {
    HashTable hash = new HashTable(5);
    hash.put(123, "abc");
    hash.put(456, "def");
    hash.put(789, "ghi");

    Object o;
    o = hash.get(123);
    System.out.println(o);
    o = hash.get(777);
    System.out.println(o);
}

動作結果:

abc
null

参考資料
スクールの教科書