快速靜態持久哈希表

Question

我在Java中的應用程序需要一個哈希表進行計算，它必須做數以百萬計的哈希表查找。散列表必須非常快速地從磁盤讀入HashTable實用程序，並且hast表中的數據是靜態的，不需要插入或刪除。

你是否建議使用任何可用的lib來做到這一點？

此外，數據的大小小於200MB。

Answer 1

如果不需要人類可讀性，那麼可以通過gasp來確保數據實現Serializable接口並使用ObjectOutputStream序列化HashMap。這很醜，但它會完成工作。

另一種選擇是DataInputStream和DataOutputStream。這些允許您讀/寫結構化二進制數據。

讓我們假設你有一個HashMap，你可以寫這樣的：

// realOutputStream should probably be a BufferedOutputStream 
DataOutputStream output = new DataOutputStream(realOutputStream); 
for (Map.Entry<Long, String> entry : map.entrySet()) { 
    // Write the key 
    output.writeLong(entry.getKey().longValue()); 
    byte bytes[] = entry.getBytes("UTF-8"); 
    // Writing the string requires writing the length and then the bytes 
    output.writeInt(bytes.length); 
    output.write(bytes, 0, bytes.length); 
} 



// realInputStream should probably be a BufferedInputStream 
DataInputStream input = new DataInputStream (realInputStream); 
Map<Long, String> map = new HashMap<Long, String>(); 
while (true) { 
    try { 
    // read the key 
    long key = output.readLong(); 
    // read the string length in bytes 
    int strlen = output.readInt(); 
    // read the bytes into an array 
    byte buf[] = new byte[strlen]; 
    output.readFully(buf, 0, strlen); 
    // Create the map entry. 
    map.put(Long.valueOf(key), new String(buf,"UTF-8")); 
    } 
    catch (EOFException e) { 
    // input is exhausted 
    break; 
    } 
} 

請記住，這是假設你想存儲和讀取的字符串爲UTF。您可以輕鬆地不提供字符集並使用jvm默認編碼。還要注意，用的東西像一個字符串變量長度會要求你先寫實際數據之前寫數據的長度。這樣你就可以知道需要讀入多少字節才能重建該字符串。

Answer 2

如果您的數據是靜態的，爲什麼不使用普通的舊數組並通過索引查找？無論您打算使用哪種key，只需提供一個index屬性。當然，如果你超過maximum possible array length，你需要在多個陣列上分割。

我說沒有哈希函數可以打敗直接隨機存取和對您的按鍵分配指標（你的「完美散列函數」）的成本將前面，在初始化過程中，而不是對每個查詢。