Может ли хэш быть отрицательным и почему

Что проверяют

Знаете ли вы, что hashCode() в Java это обычный знаковый int, и видели ли баги, которые из этого вырастают. Следом почти всегда просят превратить хэш в индекс массива и смотрят, напишете ли вы Math.abs(h) % n.

Как отвечать

Да. hashCode() возвращает int в диапазоне от Integer.MIN_VALUE до Integer.MAX_VALUE, и контракт не обещает неотрицательных значений. Причина не в «распределении», а в арифметике: хэш обычно считается умножением и сложением, int при переполнении молча заворачивается, и у хорошо перемешанных значений знаковый бит равен единице примерно в половине случаев.

• String.hashCode(): s[0]*31^(n-1) + ... + s[n-1] в арифметике int. Уже на строках средней длины переполнение гарантировано, отрицательные хэши обычное дело;
• Long.hashCode(): (int)(value ^ (value >>> 32)), отрицательный результат тоже нормален;
• Objects.hash(...): та же схема с множителем 31 и те же отрицательные значения.

Самой хэш-таблице знак не мешает. HashMap берёт индекс как (n - 1) & hash, где n степень двойки, и побитовое И с положительной маской всегда даёт число от 0 до n - 1.

Проблема появляется, когда индекс считаете вы сами, например при шардировании или в своём хэш-массиве:

• h % n: для отрицательного h остаток в Java тоже отрицательный;
• Math.abs(h) % n: ломается на Integer.MIN_VALUE, его модуль не помещается в int, и Math.abs возвращает то же отрицательное число;
• правильно: Math.floorMod(h, n) или (h & 0x7fffffff) % n.

Знаменитый пример: "polygenelubricants".hashCode() равен ровно Integer.MIN_VALUE, так что баг с Math.abs воспроизводится на реальной строке.

Где спотыкаются

Объясняют отрицательный хэш «особенностями алгоритма» вместо переполнения знакового int. Интервьюер ждёт именно слово «переполнение».

Пишут Math.abs(key.hashCode()) % size и получают ArrayIndexOutOfBoundsException на редком ключе, который в тестах не встретился и всплыл уже на проде.

Считают отрицательный хэш признаком плохой реализации hashCode() и начинают его «исправлять», ломая согласованность с equals(): равные объекты обязаны давать одинаковый хэш.