如何用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個鍵實現哈希表？

回答

相關問題