Murmur2
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;
}
MurmurHash2 — коллизии
Коллизии для алгоритма MurmurHash2 для текста в кодировке cp866:
30f0fa9f: ПО-АВГУСТОВСКИ ПРОЛЕПЕТАЛА
3128688e: DEADSORBIMENTO ОБРАЩЕННОМУ
Напишите отзыв о статье "Murmur2"
Ссылки
- [www.partow.net/programming/hashfunctions/#RSHashFunction Хеш-функции общего назначения]
- [vak.ru/doku.php/proj/hash/sources Исходные тексты хеш-функий общего назначения]
- [sites.google.com/site/murmurhash/ Страничка функции]
- [amsoftware.narod.ru/algo.html Статистика коллизий MurmurHash и её модификация]
- [www.strchr.com/hash_functions#results Статистика производительности популярных хеш-функций]
|
Отрывок, характеризующий Murmur2
– Наташу, Наташу!.. – кричала графиня. – Неправда, неправда… Он лжет… Наташу! – кричала она, отталкивая от себя окружающих. – Подите прочь все, неправда! Убили!.. ха ха ха ха!.. неправда!Наташа стала коленом на кресло, нагнулась над матерью, обняла ее, с неожиданной силой подняла, повернула к себе ее лицо и прижалась к ней.
– Маменька!.. голубчик!.. Я тут, друг мой. Маменька, – шептала она ей, не замолкая ни на секунду.
Она не выпускала матери, нежно боролась с ней, требовала подушки, воды, расстегивала и разрывала платье на матери.
– Друг мой, голубушка… маменька, душенька, – не переставая шептала она, целуя ее голову, руки, лицо и чувствуя, как неудержимо, ручьями, щекоча ей нос и щеки, текли ее слезы.
Графиня сжала руку дочери, закрыла глаза и затихла на мгновение. Вдруг она с непривычной быстротой поднялась, бессмысленно оглянулась и, увидав Наташу, стала из всех сил сжимать ее голову. Потом она повернула к себе ее морщившееся от боли лицо и долго вглядывалась в него.
– Наташа, ты меня любишь, – сказала она тихим, доверчивым шепотом. – Наташа, ты не обманешь меня? Ты мне скажешь всю правду?
Наташа смотрела на нее налитыми слезами глазами, и в лице ее была только мольба о прощении и любви.
– Друг мой, маменька, – повторяла она, напрягая все силы своей любви на то, чтобы как нибудь снять с нее на себя излишек давившего ее горя.
И опять в бессильной борьбе с действительностью мать, отказываясь верить в то, что она могла жить, когда был убит цветущий жизнью ее любимый мальчик, спасалась от действительности в мире безумия.
Наташа не помнила, как прошел этот день, ночь, следующий день, следующая ночь. Она не спала и не отходила от матери. Любовь Наташи, упорная, терпеливая, не как объяснение, не как утешение, а как призыв к жизни, всякую секунду как будто со всех сторон обнимала графиню. На третью ночь графиня затихла на несколько минут, и Наташа закрыла глаза, облокотив голову на ручку кресла. Кровать скрипнула. Наташа открыла глаза. Графиня сидела на кровати и тихо говорила.