Hashテーブルについて
ランダムアクセスが可能なデータ構造としては配列がよく使われる。ところが、配列では添字に数値しか指定できない。これを解決するためには、文字列を指定したら添字に変換してくれる関数(ハッシュ関数)を使えば良い。Javaでは、java.util.Hashtableクラスやjava.util.HashMapクラスの内部で利用されている。
ここでは、原理を知るためにハッシュ関数をもつクラスを自作してみよう。
ハッシュ関数により計算された値は複数のキーに対して同じになる場合があり、これを衝突と呼ぶ。本来はこの対策をきちんとするべきだが簡単のため省略している。ちなみに衝突の回避方法のひとつとしては、結合リストを利用する方法があるので興味のある人は考えてみてもらいたい。
文字列からハッシュ値を生成してランダムアクセスするために、文字列の最初と真中と最後の文字から、0から999までの値に変換するhashメソッドを用意している。値(value)を格納したり、取りだすには key となる文字列をパラメータとして受け取るputメソッドやgetメソッドを使用する。Hashテーブルのイメージがつかめただろうか。
public class Hash {
private final int MODSIZE = 1000;
private Object[] values = new Object[MODSIZE];
public Object get(String key) throws Exception {
return values[hash(key)];
}
public void put(String key, Object value) throws Exception {
values[hash(key)] = value;
}
public int hash(String s) throws Exception {
int n = s.length();
if (n < 3) throw new Exception("Illegal argument"); return ( s.charAt(0)-'A'+ (s.charAt(n/2-1)-'A')*26+ (s.charAt(n-2)-'A')*26*26 ) % MODSIZE; } }
private final int MODSIZE = 1000;
private Object[] values = new Object[MODSIZE];
public Object get(String key) throws Exception {
return values[hash(key)];
}
public void put(String key, Object value) throws Exception {
values[hash(key)] = value;
}
public int hash(String s) throws Exception {
int n = s.length();
if (n < 3) throw new Exception("Illegal argument"); return ( s.charAt(0)-'A'+ (s.charAt(n/2-1)-'A')*26+ (s.charAt(n-2)-'A')*26*26 ) % MODSIZE; } }