0

私は小さな C++ プログラムを単純な C に書き直していますmap。静的サイズのハッシュテーブル (サイズとリンクされたノード リストへのポインタの配列を含む構造) を使用しています。次の部分をCに書き直すのに苦労しています

#if 1       // switch between 1 and 0
# include <tr1/unordered_map>
  typedef std::tr1::unordered_map<std::string,int>  map_t;
#else
# include <map>
  typedef std::map<std::string,int>  map_t;
#endif

私は主にハッシュ関数を使用して順序付けされていないバージョンを実装しました。この方法で使用しました

#if 1    // switch between 1 and 0
    int hash_function(const char *key, int size);
#else
    #define hash_function(key, size) .......
#endif

しかし、テーブルを順序付けしたいので、テーブルの静的サイズがあるため、マクロがどのように見えるべきかわかりません。私はマップの経験がないので、これを実装する従来の方法があるかどうかはわかりません。

テーブルを2次元配列として、単純な行列として使用し、上から下まで列ごとに埋めるというアイデアを得ました。

繰り返しになりますが、これを行うためのより良い従来の方法はありますか?

4

1 に答える 1

1

順序付けされたハッシュマップの非常に典型的な実装は、すべての要素を順番に通過する追加のリンクリストを備えた通常のハッシュマップです。秘訣は、挿入と削除のたびにこのリンクリストを正しく維持することです。ハッシュ関数は、白黒および順序付きおよび順序なしのハッシュマップを変更しません（必要はありません）。

2D配列のアイデアの主な問題は、n*sizeOfHashTableスペースを消費し、そのほとんどが無駄になることです。

並べ替えられたマップを実装している場合は、通常、バイナリ検索ツリーなどの順序付けられたデータ構造を使用し、キー（並べ替えたもの）にも値を関連付けます。その場合、ハッシュ関数はまったく使用しません。

于 2012-04-22T21:18:53.307 に答える