Fast Hashtable в Java

Question

Я создаю шахматную программу, которая использует хеш-таблицу ранее оцененных позиций, чтобы (надеюсь) сократить время поиска. Единственная проблема заключается в том, что я использую ArrayList для хранения значений хэша, а время поиска увеличивается в зависимости от того, сколько позиций я сохранил. Как я могу получить хеш-таблицу, у которой время поиска не зависит от текущего размера? (Простите меня, я вроде как noob в java, цель c - это действительно моя вещь)

Редактировать: Если это имеет значение, я использую технику быстрого хэширования Zobrist. Основываясь на некоторых испытаниях, я решил, что это не генерация хеш-ключей, которые занимают большое количество времени. Методы хэширования очень быстры, и его влияние на скорость почти незаметно.

Answer 1

java.util.HashMap - ваш лучший выбор. Ключевые поисковые запросы - O(1) (амортизировано), и это очень хороший HashMap общего назначения.

Это не означает, что это оптимально: вы могли бы спроектировать обычную реализацию hashmap, чтобы быть лучше для вашего частного случая, если вы знаете, как и у вас много времени/определения. Но обычный HashMap - это, безусловно, место для начала - вы всегда можете оптимизировать его позже.

Answer 2

Стандартная Java HashMap довольно хороша и уже доступна вам, но если вы хотите, чтобы критически самая быстрая карта в Java использовала Trove (http://trove4j.sourceforge.net/html/overview.html), которая заполнена структурами данных, оптимизированными для производительности.

Answer 3

Первое предварительное примечание. В шахматном жаргоне термин 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, что намного сложнее внутри.