До недавнего времени мой ответ был очень близок к ответу Джона Скита. Тем не менее, я недавно начал проект, в котором использовались хеш-таблицы степени двойки, то есть хеш-таблицы, где размер внутренней таблицы равен 8, 16, 32 и т. Д. Есть веская причина для предпочтения размеров простых чисел, но есть Есть некоторые преимущества для размеров степени два.
И это в значительной степени отстой. Поэтому после небольшого количества экспериментов и исследований я начал перефразировать свои хэши следующим текстом:
public static int ReHash(int source)
{
unchecked
{
ulong c = 0xDEADBEEFDEADBEEF + (ulong)source;
ulong d = 0xE2ADBEEFDEADBEEF ^ c;
ulong a = d += c = c << 15 | c >> -15;
ulong b = a += d = d << 52 | d >> -52;
c ^= b += a = a << 26 | a >> -26;
d ^= c += b = b << 51 | b >> -51;
a ^= d += c = c << 28 | c >> -28;
b ^= a += d = d << 9 | d >> -9;
c ^= b += a = a << 47 | a >> -47;
d ^= c += b << 54 | b >> -54;
a ^= d += c << 32 | c >> 32;
a += d << 25 | d >> -25;
return (int)(a >> 1);
}
}
А потом мой хэш-стол с степенью двойки больше не сосал.
Это беспокоило меня, хотя, потому что выше не должно работать. Или, точнее, он не должен работать, если оригинал GetHashCode() не был очень плохим.
Повторное смешивание хеш-кода не может улучшить отличный хеш-код, потому что единственный возможный эффект - это введение нескольких коллизий.
Повторное смешивание хеш-кода не может улучшить ужасный хеш-код, потому что единственный возможный эффект - это изменение, например. большое количество столкновений по значению 53 с большим числом по значению 18,3487,291.
Повторное смешивание хеш-кода может улучшить только хеш-код, который, по крайней мере, довольно хорошо избежал абсолютных коллизий во всем диапазоне (2 32 возможных значений), но плохо избегает коллизий, когда по модулю для фактического использования в хеш-таблице. В то время как более простой модуль таблицы степеней двух сделал это более очевидным, он также имел отрицательный эффект с более распространенными таблицами простых чисел, что было не так очевидно (дополнительная работа по перефразировке перевесила бы преимущество , но выгода все равно будет там).
Редактировать: я также использовал открытую адресацию, что также увеличило бы чувствительность к столкновениям, возможно, даже больше, чем факт, что это была степень двойки.
И, конечно, было тревожно, насколько можно улучшить реализацию string.GetHashCode() в .NET (или изучить здесь ) таким образом (порядка тестов, выполняющих около 20 -30 раз быстрее из-за меньшего количества коллизий) и больше беспокоит то, насколько мои хэш-коды могут быть улучшены (гораздо больше).
Все реализации GetHashCode (), которые я кодировал в прошлом и действительно использовал в качестве основы для ответов на этом сайте, были намного хуже, чем я думал . В большинстве случаев это было «достаточно хорошо» для большинства применений, но я хотел чего-то лучшего.
Таким образом, я отложил этот проект в сторону (в любом случае, это был любимый проект) и начал искать способы быстрого создания хорошего, хорошо распределенного хеш-кода в .NET.
В итоге я остановился на портировании SpookyHash на .NET. Действительно, приведенный выше код является версией быстрого использования SpookyHash для получения 32-разрядного вывода из 32-разрядного ввода.
Теперь SpookyHash - это не просто быстрый фрагмент кода для запоминания. Мой порт этого еще меньше, потому что я много раз вписал его вручную для лучшей скорости *. Но для этого и используется повторное использование кода.
Затем я поместил этот проект в одну сторону, потому что так же, как в первоначальном проекте возник вопрос о том, как создать лучший хэш-код, так и в проекте возник вопрос о том, как создать лучший. NET memcpy.
Затем я вернулся и произвел много перегрузок, чтобы легко передать почти все нативные типы (кроме decimal †) в хэш-код.
Это быстро, за что Боб Дженкинс заслуживает большую часть кредита, потому что его оригинальный код, с которого я портировал, еще быстрее, особенно на 64-битных машинах, алгоритм которых оптимизирован для ‡.
Полный код можно увидеть на https://bitbucket.org/JonHanna/spookilysharp/src, но учтите, что приведенный выше код является его упрощенной версией.
Однако, поскольку он уже написан, его можно использовать проще:
public override int GetHashCode()
{
var hash = new SpookyHash();
hash.Update(field1);
hash.Update(field2);
hash.Update(field3);
return hash.Final().GetHashCode();
}
Он также принимает начальные значения, поэтому, если вам нужно иметь дело с ненадежным вводом и хотите защитить от атак Hash DoS, вы можете установить начальное время на основе времени безотказной работы или аналогичного, а также сделать результаты непредсказуемыми для злоумышленников:
private static long hashSeed0 = Environment.TickCount;
private static long hashSeed1 = DateTime.Now.Ticks;
public override int GetHashCode()
{
//produce different hashes ever time this application is restarted
//but remain consistent in each run, so attackers have a harder time
//DoSing the hash tables.
var hash = new SpookyHash(hashSeed0, hashSeed1);
hash.Update(field1);
hash.Update(field2);
hash.Update(field3);
return hash.Final().GetHashCode();
}
* Большим сюрпризом является то, что метод вращения вручную, который возвращает (x << n) | (x >> -n) улучшенных вещей. Я был бы уверен, что дрожание указало бы на это, но профилирование показало обратное.
† decimal не является родным с точки зрения .NET, хотя это с C #. Проблема в том, что его собственный GetHashCode() рассматривает точность как значимую, а его собственный Equals() - нет. Оба являются допустимыми, но не смешанными. При реализации своей собственной версии вам нужно выбрать одну или другую, но я не знаю, какую именно вы хотите.
Для сравнения. При использовании в строке SpookyHash на 64 битах значительно быстрее, чем string.GetHashCode() на 32 битах, что немного быстрее, чем string.GetHashCode() на 64 битах, что значительно быстрее, чем SpookyHash на 32 битах, хотя все еще достаточно быстро, чтобы быть разумный выбор.