如何用2个键实现哈希表？

我有一个问题：一个值，它可以与两个不同的键相关联。例如：如何用2个键实现哈希表？

UINT64 KEY1 - >值
UINT32 KEY2 - >值

因此，一个查询可以是双重的：

table.find（UINT64 KEY1）或
表。 find（uint32 key2）

key1和key2是完全独立的。有没有可能通过两个键来实现一张表而不需要重复项目？

一个可能的解决方案（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; 
};

但是这个解决方案在双打表项数。我有数以亿计的项目，并且我想将整个表保存在内存中，所以我在问是否存在更多的内存有效性？

来源

2013-08-19 Marek

欢迎来到SO！你正在谈论实现这个数据结构，但没有说明你愿意使用哪种语言。还要考虑到数以亿计的项目可能不会全部适合内存。 – idoby

C++。我已经实现了10多个专门的哈希表，所以我不会遇到低级别实现的问题。只是想法或算法就足够了...... :-) – Marek

请显示您的代码。你不可能以这种方式得到答案。 – idoby

哇，我感到奇怪的是周围没有想法...： -/ 所以我实现了表，所有项目的复制，如下所示：

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_; 
};

为了不重复（真实）数据，它存储在一个压缩数组中，'Item :: value'是该数组的索引。 'Insert'调用'FindKey1'和'FindKey2'来查询键是否已经在表中，如果没有，则新项将被插入到返回的索引处。我使用开放哈希来保持数组尽可能小巧。尽管做了所有的努力，表格仍然使用了超过8GB的内存来存储我的数据（并且我不计算实际数据，“值”指向）。

任何想法如何更有效地做到这一点？谢谢...

来源

2013-08-28 03:54:58 Marek

如何用2个键实现哈希表？

回答

相关问题