2つのキーを持つハッシュテーブル

Question

2つの異なる方法でアクセスできるようにするために、大量のデータがあります。私は一定の時間を、どちらかのキー、1つのキーを用いた一定時間の挿入、および他のものとの一定時間の削除に基づいて調べることを望む。そのようなデータ構造はありますか？また、tr1にデータ構造を使用して構築することができますか？

Answer 1

2つのパラレルハッシュテーブルを使用します。削除中にすべてのキーが必要になるため、キーが要素の値の中に格納されていることを確認してください。

Answer 2

あなたはBloom Filtersを見ましたか？彼らはO（1）ではありませんが、検索を行うために必要な時間とスペースの両方でハッシュテーブルより優れていると思います。

Answer 3

なぜあなたはこれを行う必要があるのか​​分かりませんが、誰かが2つの異なるハッシュテーブルを使用しようとしていると言いました。ここで だけの擬似コード：

Hashtable inHash; 
Hashtable outHash; 

//Hello myObj example!! 
myObj.inKey="one"; 
myObj.outKey=1; 
myObj.data="blahblah..."; 

//adding stuff 
inHash.store(myObj.inKey,myObj.outKey); 
outHash.store(myObj.outKey,myObj); 

//deleting stuff 
inHash.del(myObj.inKey,myObj.outKey); 
outHash.del(myObj.outKey,myObj); 

//findin stuff 

//straight 
myObj=outHash.get(1); 

//the other way; still constant time 

key=inHash.get("one"); 
myObj=outHash.get(key); 

わからないが、あなたが探しているものthatsの。

Answer 4

これは標準的なコンテナの設計の限界の1つです。コンテナは含まれるデータを「所有」し、唯一の所有者であることを想定しています...コンテナは単に「インデックス」ではありません。 単純な、しかし100％有効ではない解決策は、値として "Node *"を持つ2つのstd ::マップを持ち、両方のキーをNode構造体に格納することです（各キーを2回格納します）。このアプローチでは、データ構造を適切なオーバーヘッドで更新することができます（余分な地図検索を行いますが、それは十分に速いはずです）。

Aおそらく「正しい」解決策は、しかしながら、IMO

struct Node 
{ 
    Key key1; 
    Key key2; 
    Payload data; 
    Node *Collision1Prev, *Collision1Next; 
    Node *Collision2Prev, *Collision2Next; 
}; 

が基本的に同時に2つの異なるハッシュテーブル内の各ノードを有するようなものであろう。

標準容器はこのように組み合わせることはできません。過去に手作業でコード化した他の例は、すべてのノードが二重リンクされたリストにあるハッシュテーブル、またはすべてのノードも配列内にあるツリーです。

非常に複雑なデータ構造（例えば、それぞれが複数のチェーンの "所有者"と同時にいくつかの他のチェーンの一部である構造のネットワーク）では、時にはコード生成に頼っていましたデータ構造の説明を与えられたコード）。