第１０回 連想記憶（6月23日）

今日の課題

• 連想記憶
• キーワード付き線型リスト
• ハッシュ法

■ 連想記憶

キーワードに値を対応づけて、データを管理する方法を連想記憶という。

（例） 自動車の名前と排気量の関係
  CIVIC   1.8
  S2000   2.0

■ キーワード付き線型リスト

キーワードと値をメンバ変数とする構造体を作り、線型リストに格納する方法がある。

検索キーワードを、リストの先頭からノードのキーワードと比較して、一致するところの値を出力することで、実現できる。

リストの後半のものを検索するには、そこまでのノード数だけ文字列比較(strncmp)を実行するので、効率が悪い。

□ 課題1

キーワード（文字列）と値（double）をメンバ変数とする構造体を定義し、線型リストを操作する関数一式を作成せよ。雛型を以下に示すので、不足を補うこと。

• ⇒ list.h ヘッダファイル
• ⇒ list.c ライブラリソースファイル（補完すること）
• ⇒ list1001.c 動作確認用メインプログラム
• ⇒ Makefile メイクファイル

関数 list_set は、キーワードが既に存在している場合は、値のみの書き換えを行い、新規のキーワードの場合は、push を行なう。例えば、list_set(&head,"NSX",3.0)の実行後に list_set(&head,"NSX",3.2) を実行すると、NSX のノードの 3.0 が 3.2 に書き換わる。

■ ハッシュ法

キーワードから簡単な計算で、インデックスを求めることにして、インデックスごとに線型リストを作る。

単純な線型リストは1本で長いものだったが、この方法では、それがバラバラ（ハッシュ）になっている。そこでこの手法をハッシュ法という。

ハッシュ法でにおいて、文字列からインデックスを求めるときに重要な点は、低コストでインッデックスが求まること、である。文字列毎にユニークなインデックスが求まらなくてもよいが、できるだけ、ユニークなほうがよい。

前のセクションで説明したリストの場合、検索キー「BEAT」に対応する値「0.7」を求めるために、リストの先頭から順に、ノードの文字列がキーと一致するかの文字列比較を7回する必要があった。

ハッシュの場合、「BEAT」のINDEXを計算すると、「BEAT」という文字列からINDEXの4を得るために、1回のコスト、そして、INDEX=4 のキーワード付き線型リストの先頭から検索する際に 1回のコストがかかるので、この場合、コスト=２で検索できる。

◆ ハッシュ値（インデックス）の計算

キーワード（文字列）からインデックスを計算する方法は何とおりもある。効率は悪いがわかりやすく説明をするために、ここでは、キーワードの文字コードの総和をインデックスの上限で割った余りを使うことにする。

次のプログラムを実行し、キーワードとインデックスの関係を図と比較せよ。 ⇒ list1002.c

◆ ハッシュテーブル（ハッシュの配列変数）の定義

ハッシュ法では、ある配列変数を使っており、インデックスがその配列番号となる。この配列変数をハッシュテーブルと呼ぶ。ここでは、ハッシュテーブルに、線型リストのヘッドを格納している。

Node heads[10];

配列変数のサイズを固定しないようにするには、次のようにする。

typedef struct{
  int size;
  Node *heads;
} Hash;

- - - - - -
Hash *h;

h = (Hash *)malloc(sizeof(Hash));
h->heads = (Node *)malloc(sizeof(Node)*size);
h->size = size;

◆ データの登録

1. キーからインデックスを計算する。
   （例：('F'+'I'+'T')%10=(50+53+84)%10=7）
2. ハッシュテーブルより、インデックスに対応する線型リストのヘッドを参照する。
   （例：heads[7]→S2000(2.0)→NULL）
3. リスト操作により、FIT(1.5) を挿入する。
   （例：heads[7]→FIT(1.5)→S2000(2.0)→NULL）

◆ データの検索

1. 検索キーからインデックスを計算する。
   （例：('I'+'N'+'T'+'E'+'G'+'R'+'A')%10=2）
2. ハッシュテーブルより、インデックスに対応する線型リストのヘッドを参照する。
   （例：heads[2]→CR-X(1.6)→INTEGRA(2.0)→NULL）
3. リスト操作により、検索キーと同一の文字列を持つノードを探す。
   （例：CR-X == INTEGRA の文字列比較、INTEGRA == INTEGRA の文字列比較を行う。）
4. 見つかれば、ノードのポインタを返す。見つからなければ、NULL を返す。

◆ データの削除

1. 削除キーからインデクスを計算する。
   （例：('I'+'N'+'T'+'E'+'G'+'R'+'A')%10=2）
2. ハッシュテーブルより、インデックスに対応する線型リストのヘッドを参照する。
   （例：heads[2]→CR-X(1.6)→INTEGRA(2.0)→NULL）
3. リスト操作により、検索キーと同一の文字列を持つノードを探す。
   （例：CR-X == INTEGRA の文字列比較、INTEGRA == INTEGRA の文字列比較を行う。）
4. 見つかれば、ノードの削除を行う。

□ 課題2

ハッシュ操作の関数として、ハッシュテーブルの初期化、要素の登録、要素の検索のサブルーチンを作成せよ。

• ⇒ hash.h ヘッダファイル
• ⇒ hash.c ライブラリソースファイル（補完すること）
• ⇒ list1003.c 動作確認用メインプログラム

■ 宿題

課題1および課題2を完成させよ。list.h, list.c, hash.h, hash.c, および Makefile を提出せよ。また、list1003.c の実行結果を提出せよ。

■ もっとがんばりたい人へ

リスト操作、ハッシュ操作において、要素の削除を行うためのサブルーチンを追加せよ。たとえば、hash_remove(h, "ACCORD")、list_remove_by_key(l, "ACCORD") など。list.h/c や hash.h/c にコードを書き込み、宿題のなかに含めて提出せよ。なお、「追加課題」という印を書いておくこと。実行結果は、工夫してわかりやすく示すこと。たとえば、 list1004.c を参考にせよ。

2005.6.22 by tokuhisa