MurmurHash2: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Содержимое удалено Содержимое добавлено
отмена правки 106440338 участника 82.193.155.250 (обс.)
Метка: отмена
отмена правки 106440333 участника 82.193.155.250 (обс.)
Метка: отмена
Строка 61: Строка 61:
Вторая версия хеш-функции имеет некоторые недостатки. В частности, это проблема коллизий на небольших строках. Исправленный вариант имеет структуру типа Merkle-Damgard, выполняется немного медленнее (примерно на 20 %), но показывает лучшую статистику.
Вторая версия хеш-функции имеет некоторые недостатки. В частности, это проблема коллизий на небольших строках. Исправленный вариант имеет структуру типа Merkle-Damgard, выполняется немного медленнее (примерно на 20 %), но показывает лучшую статистику.


<source lang="c">
<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;
unsigned char *data = buffer;
const int r = 24;
const uint32_t m = 0x5bd1e995;
unsigned int l = len;


const unsigned char * data = (const unsigned char *)key;
while (length >= 4) {


unsigned int h = seed;
k = *(uint32_t *)data;
unsigned int k;


while(len >= 4)
k *= m;
{
k ^= k >> r;
k *= m;
k = *(unsigned int*)data;


h *= m;
mmix(h,k);
h ^= k;


data += 4;
data += 4;
length -= 4;
len -= 4;
}
}


unsigned int t = 0;
switch (length) {

case 3:
switch(len)
h ^= data[2] << 16;
{
h ^= data[1] << 8;
h ^= data[0];
case 3: t ^= data[2] << 16;
case 2: t ^= data[1] << 8;
h *= m;
case 1: t ^= data[0];
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;
}

Ссылки