Эффективная структура данных для ключей Zobrist

Question

Ключи Zobrist имеют 64-битные хэшированные значения, используемые в настольных играх, чтобы однозначно представлять разные позиции, найденные во время поиска дерева. Они обычно хранятся в массивах размером 1000K или более (каждая запись имеет длину около 10 байтов). Обычно для доступа к таблице используется hashKey % size в качестве индекса. Какой контейнер STL вы использовали бы для представления такой таблицы? Учтите, что, поскольку размер таблицы ограничен, могут возникнуть столкновения. С «простым» массивом мне пришлось бы обрабатывать этот случай, поэтому я подумал о unordered_map, но поскольку реализация не указана, я не уверен, насколько она будет эффективной при заполнении карты.

Answer 1

Кажется, что стандартный хэш-файл подойдет вам хорошо - очень быстрый поиск, и он будет обрабатывать столкновения для вас надежно и незаметно.

Answer 2

Если вы хотите изучить другие территории, кроме STL, взгляните на Judy arrays: они должны соответствовать вашей проблеме.

Если вы на Linux вы можете экспериментировать с ними очень легко, просто установить из хранилища ...

This по применению может помочь решить вашу задачу.

EDIT

Существует this STL интерфейс: Я буду экспериментировать с ним, то я сообщу мои результаты.