0
私はC++オープンアドレス用ハッシュテーブルを構築しています。オープンなアドレス指定ハッシュテーブル用の効率的なC++ API
の2つの特別な要素を持つキー：空と墓石の配列で構成されています。最初のスロットはスロットが空いていることに注意し、2番目のスロットはスロットが使用されたが後で削除されたことに注意するために使用されます（プロービングには必要です）。
主な課題は、この構造に効率的なAPIを設計することです。キーがハッシュされ、スロットが検索される回数を最小限に抑えたい。
これまでのところ、私は私が危険見つけ、次のAPIがあります。表はまた、
ハッシュを計算void insert(const K& key, const V& value)
、スロットの検索などの古典的な機能を持っていることを
// Return the slot index if the key is in the table
// or a slot index where I can construct the KeyValue
// if the key is not here (or -1 if there is no slot
// available and the insertion of such a key would
// need to grow the hash table)
int search(const K& key)
// Tells if the slot is empy (or if i == -1)
bool empty(int i)
// Construct a KeyValue in the HashTable in the slot i
// which has been found by search. The i might be changed
// if the table needs to grow.
void insert(const K& key, const V& value, int& i)
// Accessors for a slot i which is occupied
const V& value(int i);
注意をペアをテーブルに挿入します。しかしここでは、プログラマがテーブルを非常に効率的に使用できるようにするインターフェイスに集中したいと思います。
たとえば、f（key）が決して計算されていない場合はその値を返し、isがすでに計算されている場合はその値をHashTableから返す関数です。
const V& compute(const K& key, HashTable<K, V>& table) {
int i = table.search(key);
if (table.empty(i)) {
table.insert(key, f(key), i);
}
return table.value(i);
}
方法を挿入すると、私は（定数K &、constのV &は、&をint型）このハッシュテーブルのためのインターフェイスに完全に熱心ではないですが、私には本当に危険な感じ。
より優れたAPIについてのご意見はありますか？
PS：トーク「のアルゴリズムを使用したパフォーマンス、データ構造と効率」チャンドラーCarruthすることにより、STDの問題を理解することは本当にいいです特に午後11時50分後に:: unordered_map
は何ですか？パフォーマンス？メモリ使用量？どのような場合でも、 'std :: unordered_map'で十分でない理由を詳しく説明できますか？ – selbie
目的はperfomantハッシュテーブルを取得することです。 std :: unordered_mapの問題の1つは、リンクされたリストとの衝突を解決し、パフォーマンスの観点からは悪いことです。また、std :: unordered_mapで "compute"を書きます。 – InsideLoop
私はまた、なぜあなたが挿入した発信者に「スロットインデックス」を公開したいのか混乱しています。ハッシュテーブルの全体点は、「キー」で何かを挿入し、後で「キー」でそれを探すことができるからです。後続のルックアップのために保持している呼び出し元にスロットインデックスを返す場合は、インクリメンタルインデックスを持つフラットな配列にすることもできます。しかし、あなたが本当に望むのは、 'void Insert（k、v）'、 'void Remove（k）'、 'v Lookup（k）'の3つのメソッドを公開することだけだと思います。 – selbie