2009年 春期 応用情報技術者試験 問2

探索アルゴリズムであるハッシュ法の一つ、チェイン法に関する問題

配列に対して、データを格納すべき位置（配列の添字）をデータのキーの値を引数とする関数（ハッシュ関数）で求めることによって、探索だけではなく追加や削除も効率よく行うのがハッシュ法である。

通常、キーのとり得る値の数に比べて、配列の添字として使える値の範囲は狭いので、衝突（collision）と呼ばれる現象が起こり得る。衝突が発生した場合の対処方法の一つとして、同一のハッシュ値をもつデータを線形リストによって管理するチェイン法（連鎖法ともいう）がある。

8個のデータを格納したときの例を図1に示す。

このとき、キー値は正の整数、配列の添字は0～6の整数、ハッシュ関数は引数を7で割った剰余を求める関数とする。

このチェイン法を実現するために、表に示す構造体、配列及び関数を使用する。

構造体を参照する変数からその構造体の構成要素へのアクセスには"."を用いる。

例えば、図1のキー値25のデータはtable[4].dataでアクセスできる。また、構造体の実体を生成するには、次のように書き、生成された構造体への参照が値になる。

new Node(key, data, nextNode)

【探索関数 search】

探索のアルゴリズムを実装した関数searchの処理手順を次の(1)～(3)に、そのプログラムを図2に示す。

(1) 探索したいデータのキー値からハッシュ値を求める。 (2) ハッシュ表中のハッシュ値を添字とする要素が参照する線形リストに着目する。 (3) 線形リストのノードに先頭から順にアクセスする。キー値と同じ値が見つかれば、そのノードに格納されたデータを返す。末尾まで探して見つからなければnullを返す。

function search(key)
    hash ← hashValue(key);        // 探索するデータのハッシュ値
    node ← table[hash];           // 着目する線形リストへの参照
    while(nodeがnullでない)
        if(ア)
            return node.data;     // 探索成功
        endif
        イ;                     // 後続ノードに着目
    endwhile
    return ウ;                  // 探索失敗
endfunction

【追加関数 addNode】

データの追加手続を実装した関数addNodeの処理手順を次の(1)～(3)に、プログラムを図3に示す。図3中のア、イには、図2中のア、イと同一のものが入る。

(1) 追加したいデータのキー値からハッシュ値を求める。 (2) ハッシュ表中のハッシュ値を添字とする要素が参照する線形リストに着目する。 (3) 線形リストのノードに先頭から順にアクセスする。キー値と同じ値が見つかれば、キー値は登録済みであり追加失敗としてfalseを返す。末尾まで探して見つからなければ、リストの先頭にノードを追加してtrueを返す。

function addNode(key, data)
    hash ← hashValue(key);        // 追加するデータのハッシュ値
    node ← table[hash];           // 着目する線形リストへの参照
    while (nodeがnullでない)
        if(ア)
            return false;         // このキー値は登録済み
        endif
        イ;                     // 後続ノードに着目
    endwhile
    tempNode ← new Node(エ);   // ノードを生成
    オ ← tempNode;              // ノードを追加
    return true;
endfunction

【チェイン法の計算量】

チェイン法の計算量を考える。

計算量が最悪になるのは、カ場合である。しかし、ハッシュ関数の作り方が悪くなければ、このようなことになる確率は小さく、実際上は無視できる。

チェイン法では、データの個数をnとし、表の大きさ（配列の長さ）をmとすると、線形リスト上の探索の際にアクセスするノードの数は、線形リストの長さの平均n/mに比例する。mの選び方は任意なので、nに対して十分に大きくとっておけば、計算量がキとなる。この場合の計算量は2分探索木による0(log n)より小さい。