CODEWITHSUNDEEP
c++data-structureshashtable
pythonic metaphor
pythonic metaphor

Reputation: 10546

Hash table with two keys

I have a large amount of data the I want to be able to access in two different ways. I would like constant time look up based on either key, constant time insertion with one key, and constant time deletion with the other. Is there such a data structure and can I construct one using the data structures in tr1 and maybe boost?

Upvotes: 3

Views: 5048

Answers (4)

6502
6502

Reputation: 114461

This is one of the limits of the design of standard containers: a container in a sense "own" the contained data and expects to be the only owner... containers are not merely "indexes". For your case a simple, but not 100% effective, solution is to have two std::maps with "Node *" as value and storing both keys in the Node structure (so you have each key stored twice). With this approach you can update your data structure with reasonable overhead (you will do some extra map search but that should be fast enough).

A possibly "correct" solution however would IMO be something like

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

basically having each node in two different hash tables at the same time.

Standard containers cannot be combined this way. Other examples I coded by hand in the past are for example an hash table where all nodes are also in a doubly-linked list, or a tree where all nodes are also in an array.

For very complex data structures (e.g. network of structures where each one is both the "owner" of several chains and part of several other chains simultaneously) I even resorted sometimes to code generation (i.e. scripts that generate correct pointer-handling code given a description of the data structure).

Upvotes: 0

Ivan Arrizabalaga
Ivan Arrizabalaga

Reputation: 685

Hard to find why you need to do this but as someone said try using 2 different hashtables. Just pseudocode in here:

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);

Not sure, thats what you're looking for.

Upvotes: 1

Ben Voigt
Ben Voigt

Reputation: 283624

Use two parallel hash-tables. Make sure that the keys are stored inside the element value, because you'll need all the keys during deletion.

Upvotes: 4

David Weiser
David Weiser

Reputation: 5195

Have you looked at Bloom Filters? They aren't O(1), but I think they perform better than hash tables in terms of both time and space required to do lookups.

Upvotes: 1

Related Questions