ハッシュ法
ここまでの授業では、配列(データ検索は、登録順保存ならO(N)、２分探索ならO(log N)となる、2分探索ができるのは配列がランダムアクセスができるからこそ)、単純リスト(データ検索(シーケンシャルアクセスしかできないのでO(N)となる)、2分探索木( O(log N) ) といった手法を説明してきた。しかし、もっと高速なデータ検索はできないのであろうか？
究極のシンプルなやり方(メモリの無駄)
最も簡単なアルゴリズムは、電話番号から名前を求めるようなデータベースであれば、電話番号自身を配列添え字番号とする方法がある。しかしながら、この方法は大量のメモリを必要とする。
import java.util.*;
class PhoneName {
int phone ; // (例) 27-2925
String name ;
PhoneName( int ph , String nm ) {
this.phone = ph ;
this.name = nm ;
}
}
public class Main {
public static PhoneName[] table ;
public static void entry( int ph , String nm ) {
table[ ph ] = new PhoneName( ph , nm ) ;
}
public static String find( int ph ) {
return table[ ph ].name ;
}
public static void main(String[] args) throws Exception {
table = new PhoneName[ 1000000 ] ; // 無駄にでかい
entry( 272925 , "tsaitoh" ) ;
entry( 621111 , "nit-fukui") ;
entry( 123456 , "forger" ) ;
System.out.println( find( 621111 ) ) ;
}
}
しかし、50人程度のデータであれば、電話番号の末尾2桁を取り出した場合、同じ数値の人がいることは少ないであろう。であれば、電話番号の末尾2桁の値を配列の添え字番号として、データを保存すれば、配列サイズは100件となり、メモリの無駄を減らすことができる。
ハッシュ法
先に述べたように、データの一部を取り出して、それを配列の添え字番号として保存することで、高速にデータを読み書きできるようにするアルゴリズムはハッシュ法と呼ばれる。データを格納する表をハッシュ表、データの一部を取り出した添え字番号はハッシュ値、ハッシュ値を得るための関数がハッシュ関数と呼ばれる。
import java.util.*;
class PhoneName {
int phone ; // 27-2925
String name ;
PhoneName( int ph , String nm ) {
this.phone = ph ;
this.name = nm ;
}
}
public class Main {
public static PhoneName[] table ;
public static void entry( int ph , String nm ) {
table[ ph ] = new PhoneName( ph , nm ) ;
}
public static String find( int ph ) {
return table[ ph ].name ;
}
public static void main(String[] args) throws Exception {
table = new PhoneName[ 1000000 ] ;
entry( 272925 , "tsaitoh" ) ;
entry( 621111 , "nit-fukui") ;
entry( 123456 , "forger" ) ;
System.out.println( find( 621111 ) ) ;
}
}
ただし、上記のプログラムでは、電話番号の末尾2桁が偶然他の人と同じになることを考慮していない。
例えば、データ件数が100件あれば、同じ値の人も出てくるであろう。このように、異なるデータなのに同じハッシュ値が求まることを、ハッシュ衝突と呼ぶ。
ハッシュ関数に求められる特性
ハッシュ関数は、できる限り同じような値が求まるものは、ハッシュ衝突が多発するので、避けなければならない。例えば、6桁の電話番号の先頭2桁であれば、電話番号の局番であり、同じ学校の人でデータを覚えたら、同じ地域の人でハッシュ衝突が発生してしまう。また、ハッシュ値を計算するのに、配列の空き場所を一つ一つ探すような方式では、データ件数に比例した時間がかかり、高速なアルゴリズムとは言えない。このことから、ハッシュ関数には以下のような特徴が必要となる。
- 同じハッシュ値が発生しづらい(一見してデタラメのように見える値)
- 簡単な計算で求まること。
- 同じデータに対し常に、同じハッシュ値が求まること。
ここで改めて、異なるデータでも同じハッシュ値が求まった場合、どうすれば良いのだろうか？
ハッシュ法を簡単なイメージで説明すると、100個の椅子(ハッシュ表)が用意されていて、1クラスの学生が自分の電話番号の末尾2桁(ハッシュ関数)の場所(ハッシュ値)に座るようなもの。自分のイスに座ろうとしたら、同じハッシュ値の人が先に座っていたら、どこに座るべきだろうか？
オープンアドレス法
先の椅子取りゲームの例え話であれば、先に座っている人がいた場合、最も簡単な椅子に座る方法は、隣が空いているか確認して空いていたらそこに座ればいい。
これをプログラムにしてみると、以下のようになる。このハッシュ法は、求まったアドレスの場所にこだわらない方式でオープンアドレス法と呼ばれる。
import java.util.*;
class PhoneName {
int phone ; // 27-2925
String name ;
PhoneName( int ph , String nm ) {
this.phone = ph ;
this.name = nm ;
}
}
public class Main {
public static PhoneName[] table ;
public static int hash_func( int ph ) {
return ph % 100 ;
}
public static void entry( int ph , String nm ) {
int idx = hash_func( ph ) ;
while( table[ idx ] != null )
idx = (idx + 1) % 100 ;
table[ idx ] = new PhoneName( ph , nm ) ;
}
public static String find( int ph ) {
int idx = hash_func( ph ) ;
for( ; table[ idx ] != null ; idx = (idx + 1) % 100 )
if ( table[ idx ].phone == ph )
return table[ idx ].name ;
return null ;
}
public static void main(String[] args) throws Exception {
table = new PhoneName[ 100 ] ;
entry( 272925 , "tsaitoh" ) ;
entry( 621111 , "nit-fukui") ;
entry( 123425 , "forger" ) ;
System.out.println( find( 272925 ) ) ;
System.out.println( find( 123425 ) ) ;
}
}
注意：このプログラムは、ハッシュ表すべてにデータが埋まった場合、無限ループとなるので、実際にはもう少し改良が必要である。
この実装方法であれば、ハッシュ表にデータが少ない場合は、ハッシュ値を計算すれば終わり。よって、処理時間のオーダはO(1)となる。しかし、ハッシュ表がほぼ埋まっている状態だと、残りわずかな空き場所を探すようなもの。
文字列のハッシュ値
ここまでで説明した事例は、電話番号をキーとするものであり、余りを求めるだけといったような簡単な計算で、ハッシュ値が求められた。しかし、一般的には文字列といったような名前から、ハッシュ値が欲しいことが普通だろう。
ハッシュ値は、簡単な計算で、見た目デタラメな値が求まればいい。 (ただしく言えば、ハッシュ値の出現確率ができるだけ一様であること)。一見規則性が解らない値として、文字であれば文字コードが考えられる。複数の文字で、これらの文字コードを加えるなどの計算をすれば、 偏りの少ない値を取り出すことができる。
public static int hash_func( String nm ) {
int s = 0 ;
for( int i = 0 ; i < nm.length() ; i++ )
s += nm.charAt( i ) ;
return s % 100 ;
}
文字列順で異なる値となるように
前述のハッシュ関数は、”ABC”さんと”CBA”さんでは、同じハッシュ値が求まってしまう。文字列順で異なる値が求まるように改良してみる。
public static int hash_func( String nm ) {
int s = 0 ;
for( int i = 0 ; i < nm.length() ; i++ )
s += (nm.charAt( i ) + s * 小さい素数) % 大きい素数 ;
return s % 100 ;
}
以下の方法は、繰り返しの度に s に小さい素数を掛けることで、数値全体に文字の影響がでるようにしている。これだけだと計算途中の s の値が最終的な100個に収めるための “% 100” で下2桁に影響がでないことから、大きい素数で余りを求めてみた。この計算方法は、疑似乱数を生み出す線形合同法の考え方を参考にした。
チェイン法
前に述べたオープンアドレス法は、ハッシュ衝突が発生した場合、別のハッシュ値を求めそこに格納する。配列で実装した場合であれば、ハッシュ表のサイズ以上の データ件数を保存することはできない。
チェイン法は、同じハッシュ値のデータをグループ化して保存する方法。 同じハッシュ値のデータは、リスト構造とするのが一般的。ハッシュ値を求めたら、そのリスト構造の中からひとつづつ目的のデータを探す処理となる。
この処理にかかる時間は、データ件数が少なければ、O(1) となる。しかし、ハッシュ表のサイズよりかなり多いデータ件数が保存されているのであれば、ハッシュ表の先に平均「N/ハッシュ表サイズ」件のデータがリスト構造で並んでいることになるので、O(N) となってしまう。
import java.util.*;
class PhoneNameNode {
int phone ; // 27-2925
String name ;
PhoneNameNode next ;
PhoneNameNode( int ph , String nm , PhoneNameNode nx ) {
this.phone = ph ;
this.name = nm ;
this.next = nx ;
}
}
public class Main {
public final static int table_size = 100 ;
public static PhoneNameNode[] table ;
public static int hash_func( int ph ) {
return ph % table_size ;
}
public static void entry( int ph , String nm ) {
int idx = hash_func( ph ) ;
table[ idx ] = new PhoneNameNode( ph , nm , table[ idx ] ) ;
}
public static String find( int ph ) {
int idx = hash_func( ph ) ;
for( PhoneNameNode p = table[ idx ] ; p != null ; p = p.next )
if ( p.phone == ph )
return p.name ;
return null ;
}
public static void main(String[] args) throws Exception {
table = new PhoneNameNode[ table_size ] ;
for( int i = 0 ; i < table_size ; i++ )
table[ i ] = null ;
entry( 521125 , "tomoko" ) ;
entry( 272925 , "saitoh" ) ;
entry( 621160 , "mike" ) ;
System.out.println( find( 272925 ) ) ;
System.out.println( find( 521125 ) ) ;
}
}
理解度確認
毎年、冬休み期間中の自主的な理解度確認として、CBT を用いた理解度確認を行っています。今年も実施しますので、下記のシステムにログインし情報構造論では「ソフトウェア」(50分) を受講して下さい。
- https://cbt.kosen-ac.jp/
- 認証には、MS-365 のアカウントとパスワードでログインしてください。