Хеширующая функция для трех подписи целых чисел

Question

Я пытаюсь использовать unordered_map с тремя целыми знаками в качестве ключа (это потому, что я хочу использовать tubb concurrent_unordered_map).

я соединял эту маленькую функцию (3x16-битную => 64-разрядная версия):

// to hash 

int64_t result = int16_t(x); 

result = int64_t(result << 16) + int16_t(y); 
result = int64_t(result << 16) + int16_t(z); 

// from hash 

int16_t x_ = int16_t(result >> 32); 
int16_t y_ = int16_t(result >> 16); 
int16_t z_ = int16_t(result & 0xFFFF); 

Это не работает, какая ошибка я сделал здесь?

Мое распределение чисел таково, что отрицательное или положительное число ближе к нулю более вероятно (обычно меньше +/- 2^8), но я хотел бы расширить его для работы с диапазоном до 2^32 , а не мой пример здесь. В идеале, я ищу очень мало столкновений в типичном диапазоне и предпочтительно простой алгоритм. Какие-либо предложения?

Answer 1

Ваша проблема заключается в том, что вы выполняете манипуляции с битами и добавляете на подписанные номера. Если числа отрицательные, операция сложения будет переведена в вычитание. После этого будет трудно поддразнивать правильные исходные значения.

Рассмотрим:

int16_t x = -1, y = 2, z = -3; 
int64_t result = x;   // result: FFFFFFFFFFFFFFFF 
result = (result << 16) + y; // result: FFFFFFFFFFFF0000 + 0002 
result = (result << 16) + z; // result: FFFFFFFF00020000 - 0003 
return result;    // result: FFFFFFFF0001FFFD 

Таким образом, в то время как -1 и -3 была сохранена, то результат вычитания уменьшил 2 к 1.

Вместо этого вы должны ограничить свои операции на неподписанные значения. С неподписанными значениями + и | будут эквивалентны в вашем коде, так как вы добавляете в часть номера 0.

int64_t hash() { 
    uint64_t result = uint16_t(x_); 
    result = (result << 16) + uint16_t(y_); 
    result = (result << 16) + uint16_t(z_); 
    return result; 
}