c++ - How to implement a hash table with 2 keys? -
i have following problem: single value, can associated 2 different keys. example:
- uint64 key1 -> value
- uint32 key2 -> value
so query can twofold:
table.find(uint64 key1) or
table.find(uint32 key2)
key1 , key2 independent. there possibility implement 1 table having access through 2 keys without duplicating items?
one possible solution (psedocode):
class twokeyhashtable { value find(uint64); value find(uint32); insert(key1, key2, value) { insert_into_table(key1, value); insert_into_table(key2, value); } struct item { uint64 key1; uint32 key2; value value; } *table; };
however solutions doubles number of items in table. have hundreds of millions of items , want keep entire table in memory, asking if more memory efficient exists?
wow, surprised there no ideas around... :-/ implemented table, duplicating of items, follows:
class twokeyshashtable { public: struct item { uint64 key1; uint32 key2; int32 value; item() : key1(0), key2(0) { } item(uint64 k1, uint32 k2, int val) : key1(k1), key2(k2), value(val) { } }; ... item *find(uint64 key) const; item *find(uint32 key) const; int insert(uint64 key1, uint32 key2, int value); private: item *findkey1(uint64 key, int *return_index) const; item *findkey2(uint32 key, int *return_index) const; int getnextindex(int start_index, int counter) const; void rehash(); item *array_; int number_key1_; int number_key2_; int allocated_items_; };
in order not duplicate (real) data, stored in compressed array, , 'item::value' index array. 'insert' calls both 'findkey1' , 'findkey2' query if keys in table , if not, new items inserted @ returned indexes. used open hashing keep array compact possible. despite effort, table still using on 8gb of memory data (and not counting actual data, 'value' pointing to).
any ideas how more memory efficiently? thanks...
Comments
Post a Comment