Комментарии 23
Возник вопрос, почему хеш функция строки именно такая? Откуда взялся коэффициент 31, и почему решили считать именно так?
31 - красивое простое число состоящее из 4 единичек в бинарном представлении. А учитывая, что ASCII символы занимают 7 бит, то получается, что примерно половина бит очередного символа тратится на "перемешивание", а половина на "рост" хеша.
Не самый оптимальный коэффициент, конечно. Хеш растёт слишком медленно. Так что ведущие нули уходят лишь символу к седьмому.
По всей видимости сначала реализовали самый простой алгоритм, а потом оставили его из соображений совместимости.
До Java 1.2 хеш-функция строки была другой:
public int hashCode() {
int h = 0;
int off = offset;
char val[] = value;
int len = count;
if (len < 16) {
for (int i = len ; i > 0; i--) {
h = (h * 37) + val[off++];
}
} else {
// only sample some characters
int skip = len / 8;
for (int i = len ; i > 0; i -= skip, off += skip) {
h = (h * 39) + val[off];
}
}
return h;
}Она была медленнее, коллизии для неё подобрать было ещё легче, для строк длиннее 15 символов учитывался лишь каждый S.length() / 8 символ, да ещё и в Java Language Specification была ошибка.
Потом это обнаружили и Джош Блох предложил всё переделать, детали в JDK-4045622.
Откуда взялся коэффициент 31, и почему решили считать именно так?
Приведу несколько цитат из вышеупомянутого issue:
The class of hash function that I recommend using is polynomials whose
coefficients are the characters in the string:
P(x) = s[0] * x^(n-1) + s[1] * x^(n-2) +… + s[n-1]
The value of x is part of the definition of the hash function; choosing
this value is somewhat of a black art.
While this class of hash function is recommended in The Dragon Book
(P(65599)) and Kernighan and Ritchie's «The C Programming Language, 2 Ed.»
(P(31)), it is not attributed in either of these books.
I went so far as to call up Dennis Ritchie, who said that he did not know where the hash function came from. He walked across the hall and asked Brian Kernighan, who also had no recollection.
I'd probably select P(31), as it's the cheapest to calculate on a RISC machine (because 31 is the difference of two powers of two).
Откуда взялось 31 не помнят даже Керниган и Ричи. Чёрная магия, как она есть.
Если тема интересна, то стоит прочитать все комментарии к JDK-4045622 по ссылке выше.
Я бы задал другой вопрос: почему вообще Object.hashCode() возвращает int, а не long
Эдак и до вопроса «почему локальная переменная типа long занимает 2 слота памяти, а ссылка на объект даже на 64-битной системе с -XX:-UseCompressedOops — один» дойти можно.
Вы не забывайте, что java запускалась даже на тапках, где 64 бита большая роскошь.
Так а что от этого меняется? 64-битный лонг останется 64-битным, а размер ссылки останется подробностями реализации, разве нет?
Два слота под один long/double это тоже деталь реализации, да ещё и протёкшая в байткод. Не аккуратненько-с.
Можете объяснить, что такого жёсткого в 32-битных хешах?
Для 64-битных точно так же писали бы реализации hashCode() с плохим распределением, а разница в скорости в старые-добрые девяностые была бы ощутима.
jshell почему-то воспринимается как js hell
Порадуюсь за C# - там такого нет:
то что не подошли именно эти символы не значит что там такой фигни нет.
Вот реализация String.GetHashCode:
public override int GetHashCode()
{
ulong seed = Marvin.DefaultSeed;
// Multiplication below will not overflow since going from positive Int32 to UInt32.
return Marvin.ComputeHash32(ref Unsafe.As<char, byte>(ref _firstChar), (uint)_stringLength * 2 /* in bytes, not chars */, (uint)seed, (uint)(seed >> 32));
}
Используется алгоритм Marvin, который использует случайный seed генерируемый один раз за запуск приложения. Так что даже одна и та же строка будет иметь разный хэш код при разных запусках.
public static ulong DefaultSeed { get; } = GenerateSeed();
private static unsafe ulong GenerateSeed()
{
ulong seed;
Interop.GetRandomBytes((byte*)&seed, sizeof(ulong));
return seed;
}
Microsoft настолько заморочилась, что разработала алгоритм и даже запатентовала его.
Но так как хеширование в общем случае это отображение бОльшего множества на меньшее, то коллизии по хеш-коду между различными строками будут и в .net.
Да, есть твит Шипилева по этому вопросу https://twitter.com/shipilev/status/1561637440938541056
Атака на String.hashCode: прообразы и коллизии