возможно ли для MurmurHash3 создать 64-битный хеш, где верхние 32 бита равны 0?

Question

возможно ли для MurmurHash3 создать 64-битный хеш, где верхние 32 бита равны 0?

Смотря на https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp Я так не думаю, но я хотел проверить.

Ситуация такова, если у меня есть ключ 1,2,3 или 4 байта, надежно ли просто взять числовое значение этих байтов вместо хеширования до 8 байтов, или они вызовут коллизию для ключей больше 4 байты, которые были хешированы с шумом3?

0

c++hash murmurhash

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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

Более того, этот блог предоставляет функцию инверсии для MurmurHash:

uint64 murmur_hash_64(const void * key, int len, uint64 seed)
{
const uint64 m = 0xc6a4a7935bd1e995ULL;
const int r = 47;

uint64 h = seed ^ (len * m);

const uint64 * data = (const uint64 *)key;
const uint64 * end = data + (len / 8);

while (data != end)
{
#ifdef PLATFORM_BIG_ENDIAN
uint64 k = *data++;
char *p = (char *)&k;
char c;
c = p[0]; p[0] = p[7]; p[7] = c;
c = p[1]; p[1] = p[6]; p[6] = c;
c = p[2]; p[2] = p[5]; p[5] = c;
c = p[3]; p[3] = p[4]; p[4] = c;
#else
uint64 k = *data++;
#endif

k *= m;
k ^= k >> r;
k *= m;

h ^= k;
h *= m;
}

const unsigned char * data2 = (const unsigned char*)data;

switch (len & 7)
{
case 7: h ^= uint64(data2[6]) << 48;
case 6: h ^= uint64(data2[5]) << 40;
case 5: h ^= uint64(data2[4]) << 32;
case 4: h ^= uint64(data2[3]) << 24;
case 3: h ^= uint64(data2[2]) << 16;
case 2: h ^= uint64(data2[1]) << 8;
case 1: h ^= uint64(data2[0]);
h *= m;
};

h ^= h >> r;
h *= m;
h ^= h >> r;

return h;
}

uint64 murmur_hash_64_inverse(uint64 h, uint64 seed)
{
const uint64 m = 0xc6a4a7935bd1e995ULL;
const uint64 minv = 0x5f7a0ea7e59b19bdULL; // Multiplicative inverse of m under % 2^64
const int r = 47;

h ^= h >> r;
h *= minv;
h ^= h >> r;
h *= minv;

uint64 hforward = seed ^ (((uint64)8) * m);
uint64 k = h ^ hforward;

k *= minv;
k ^= k >> r;
k *= minv;

#ifdef PLATFORM_BIG_ENDIAN
char *p = (char *)&k;
char c;
c = p[0]; p[0] = p[7]; p[7] = c;
c = p[1]; p[1] = p[6]; p[6] = c;
c = p[2]; p[2] = p[5]; p[5] = c;
c = p[3]; p[3] = p[4]; p[4] = c;
#endif

return k;
}

Вы можете найти столько входов со значениями хеш <2^32 как ты хочешь.

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

1