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中的快速哈希表

回答

相关问题