Самый быстрый генератор хеш-кода .NET

Question

Я реализую пользовательский GetHashCode для класса System.Drawing.Point в C #. Мой метод в настоящее время не соответствует следующему требованию:

var hashA = MyGetHashCode(new Point(1, 0));
var hashB = MyGetHashCode(new Point(0, 1));
var hashC = MyGetHashCode(new Point(0, 0));
var hashD = MyGetHashCode(new Point(1, 1));
Assert.AreNotEqual(hashA ^ hashB, hashC ^ hashD);

Чтобы пройти этот тест, я уверен, что использование нового SHA256Managed (). ComputeHash (currentHash) подойдет Но есть ли другой более быстрый алгоритм хеширования? Я знаю, что SHA256 - это безопасность, и мне это не нужно.

Answer 1

Простой хеш? как насчет чего-то вроде:

 (17 * point.X) + (23 * point.Y);

Или для более очевидной энтропии:

int hash = -1047578147;
hash = (hash * -1521134295) + point.X;
hash = (hash * -1521134295) + point.Y;

(цифры из кода анонимного типа C #)

Answer 2

• Почему ты это делаешь? Конечно, System.Drawing.Point уже имеет прекрасную функцию хеширования?

• Вы понимаете, что тест не является строгим требованием, верно? Хеш-коды не должны быть уникальными.

• Если вы действительно хотите действительно хороший хэш рассматриваемых координат, вы можете начать с этой страницы о хешировании нескольких целых чисел.

Answer 3

Простая реализация хеш-эльфа (она на Delphi, ее легко перевести)

function ElfHash(id : string; tableSize : integer) : integer;
var
  i : integer;
  h,x : longint;
begin
  h := 0;
  // Obtener el valor numérico
  for i := 1 to Length(id) do
  begin
    h := (h shl 4) + Ord(id[i]);

    x := h and $F0000000;
    if x <;>; 0 then
       h = h xor (x shr 24) xor x;
  end;
  // Ajustar al tamaño de la tabla
  result := h mod tableSize;
end;

Answer 4

Вот интересная статья о скорости хеширования:

Функция хеширования для поиска хеш-таблицы

Answer 5

Я знаю, что это не ответит на ваш вопрос, но ради других читателей я должен упомянуть, что вы меняете поведение по умолчанию встроенного метода фреймворка. Согласно документации:
http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx

Реализация по умолчанию Метод GetHashCode не не гарантировать уникальные возвращаемые значения для разные предметы . Кроме того, .NET Framework не гарантирует реализация по умолчанию Метод GetHashCode и его значение возвраты будут одинаковыми между разные версии .NET Фреймворк. Следовательно, по умолчанию реализация этого метода должна не должен использоваться как уникальный объект идентификатор для хеширования.

Answer 6

Если вы заранее знаете, что значение вашей точки находится в диапазоне от 0 до N, вы можете использовать hashcode = X+Y*N; Это довольно очевидный возможный хэш. Это совсем не случайно, уродливое повторение и вообще довольно глупо. Это эквивалентно объединению битов двух ваших точек, если предположить, что N - степень 2. И у него идеальное равномерное распределение и нет коллизий.

Я использовал эту стратегию для превосходного эффекта в прошлом, но признаю, что она имеет некоторые реальные (но очевидные) ограничения. Самым большим является то, что происходит, когда N достаточно велико, чтобы N ^ 2 не вписывалось в ваше хеш-значение (то есть болезненные столкновения.

Answer 7

Я не знаю, какое у вас приложение, но вы, возможно, ищете хеширование Zobrist.

http://en.wikipedia.org/wiki/Zobrist_hashing

Может обновляться постепенно, что делает его очень быстрым.