B木とハッシュ法

2分木の応用(式の表現・意思決定木)の説明が終わったので、 B木とハッシュ法の説明を行った。

B木

2分木では、ポインタの参照も頻繁に発生するし、偏った木への対応も面倒なので、 その対処方法として B木が使われる。 イメージは、2分木をそのままN要素にしただけ。

#define N 4
struct BTree {
    int           size ; // ノード内に実際に入っているデータ件数。
    int           data[ N ] ;
    struct BTree* ptr[ N+1 ] ;
                  // data[i]〜data[i+1]は、ptr[i+1]に保存
} ;

Wikipediaより引用

B木では、データの追加の際に、ノードの中央値を上のノードに組み込む 処理を行うために、木の偏りが発生しにくいようになっている。

Wikipediaより引用

B木の改良型であるB+木をさらに発展させたアルゴリズムが、 データベースエンジンで用いられている。 データベースでは、全要素シーケンシャルアクセスなどが発生するため、 B+木ではノードを横断的に移動するためのポインタを持っているのが特徴。

ハッシュ法

ここまでに説明してきた方法は、速くても であったが、もっと速いアルゴリズムは無いか？

電話番号の検索であれば、電話番号そのものが保存場所という方式であれば、 一発でデータを見つけることができるが、メモリはあまりにも無駄遣いとなる。

int tel = 272925 ;
int a[ 1000000 ] ;
a[ tel ] = tel ;

このままでは、メモリがムダだけど、電話番号であれば、50件程度ならば、 末尾2桁が同じ場合は、極めて少ない。

int a[ 100 ] ;
a[ tel % 100 ] = tel ;

この様に、データの一部分を計算処理(ハッシュ関数)で抜き出し、 その値(ハッシュ値)を保存場所とする方式は、ハッシュ法と呼ばれる。 また、異なるデータでも同じハッシュ値になる(衝突)場合があり、 この対処方法で、いろいろな方法がある。 ここでは、最も簡単な「イス取りゲームでダメなら隣りに座る」方式(オープンアドレス方)を紹介する。

// 電話番号が保存されているかを判断する
#define SIZE 100
int hash[ SIZE ] ; // 電話番号0はエントリ無しとして扱う
int hash_func( int tel ) {
    return tel % SIZE ;
}
void entry( int tel ) {
    int h = hash_func( tel ) ;
    while( hash[ h ] != 0 ) {  // 溢れると無限ループの問題あり
        h = (h + 1) % SIZE ;
    }
    hash[ h ] = tel ;
}
int search( int tel ) {
    int h = hash_func( tel ) ;
    while( hash[ h ] != 0 ) {  // 無限ループの問題あり
        if ( hash[ h ] == tel )
            return tel ; // 見つかった
        h = (h + 1) % SIZE ;
    }
    return 0 ; // 見つからない
}