Алгоритмы общего назначения

Простые хэш-функции высокой производительности

Уже знакомы с первым выпуском? Таки второй вышел!

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

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

Зачем все это? Да, как правило, распространены либо сугубо статистические тесты, методика которых схожа с методикой тестирования генераторов псевдослучайных чисел и поточных шифров, либо тесты на одном наборе информации. Но говорить о хэш-функции как о хорошей сложно, исходя из одного теста. Более того, такую функцию можно просто оптимизировать под определенный набор данных, строки определенной длины или в определенном промежутке символов. Один тест может не выявить слабые места алгоритма. Здесь же вы найдете комплексное и мощное тестирование на богатом наборе тестового материала. Все это, возможно, приведет к самым неожиданным результатам.

Приступим к тестированию.

Тестовый набор содержит слова, отсортированные в алфавитном порядке, дубликаты удалены. В качестве основы были взяты заголовки из Русской Википедии, Большой советской энциклопедии, Большого англо-русского словаря и других словарных источников в общем колличестве 2726299 уникальных слова. Важно отменить, что все тексты - в кодировке cp866, минимальная длина - 3 символа, регистр - верхний. Тестовый набор можно скачать здесь или здесь. Инструментарий тестирования, который включает исходные тексты всех алгоритмов, можно найти здесь. Результаты тестов в виде электронной таблицы можно найти здесь.

Порядок тестово таков: хэшируем все слова в текстовом файле, сортируем результаты, находим коллизии. Чем меньше дубликатов, тем лучше алгоритм хэширования, поскольку идентичных слов в тестовом наборе у нас нет.

Описание вариантов теста:

• Тест A: простое хэширование
• Тест B: добавляем символ конца строки к слову
• Тест C: добавляем четыре символа конца строки к слову
• Тест D: добавляем к слову пять символов ABCDE
• Тест E: добавляем к слову его дубликат
• Тест F: добавляем к слову его три дубликата
• Тест G: изменяем порядок символов в слове на обратный
• Тест H: делаем из слова его палиндром

MaHash7

Что отличает эту функцию? Правильно, бросается в глаза таблица замены (подстановки). Зачем она в таком простом алгоритме? Прежде всего затем, что таблица замены - это сложная функция, которую просто описали несколько иным способом. При этом такую функцию очень легко реализовать как программно, так и аппаратно, скорость запроса к таблице высока в обоих случаях. У функции есть параметр - число итераций. Статистически, лучшим параметром будет одна итерация для большинства текстов. Хотя для оригинальной функции оптимальными будут три итерации. Сама таблица подстановки идентична таковой в криптоалгоритме Skipjack. Результаты не лучшие, но конструкция имеет право на жизнь.

static const unsigned char sTable[256] =
{
  0xa3,0xd7,0x09,0x83,0xf8,0x48,0xf6,0xf4,0xb3,0x21,0x15,0x78,0x99,0xb1,0xaf,0xf9,
  0xe7,0x2d,0x4d,0x8a,0xce,0x4c,0xca,0x2e,0x52,0x95,0xd9,0x1e,0x4e,0x38,0x44,0x28,
  0x0a,0xdf,0x02,0xa0,0x17,0xf1,0x60,0x68,0x12,0xb7,0x7a,0xc3,0xe9,0xfa,0x3d,0x53,
  0x96,0x84,0x6b,0xba,0xf2,0x63,0x9a,0x19,0x7c,0xae,0xe5,0xf5,0xf7,0x16,0x6a,0xa2,
  0x39,0xb6,0x7b,0x0f,0xc1,0x93,0x81,0x1b,0xee,0xb4,0x1a,0xea,0xd0,0x91,0x2f,0xb8,
  0x55,0xb9,0xda,0x85,0x3f,0x41,0xbf,0xe0,0x5a,0x58,0x80,0x5f,0x66,0x0b,0xd8,0x90,
  0x35,0xd5,0xc0,0xa7,0x33,0x06,0x65,0x69,0x45,0x00,0x94,0x56,0x6d,0x98,0x9b,0x76,
  0x97,0xfc,0xb2,0xc2,0xb0,0xfe,0xdb,0x20,0xe1,0xeb,0xd6,0xe4,0xdd,0x47,0x4a,0x1d,
  0x42,0xed,0x9e,0x6e,0x49,0x3c,0xcd,0x43,0x27,0xd2,0x07,0xd4,0xde,0xc7,0x67,0x18,
  0x89,0xcb,0x30,0x1f,0x8d,0xc6,0x8f,0xaa,0xc8,0x74,0xdc,0xc9,0x5d,0x5c,0x31,0xa4,
  0x70,0x88,0x61,0x2c,0x9f,0x0d,0x2b,0x87,0x50,0x82,0x54,0x64,0x26,0x7d,0x03,0x40,
  0x34,0x4b,0x1c,0x73,0xd1,0xc4,0xfd,0x3b,0xcc,0xfb,0x7f,0xab,0xe6,0x3e,0x5b,0xa5,
  0xad,0x04,0x23,0x9c,0x14,0x51,0x22,0xf0,0x29,0x79,0x71,0x7e,0xff,0x8c,0x0e,0xe2,
  0x0c,0xef,0xbc,0x72,0x75,0x6f,0x37,0xa1,0xec,0xd3,0x8e,0x62,0x8b,0x86,0x10,0xe8,
  0x08,0x77,0x11,0xbe,0x92,0x4f,0x24,0xc5,0x32,0x36,0x9d,0xcf,0xf3,0xa6,0xbb,0xac,
  0x5e,0x6c,0xa9,0x13,0x57,0x25,0xb5,0xe3,0xbd,0xa8,0x3a,0x01,0x05,0x59,0x2a,0x46
};




#define LROT14(x) (((x) << 14) | ((x) >> 18 ))

#define ITERATIONS 1

unsigned int
MaHash7 (unsigned char *str, unsigned int len)
{
  unsigned int hash = len, i;

  for (i = 0; i != len * ITERATIONS; i++)
    {

     str += (i % len);      

      hash =
        LROT13 (hash + ((hash << 8) ^ (hash >> 12))) -
        sTable[(*str + i) & 255];

    }

  return hash;
}

MaHash9

Что изменено? Другие константы сдвигов и циклический сдвиг влево на 14 бит, дополнительная операция побитового НЕ. Как результат - немного лучше показатели в ряде тестов, но в итоге изменения себя не оправдали. В итоге - далеко не первое место, так же - твердый середнячок.

#define LROT14(x) (((x) << 14) | ((x) >> 18 ))

unsigned int MaHash9 (unsigned char *str, unsigned int len)
{
    unsigned int hash = len, i;

    for (i = 0; i != len; i++, str++)
    {

        hash = LROT14( ~hash + ((hash << 6) ^ (hash >> 11))) - sTable[(*str + i) & 255];

    }

    return hash;
}

MaHash2

Что же здесь нового? По-сути, это два алгоритма MaHash для параллельного подсчета двух 32-разрядных значений. На каждом этапе результат вычисления оригинальной и видоизмененной функции с обратным циклическим сдвигом вправо взаимозаменяются. Результатом хэш-функции будет сумма подфункций по модулю 2 (операция XOR). Такая конструкция позволила улучшить результаты алгоритма в плане числа коллизий. Достоинства алгоритма - отсутствие операций деления, умножения (наиболее медленных на современных неспециализированных процессорах) и возможность распараллеливания. С неба звезд не хватает, но показывает сравнительно хорошие результаты - восьмое место в рейтинге с небольшим отставанием от ближайших соперников.

#define LROT(x) (((x) << 11) | ((x) >> 21 ))
#define RROT(x) (((x) << 21) | ((x) >> 11 ))


unsigned int MaHash2 (unsigned char *str, unsigned int len)
{
    unsigned int t, hash1 = len, hash2 = len, i;
    for (i = 0; i != len; i++, str++)
    {

        hash1 += sTable[(*str + i) & 255];
        hash1 = LROT(hash1 + ((hash1 << 6) ^ (hash1 >> 8)));
        hash2 += sTable[(*str + i) & 255];
        hash2 = RROT(hash2 + ((hash2 << 6) ^ (hash2 >> 8)));

        t = hash1;
        hash1 = hash2;
        hash2 = t;

    }



    return hash1 ^ hash2;
}

MaHash8

Найдем отличия? Изменились сдвиги, циклический сдвиг увеличился не несколько разрядов. На смену взаимозамены результатов подфункций теперь они “собираются” из младшего родного слова и старшего слова альтернативной функции. Показал в среднем лучшие среди участников результаты.

#define LROT14(x) (((x) << 14) | ((x) >> 18 ))
#define RROT14(x) (((x) << 18) | ((x) >> 14 ))



unsigned int MaHash8 (unsigned char *str, unsigned int len)
{
    unsigned int sh1, sh2, hash1 = len, hash2 = len, i;
    for (i = 0; i != len; i++, str++)
    {

        hash1 += sTable[(*str + i) & 255];
        hash1 = LROT14(hash1 + ((hash1 << 6) ^ (hash1 >> 11)));
        hash2 += sTable[(*str + i) & 255];
        hash2 = RROT14(hash2 + ((hash2 << 6) ^ (hash2 >> 11)));     
	   
        sh1 = hash1;
        sh2 = hash2;
		
        hash1 = ((sh1 >> 16) & 0xffff) | (sh2 & 0xffff) << 16;
        hash2 = ((sh2 >> 16) & 0xffff) | (sh1 & 0xffff) << 16;

    }



    return hash1 ^ hash2;
}

MaHash4

Вернулись обратно? Да, здесь опять классические сдвиги и обычный циклический сдвиг. Только вместо взаимозамены опять “сборка” значений. Эта функция, как и прошлая, стабильно показывает очень хорошие результы, не имеет “провалов”. Не даром заняла второе место в общем зачете и победила в сокращенном тесте.

#define LROT(x) (((x) << 11) | ((x) >> 21 ))


unsigned int
MaHash4 (unsigned char *str, unsigned int len)
{
  unsigned int sh1, sh2, hash1 = len, hash2 = len, i;
  for (i = 0; i != len; i++, str++)
    {

      hash1 += sTable[(*str + i) & 255];
      hash1 = LROT (hash1 + ((hash1 << 6) ^ (hash1 >> 8)));
      hash2 += sTable[(*str + i) & 255];
      hash2 = RROT (hash2 + ((hash2 << 6) ^ (hash2 >> 8)));

      sh1 = hash1;
      sh2 = hash2;

      hash1 = ((sh1 >> 16) & 0xffff) | (sh2 & 0xffff) << 16;
      hash2 = ((sh2 >> 16) & 0xffff) | (sh1 & 0xffff) << 16;

    }



  return hash1 ^ hash2;
}

MaHash5

Усложнили? Да, немного. Добавлено дополнительное преобразование в конце шага. Результаты стабильны для обоих тестов, хотя в сравнении с прошлой функцией усложнение, которое немного улучшило результат первого теста, не оправдано. Как результат, пятое место в зачете и фактическая несостоятельность.

#define LROT(x) (((x) << 11) | ((x) >> 21 ))


unsigned int
MaHash5 (unsigned char *str, unsigned int len)
{
  unsigned int sh1, sh2, hash1 = len, hash2 = len, i;
  for (i = 0; i != len; i++, str++)
    {

      hash1 += sTable[(*str + i) & 255];
      hash1 = LROT (hash1 + ((hash1 << 6) ^ (hash1 >> 8)));
      hash2 += sTable[(*str + i) & 255];
      hash2 = RROT (hash2 + ((hash2 << 6) ^ (hash2 >> 8)));

      sh1 = LROT (hash1 + ((hash1 << 6) ^ (hash1 >> 8)));
      sh2 = RROT (hash2 + ((hash2 << 6) ^ (hash2 >> 8)));

      hash1 = ((sh1 >> 16) & 0xffff) | (sh2 & 0xffff) << 16;
      hash2 = ((sh2 >> 16) & 0xffff) | (sh1 & 0xffff) << 16;

    }



  return hash1 ^ hash2;
}

MaHash11

Знакомо? Да, ведь это MaHash2 с другими константами сдвигов. Причем, теперь для каждой подфункции теперь применяется свое значение циклического сдвига. Показала себя очень хорошо, без резких счачков коллизий в сложных наборах. Третье место в нашем рейтинге.

#define LROT12(x) (((x) << 12) | ((x) >> 20 ))
#define RROT13(x) (((x) << 19) | ((x) >> 13 ))


unsigned int MaHash11 (unsigned char *str, unsigned int len)
{
    unsigned int t, hash1 = len, hash2 = len, i;
    for (i = 0; i != len; i++, str++)
    {

        hash1 += sTable[(*str + i) & 255];
        hash1 = LROT12(hash1 + ((hash1 << 6) ^ (hash1 >> 14)));
        hash2 += sTable[(*str + i) & 255];
        hash2 = RROT13(hash2 + ((hash2 << 6) ^ (hash2 >> 14)));

        t = hash1;
        hash1 = hash2;
        hash2 = t;

    }



    return hash1 ^ hash2;
}

MaHash10

Что-то новенькое ? Не совсем, но стоит особняком, выделяется немного новой структурой. Здесь уже нет двух параллельных подфункций, хотя и вычисляются два 32-разядных значения на каждом шаге. Как и впрошлой функции, циклические сдвиги различны для каждого вычисления. Как оказалась, такая конструкция имеет небольшие всплески коллизий и от классической пока отсказываться спешить не следует. Из всего семейства показала худший результат, хотя и опередила некоторых именитых соперников.

#define LROT14(x) (((x) << 14) | ((x) >> 18 ))
#define RROT14(x) (((x) << 18) | ((x) >> 14 ))


unsigned int MaHash10 (unsigned char *str, unsigned int len)
{
    unsigned int hash1 = len, hash2 = len, i, value;
    for (i = 0; i != len; i++, str++)
    {


        value = sTable[(*str + i) & 255];
        hash1 =  LROT14(hash2 + ((hash2 << 6) ^ (hash2 >> 11)));
        hash1 += value;
        hash2 =  RROT15(hash1 + ((hash1 << 6) ^ (hash1 >> 11)));
        hash2 += value;


    }



    return hash1 ^ hash2;
}

MaHash3

Опять усложняем ? И не зря. Как показали тесты, функция - одна из самых удачных в семействе. Дополнительная интерация немного снизила число коллизий на самых сложных тестах.

#define LROT(x) (((x) << 11) | ((x) >> 21 ))
#define RROT(x) (((x) << 21) | ((x) >> 11 ))

unsigned int
MaHash3 (unsigned char *str, unsigned int len)
{
  unsigned int t, hash1 = len, hash2 = len, i;
  unsigned char index;

  for (i = 0; i != len; i++, str++)
    {

      index = (*str + i) & 255;

      hash1 += sTable[index];
      hash1 = LROT (hash1 + ((hash1 << 6) ^ (hash1 >> 8)));
      hash2 += sTable[(sTable[index] + 1) & 255];
      hash2 = RROT (hash2 + ((hash2 << 6) ^ (hash2 >> 8)));
      t = hash1;
      hash1 = hash2;
      hash2 = t;

    }

  hash1 = LROT (hash1 + ((hash1 << 6) ^ (hash1 >> 8)));
  hash1 += sTable[len];
  hash2 = RROT (hash2 + ((hash2 << 6) ^ (hash2 >> 8)));
  hash2 += sTable[len];


  return hash1 ^ hash2;
}

MaBKDR

Говорят, существующие алгоритмы не улучшишь? Пусть говорят. У BKDR есть небольшой недостаток, он хорош на строках одной длины - на больших объемах текстов различной длины число коллизий увеличивается. Это легко исправить, просто добавляем счетчик символа на каждом шаге. Такая модификация, как показали исследования, значительно улучшит статистические показатели, снизив число столкновений. В то же время никаких деградаций функции по результатам тестов мной замечено не было. Значит, модификация имеет право на жизнь и такой вариант предпочтительнее оригинальной функции. И, что важно, добавлена лишь одна операция, которая выполняется быстро на современных процессорах.

unsigned int
maBKDRHash (unsigned char *str, unsigned int len)
{
  unsigned int seed = 131313;   /* 31 131 1313 13131 131313 etc.. */
  unsigned int hash = 0;
  unsigned int i = 0;

  for (i = 0; i < len; str++, i++)
    {
      hash = (hash * seed) + *str + /* maBKDR modification here*/ i;
    }
  return hash;
}

MaPrime

Простые числа? Они самые. Существующие простые хэш-функции на простых числах немного деградируют в сложных случаях, судя по моим тестам. Такие случаи - это наборы текстов, имеющие совпадающие участки. Более точно - это потому, что алгоритмы не предусмотрели четкой взаимосвязи между символом и его позицией в строке. Наш алгоритм очень прост, основан на операции умножения на простое число. Используется таблица подстановки, так же что и в других моих функциях. Как вариант, может использоваться упрощенный вариант без таблицы. Преимущества - элементарная и понятная структура, простота реализации и хорошие результаты во всех тестах.

#define PRIME_MULT 0x1FAF
#define START_PRIME 0x3A8F05C5
#define USE_SBOX


unsigned int maPrimeHash (unsigned char *buf, unsigned int len)
{
    unsigned int hval = START_PRIME, i;

    for (i = 0; i != len; i++, buf++)
    {

#ifdef USE_SBOX
        hval ^= sTable[(*buf +  i) & 255];
#else
        hval += ((unsigned int)*buf)  ^  i;
#endif
        hval *= PRIME_MULT;

    }

    return hval;
}

MaPrime2c

Брат-близнец? Конечно. И найти отоличия сложно. Этот алгоритм отличается константой, на которую умножается внутреннее состояние, и тем, что его стартовым значением является не фиксированное число, а длина сообщения. Результаты тоже не плохие. По соотношению качества хэширования и производительности это лучшая из моих функций.

#define PRIME_MULT 1717


unsigned int
maPrime2cHash (unsigned char *str, unsigned int len)
{
  unsigned int hash = len, i;


  for (i = 0; i != len; i++, str++)
    {

      hash ^= sTable[( *str + i) & 255];
      hash = hash * PRIME_MULT;
    }

  return hash;
}

MaPrime2d

Какой смысл опять усложнять? Он, определенно есть. Как показали автоматизированные тесты, функция показывает более стабильные результаты, нежели оригинальная. Да и дополнения не так сильно отражаются на производительности. Второй момент - это возможность параметризации, т.е. тонкой натройки под определенный набор данных. Существенный параметр здесь - это константа циклического сдвига. В тесте использован сдвиг на два бита вправо, что обеспечило усредненные результаты по тестам вцелом, однако использование некоторых других значений может быть более приемлимым в зависимости от набора текстов. К примеру - один или три бита.

unsigned int
maPrime2dHash (unsigned char *str, unsigned int len)
{
  unsigned int hash = 0, i;
  unsigned int rotate = 2;
  unsigned int seed = 0x1A4E41U;


  for (i = 0; i != len; i++, str++)
    {
      
      hash += sTable[(*str + i) & 255];
      hash = (hash << (32 - rotate) ) | (hash >> rotate);
      hash = (hash + i ) * seed;

    }


  return (hash + len) * seed;
}

MaHash8v64

Где-то уже видели эту функцию? Конечно, видели. Это - двойник алгоритма MaHash8, только теперь функция возвращает 64-разрядный хэш, тоесть оба 32-разрядных значения, не сжимая из в одно. Сам алгоритм полностью 32-разрядный, скорость его не уменьшилась. Такую манимуляцию можно провести со всеми алгоритмами семейства, в которых структура - это две подфункции. Достоинства алгоритма - высокая скорость, равная алгоритму с 32-разрядным хэшем, простота реализации и очень хорошие показатели по числу коллизий. Функция, безусловно, лидер в нашем забеге, хотя участвует вне конкурса - ведь хэш в два раза больше, чем у других участников.

Для увеличения лавинного эффекта можно использовать простую модификацию с дополнительным преобразованием финального 64-битного значения.

#define LROT14(x) (((x) << 14) | ((x) >> 18 ))
#define RROT14(x) (((x) << 18) | ((x) >> 14 ))

#ifdef HIAVAL
#define LROT64(x) (((x) << 29) | ((x) >> 34 ))
#endif

unsigned long long
MaHash8v64 (unsigned char *str, unsigned int len)
{
  unsigned int sh1, sh2, hash1 = len, hash2 = len, i;
  unsigned long long digest;

  for (i = 0; i != len; i++, str++)
    {

      hash1 += sTable[( *str + i) & 255];
      hash1 = LROT14 (hash1 + ((hash1 << 6) ^ (hash1 >> 11)));
      hash2 += sTable[( *str + i) & 255];
      hash2 = RROT14 (hash2 + ((hash2 << 6) ^ (hash2 >> 11)));

      sh1 = hash1;
      sh2 = hash2;

      hash1 = ((sh1 >> 16) & 0xffff) | ((sh2 & 0xffff) << 16);
      hash2 = ((sh2 >> 16) & 0xffff) | ((sh1 & 0xffff) << 16);

    }


#ifdef HIAVAL
  digest = (((unsigned long long) hash1) << 32)  | ((unsigned long long) hash2 );
  digest ^= LROT64(digest + ((digest << 13) ^ (digest >> 23)));
#else
  digest = (((unsigned long long) hash2) << 32)  | ((unsigned long long) hash1 );
#endif

  return digest;
}

MaHash4v64

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

#define LROT(x) (((x) << 11) | ((x) >> 21 ))
#define RROT(x) (((x) << 21) | ((x) >> 11 ))

#ifdef HIAVAL
#define LROT64(x) (((x) << 29) | ((x) >> 34 ))
#endif

unsigned long long
MaHash4v64 (unsigned char *str, unsigned int len)
{
  unsigned int sh1, sh2, hash1 = len, hash2 = len, i;
  unsigned long long digest;

  for (i = 0; i != len; i++, str++)
    {

      hash1 += sTable[( *str + i) & 255];
      hash1 = LROT (hash1 + ((hash1 << 6) ^ (hash1 >> 8)));
      hash2 += sTable[( *str + i) & 255];
      hash2 = RROT (hash2 + ((hash2 << 6) ^ (hash2 >> 8)));

      sh1 = hash1;
      sh2 = hash2;

      hash1 = ((sh1 >> 16) & 0xffff) | ((sh2 & 0xffff) << 16);
      hash2 = ((sh2 >> 16) & 0xffff) | ((sh1 & 0xffff) << 16);

    }

#ifdef HIAVAL
  digest = (((unsigned long long) hash1) << 32)  | ((unsigned long long) hash2 );
  digest ^= LROT64(digest + ((digest << 13) ^ (digest >> 23)));
#else
  digest = (((unsigned long long) hash2) << 32)  | ((unsigned long long) hash1 );
#endif

  return digest;

}

MaHashMR1

Белая ворона? Более чем. Здесь мы имеет саму необычную структуру: четыре “вращающихся” 8-битных регистра накопления, которые модифицируются с помощью двойной табличной замены. На каждом шаге для накопления входного текста выбирается следующий регистр, затем все биты всех регистров циклически сдвигаются на один бит. Функция может иметь любое кол-во итераций. По всей видимости, оптимальным их числом будет три.

#define LROT1(x) (((x) << 1) | ((x) >> 31 ))
#define MR_ITERATIONS 3

union type_regs
  {
    unsigned long d32;
    unsigned char d8[4];
  };


unsigned long
MaHashMR1 (unsigned char *str, unsigned int len)
{
  unsigned int  i, s = 0;
  unsigned char val;
  union type_regs regs;

  regs.d32 = len;

  for (i = 0; i != len * MR_ITERATIONS; i++)
    {
      val = *(str + (i % len));

      regs.d8[s] =  sTable[(sTable[(val + i) & 255] + regs.d8[s]) & 255];

      s = (s + 1) % 4;

      regs.d32 = LROT1(regs.d32);
    }

  return regs.d32;
}

MurmurHash2AM

Как можно улучшить функцию, котороя итак уже близка к оптимальной? Легко. Надо добавить счетчик. Счетчик блока. Ведь счетчик вообще - дело хорошее. Он помогает нам для двух одинаковых блоков вычислить разные значения. Это не совсем то, что даст хорошая табличная подстановка, но уже избавит от множества проблем. Мы не получим таких всплесков на сложных наборах, как исходный вариант. При этом общие результаты пострадать не должны.

Итак, перед вами моя модификация MurmurHash2AM. M- потому, что модификация. AM, как ни странно - тоже имеет смысл - имя автора модификации.

#define mmix(h,k) { k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; }

unsigned int MurmurHash2AM ( char * key, unsigned int len)
{
  const unsigned int m = 0x5bd1e995;
  const int r = 24;
  unsigned int l = len, h = 0, i = 1;

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


  while (len >= 4)
    {
      unsigned int k = *(unsigned int*)data + i++;

      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;

}