MurmurHash2: различия между версиями
Перейти к навигации
Перейти к поиску
[непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
отмена правки 106440338 участника 82.193.155.250 (обс.) Метка: отмена |
отмена правки 106440333 участника 82.193.155.250 (обс.) Метка: отмена |
||
Строка 61: | Строка 61: | ||
Вторая версия хеш-функции имеет некоторые недостатки. В частности, это проблема коллизий на небольших строках. Исправленный вариант имеет структуру типа Merkle-Damgard, выполняется немного медленнее (примерно на 20 %), но показывает лучшую статистику. |
Вторая версия хеш-функции имеет некоторые недостатки. В частности, это проблема коллизий на небольших строках. Исправленный вариант имеет структуру типа Merkle-Damgard, выполняется немного медленнее (примерно на 20 %), но показывает лучшую статистику. |
||
<source lang=" |
<source lang="C"> |
||
#define mmix(h,k) { k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; } |
|||
uint32_t hash_murmur32(void *buffer, size_t length) { |
|||
unsigned int MurmurHash2A ( const void * key, int len, unsigned int seed ) |
|||
uint32_t k; |
|||
{ |
|||
const int32_t r = 24; |
|||
const unsigned int m = 0x5bd1e995; |
|||
int32_t h = length; |
|||
const int r = 24; |
|||
unsigned int l = len; |
|||
const unsigned char * data = (const unsigned char *)key; |
|||
⚫ | |||
unsigned int h = seed; |
|||
k = *(uint32_t *)data; |
|||
unsigned int k; |
|||
⚫ | |||
k *= m; |
|||
⚫ | |||
k ^= k >> r; |
|||
k |
k = *(unsigned int*)data; |
||
h |
mmix(h,k); |
||
h ^= k; |
|||
data += 4; |
data += 4; |
||
len -= 4; |
|||
} |
} |
||
unsigned int t = 0; |
|||
⚫ | |||
case 3: |
|||
⚫ | |||
⚫ | |||
{ |
|||
⚫ | |||
case 3: t ^= data[2] << 16; |
|||
⚫ | |||
h *= m; |
|||
⚫ | |||
break; |
|||
}; |
|||
case 2: |
|||
h ^= data[1] << 8; |
|||
mmix(h,t); |
|||
h ^= data[0]; |
|||
mmix(h,l); |
|||
h *= m; |
|||
break; |
|||
case 1: |
|||
h ^= data[0]; |
|||
h *= m; |
|||
break; |
|||
⚫ | |||
h ^= h >> 13; |
h ^= h >> 13; |
Версия от 22:44, 18 апреля 2020
Этой статье нужно больше ссылок на другие статьи для интеграции в энциклопедию. |
MurmurHash2 — простая и быстрая хеш-функция общего назначения, разработанная Остином Эпплби. Не является криптографически-безопасной, возвращает 32-разрядное беззнаковое число.
Из достоинств функции авторами отмечена простота, хорошее распределение, мощный лавинный эффект, высокая скорость и сравнительно высокая устойчивость к коллизиям. Текущие версии алгоритма оптимизированы под Intel-совместимые процессоры.
Пример кода
unsigned int MurmurHash2 (char * key, unsigned int len)
{
const unsigned int m = 0x5bd1e995;
const unsigned int seed = 0;
const int r = 24;
unsigned int h = seed ^ len;
const unsigned char * data = (const unsigned char *)key;
unsigned int k;
while (len >= 4)
{
k = data[0];
k |= data[1] << 8;
k |= data[2] << 16;
k |= data[3] << 24;
k *= m;
k ^= k >> r;
k *= m;
h *= m;
h ^= k;
data += 4;
len -= 4;
}
switch (len)
{
case 3:
h ^= data[2] << 16;
case 2:
h ^= data[1] << 8;
case 1:
h ^= data[0];
h *= m;
};
h ^= h >> 13;
h *= m;
h ^= h >> 15;
return h;
}
MurmurHash 2A
Вторая версия хеш-функции имеет некоторые недостатки. В частности, это проблема коллизий на небольших строках. Исправленный вариант имеет структуру типа Merkle-Damgard, выполняется немного медленнее (примерно на 20 %), но показывает лучшую статистику.
#define mmix(h,k) { k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; }
unsigned int MurmurHash2A ( const void * key, int len, unsigned int seed )
{
const unsigned int m = 0x5bd1e995;
const int r = 24;
unsigned int l = len;
const unsigned char * data = (const unsigned char *)key;
unsigned int h = seed;
unsigned int k;
while(len >= 4)
{
k = *(unsigned int*)data;
mmix(h,k);
data += 4;
len -= 4;
}
unsigned int t = 0;
switch(len)
{
case 3: t ^= data[2] << 16;
case 2: t ^= data[1] << 8;
case 1: t ^= data[0];
};
mmix(h,t);
mmix(h,l);
h ^= h >> 13;
h *= m;
h ^= h >> 15;
return h;
}