[解決済み] C言語でHashMapを実装する【終了しました

2022-03-01 11:46:45

質問

C++のSTLにあるようなHashmapをCで一から作るにはどうしたらいいのでしょうか？

どのようなパラメータが考慮され、どのようにハッシュマップをテストするのでしょうか？例えば、ハッシュマップが完成したと言う前に実行するベンチマークテストはどのようなものでしょうか？

基本的なことが分かっていれば、それほど難しくはないはずです。

一般的には、キーと値を含む "buckets" という配列を作成し、オプションでポインタを追加してリンクリストを作成します。

キーでハッシュテーブルにアクセスする場合、カスタムハッシュ関数でキーを処理し、整数を返す。そして、その結果のモジュラスが、配列のインデックスやバケットの位置となる。そして、ハッシュ化されていないキーと保存されているキーを照合し、一致すれば正しい場所を見つけたことになります。

そうでない場合は、quot;collision" が発生し、リンクリストを這い回り、一致するまでキーを比較する必要があります。(衝突のためにリンクリストの代わりにバイナリツリーを使用する実装があることに注意)。

この高速なハッシュテーブルの実装をチェックしてみてください。