Как найти/реализовать хорошую хэш -функцию для битсет ⇐ C++

[Anonymous]

Я пытаюсь использовать Unordered_map, в котором ключ (хранящий в битсе) генерируется кодированием Мортона. Я проверил несколько случаев, когда ключ находится в диапазоне 2^0-2^6, 2^3-2^9 (последние 3 бита равны нулю), 2^6-2^12 (последние 6 бит равны нулю) и 2^9-2^15 (последние 9 битов-это нулевое). Время для поиска элемента в Unoromeded_Map для всех случаев находится в одном и том же порядке и монотонно увеличивается с размером контейнера. Я использую хэш -функцию < /p>

class my_bitset_hash
{
public:
size_t operator()(const bitset& key) const
{
size_t hashVal = 0;
hashVal = key.to_ullong();
return hashVal;
}
};
< /code>

Время для поиска элемента, когда ключ находится в диапазоне 2^9-2^15, по крайней мере два порядка величин, больше, чем когда ключ находится в диапазоне 2^0-2^6, даже если размер Unomord_MAP такой же. Насколько я знаю, если столкновения нет, потребление времени для поиска должно быть самым низким, а сложность времени должна быть O (1). Кроме того, всем случаям нужно больше времени для поиска по сравнению с теми, которые используют функцию по умолчанию.>

Подробнее здесь: https://stackoverflow.com/questions/623 ... for-bitset