Хеш-таблица с 64-битными значениями в качестве ключа

Question

У меня есть хеш-таблица, ключи которой имеют 64-битные значения.Размер таблицы может иметь различную длину степени 2, например 2, 4, 8 и т. Д. Я хочу использовать функцию хэш-таблицы, которая хорошо работает в таких случаях, то есть имеет минимальные коллизии.Например, если мне нужен размер таблицы 32, хеш-функция должна выдавать значения от 0 до 31 с минимальным коллизией для 64-битных входов.

Я нашел хорошие решения для 32-битных входов, но ни для 64битовых входов пока нет.

Для 32-битных ключей я использую эту функцию

#define hash32(x)   ( (x) * 2654435761 )

unsigned int getHashKey( unsigned long x )
{
  return hash32(x) >> ( 32 - h_bits );
}

Было бы интересно иметь хэш32 (x) эквивалентный 64-битному.

Answer 1

Эта страница (и это ) имеет несколько хеш-функций, подходящих для целых чисел.Вот один для 64-битных целых чисел:

public long hash64shift(long key)
{
  key = (~key) + (key << 21); // key = (key << 21) - key - 1;
  key = key ^ (key >>> 24);
  key = (key + (key << 3)) + (key << 8); // key * 265
  key = key ^ (key >>> 14);
  key = (key + (key << 2)) + (key << 4); // key * 21
  key = key ^ (key >>> 28);
  key = key + (key << 31);
  return key;
}

Answer 2

Кажется, это работает довольно хорошо. Он использует хеш-константу FVN для 64 бит, http://isthe.com/chongo/tech/comp/fnv/.

#define hash64(x)       ( (unsigned long)(x) * 14695981039346656037 )
#define H_BITS          4   // Hashtable size = 2 ^ 4 = 16
#define H_SHIFT_64      ( 64 - H_BITS )

unsigned int getHashKey( unsigned long x )
{
  return hash64(x) >> H_SHIFT_64;
}

Answer 3

Поиск идеальной хэш-функции подобен поиску Святого Грааля.В любом случае это зависит от значения.

Если вам нужны универсальные хеширующие функции на x86, Murmur2, Meiyan, SBox и CRC32 обеспечивают хорошую производительность для всех видов ключей.Для 64-битных значений вы также можете попробовать CityHash.

Answer 4

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

phi = 0.5 * (sqrt(5) - 1) = 0.618...

2^32 * phi = 2654435769.497...

2^64 * phi = 11400714819323198485.951...

2654435761 - это ближайшее простое число в 32-битном случае.С 64 битами это 11400714819323198549. Таким образом, алгоритм становится:

unsigned int getHashKey(unsigned long x) {
    return (x * 11400714819323198549ul) >> (64 - h_bits);
}