Java中的快速哈希表

我創建了一個國際象棋程序，該程序利用之前評估位置的哈希表（希望）可以縮短搜索時間。唯一的問題是我使用ArrayList來存儲散列值，查找時間會根據我存儲的位置數增加。我怎樣才能得到一個查詢時間獨立於當前大小的哈希表？（原諒我，我有點在java的noob，目標c是真的我的東西）Java中的快速哈希表

編輯：如果它很重要，我使用Zobrist快速散列技術。根據一些試驗，我確定它不是佔用大量時間的哈希鍵的生成。哈希方法非常快，對速度的影響幾乎不明顯。

來源

2013-01-09 Christian Daley

使用['HashMap']（http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html）（或'HashSet'）。 –

謝謝，生病了吧 –

java.util.HashMap是你最好的選擇。重要的查找是O(1)（攤銷），它是一個非常好的通用HashMap。

這並不是說它是最優的：如果你知道如何並且有很多時間/決心，你當然可以設計一個定製的hashmap實現，以更好地適合你的特殊情況。但是一個普通的HashMap肯定是開始的地方 - 你可以隨時進行優化。

來源

2013-01-09 02:23:22 mikera

標準的Java HashMap是相當不錯的，並且已經可以使用，但是如果你想在Java中使用尖叫最快的地圖，可以使用Trove（http://trove4j.sourceforge.net/html/overview.html），它充滿了爲性能優化的數據結構。

來源

2013-01-09 02:31:18

謝謝你們，我使用了HashMap，它工作的很好！儘管它的確讓我的評價慢了一點，但緩存位置所構成的時間已經超過了它！ –

首先初步注意：在國際象棋術語中，術語transposition table比「哈希表」更常見，並且會在Google上爲您提供更好的搜索結果。

考慮到這一點，有一個置換表;以及通用哈希表之間一個重要的區別（例如，Java Map）：

地圖是一個關聯數組這保證了沒有現有條目被刪除當插入一個新值時。通常情況下，這是你想要的，但是當你編寫一個國際象棋引擎時，如果你不刪除或覆蓋舊的條目，你很快就會耗盡內存。

相比之下，轉置表更像是一個只包含最新條目的緩存。它可以作爲一個簡單的固定大小的數組來實現，該數組通過當前位置的散列值進行尋址。一個衆所周知的和非常有效的方法來計算密鑰是Zobrist hashing（你已經在你的問題中提到過）。該鍵用於索引數組。添加新條目時，它們將簡單覆蓋現有條目。

下面是一些僞代碼來說明這個想法：

// the transposition table entry 
class TTEntry { 
    long hashKey; // should be at least 64-bit to be safe 

    // other information, e.g.: 
    Move move; 
    int distance; 
    // ... 
} 

TTEntry[] ttable = ... // the more memory, the better 

Entry getTTEntry(Board board) { 
    long hashKey = board.getHashKey(); 
    int index = hashKey % ttable.length; 
    return ttable[index]; 
} 

void store(Board board) { 
    Entry entry = getTTEntry(board); 
    entry.hashKey = board.getHashKey(); 
    entry.move = ...; 
    entry.distance = ...; 
} 

void probe(Board board) { 
    Entry entry = getTTEntry(board); 
    if (entry.hashKey == hashKey) { 
    // entry found 
    // ... do something with entry.move and entry.distance 
    } 
}

你說你使用的ArrayList但你的查找時間和存儲位置的數量增加。如果你在上面的例子中使用了這種技術，那永遠不會發生。它不僅與搜索到的位置數量無關，而且還會比內部更復雜的HashMap更快。

來源

2013-01-14 23:12:37

Java中的快速哈希表

回答

相關問題