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;
 
  while (len >= 4)
    {
      unsigned int k;
 
      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;
 
        while(len >= 4)
        {
                unsigned int 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
            ОБРАЩЕННОМУ

Ссылки

• Хэш-функции общего назначения
• Исходные тексты хэш-функий общего назначения
• Страничка функции
• Статистика коллизий MurmurHash и ее модификация
• Статистика производительности популярных хэш-функций