スポンサーリンク

ハッシュテーブルをc言語で実装

今回は下記のようなハッシュ関数を採用することにしました。
とてもシンプルです。
キーとなる入力文字列の各文字のアスキーコードの和を求めて、ハッシュテーブルのテーブルサイズで割った余りをハッシュ値としました。

今回はキーの衝突(異なるキーでもハッシュ値が同じになる場合にがある)を前提としています。
衝突した場合は、同じハッシュ値となったキー同士を連結リストを使って格納していきます。

参考:連結リスト(片方向)でpushとpopをc言語で実装(サンプルコードあり)

そして、ハッシュテーブルには連結リストの先頭のポインタを格納します。
下記のように宣言します。

それでは、ハッシュテーブルにキーを登録する関数です。
大まかに下記のステップで関数を実装しています。
1. キーのハッシュ値を求める
2. ハッシュ値を、ハッシュテーブルの配列のインデックスとする
3. ハッシュ値に紐付く連結リストへのポインタを取得する
※ハッシュ値で指定した要素は、連結リストの先頭のポインタとなっている
4. 連結リストを検索して、入力キーが存在するか判定
  存在しない→値を書き換え
  存在した →新規でノードを登録

続いて、キーを削除する関数です。
ハッシュテーブルに紐付く連結リストに、同じキーが存在するか検索します。
存在すればfreeして、freeした左右のノードを連結し直します。

スポンサーリンク

サンプルコード

下記がサンプルコードになります。

下記が実行結果になります。

スポンサーリンク