━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
データ構造・アルゴリズム論 確認問題５
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

●問 (ハッシュ表)

リストの配列（要素数11）とハッシュ関数 h(x) ＝ x mod 11 を使い，
連鎖法に基づく簡単なハッシュ表を実現する．空のハッシュ表に対して，

        23, 5, 10, 12, 40, 25, 7, 55, 45, 29

を順に挿入する．ただし，各要素はリストの先頭に追加されるものとする．
全要素の挿入後のハッシュ表を次の形式で示せ．

         i | table[i]
        ---+----------
         0 |
         1 |
         2 |
         : |
         : |

──────────────────────────────────────

●答 (ハッシュ表)

挿入結果のハッシュ表 table は次の通り．

         i | table[i]
        ---+-----------
         0 | [55]
         1 | [45,12,23]
         2 | []
         3 | [25]
         4 | []
         5 | [5]
         6 | []
         7 | [29,7,40]
         8 | []
         9 | []
        10 | [10]

[解説]

11 で割った余りをハッシュ値(配列の添え字)として使うので，
ハッシュ表を表す配列は，添え字 0〜10 の 11 要素からなる．

挿入する各要素に対するハッシュ値は，次の通りである．

        x        | 23  5  10  12  40  25  7  55  45  29
        ---------+-------------------------------------
        x mod 11 |  1  5  10   1   7   3  7   0   1   7

ハッシュ値 1 と 7 が複数回現れるため，table[1] と table[7] で
衝突（同じ格納位置への複数のデータの割り当て）が起こる．
衝突の解消法として，この問題では，リストを使う連鎖法を採用した．
要素をリストの先頭に追加する場合には，追加したのと逆順に要素が並ぶ．

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
授業のホームページ

山田 俊行
https://www.cs.info.mie-u.ac.jp/~toshi/