Использование Integer в качестве ключа с HashMap в Java

Question

Недавно я искал хорошую реализацию метода hashCode() в Java API и просмотрел исходный код Integer.Не ожидал этого, но hashCode() просто возвращает поддерживаемое значение int.

public final class Integer ... {
private final int value;
...
    public int hashCode() {
        return Integer.hashCode(value);
    }
    public static int hashCode(int value) {
        return value;
    }

Это действительно странно, так как есть много статей и страниц, а также пакетов, посвященных этому вопросу -как спроектировать хорошую хеш-функцию для распределения значений.

Наконец, я пришел к такому выводу:

Integer - худший кандидат на тип данных для ключа при использовании с HashMap, так каквсе последовательные ключи будут размещены в одной корзине.Как в примере выше.

Map<Integer, String> map = HashMap<>();

for (int i = 1; i < 10; i++) {
    map.put(Integer.valueOf(i), "string" + i);
}

Есть два вопроса, на которые я не нашел ответов, когда гуглил:

1. Прав ли я с моим выводом относительно Integerтип данных?
2. В случае, если это правда, почему метод Integer's hashCode() не реализован каким-то хитрым способом, когда используются степенная операция, простые числа, двоичное смещение?

Answer 1

Из документов :

Общий контракт hashCode:

Всякий раз, когда он вызывается для одного и того же объекта более одного раза во время выполнения приложения Java, метод hashCode должен согласованно возвращает одно и то же целое число при условии, что информация не используется в равных сравнения на объекте модифицированы. Это целое число не должно оставаться соответствует от одного исполнения приложения к другому исполнению того же приложения.

-> Integer#hashCode выполняет это.

Если два объекта равны в соответствии с методом equals (Object), то вызов метода hashCode для каждого из двух объектов должен вывести тот же результат целого числа.

-> Integer#hashCode тоже выполняет это.

Не требуется, чтобы, если два объекта были неравны в соответствии с методом equals (java.lang.Object), то вызывается метод hashCode на каждом из двух объектов должны выдаваться разные целочисленные результаты. Тем не менее, программист должен знать, что создание различных целочисленные результаты для неравных объектов могут улучшить производительность хеш-таблицы.

-> Integer#hashCode выполняет это в максимальной степени, то есть два неравных Integer s будут никогда иметь одинаковый хэш-код.

Answer 2

В дополнение к ответу @ Eran, Java HashMap также имеет защиту от «плохих хэш-функций» (которых нет Integer.hashCode(), но все же).

/**
 * Computes key.hashCode() and spreads (XORs) higher bits of hash
 * to lower.  Because the table uses power-of-two masking, sets of
 * hashes that vary only in bits above the current mask will
 * always collide. (Among known examples are sets of Float keys
 * holding consecutive whole numbers in small tables.)  So we
 * apply a transform that spreads the impact of higher bits
 * downward. There is a tradeoff between speed, utility, and
 * quality of bit-spreading. Because many common sets of hashes
 * are already reasonably distributed (so don't benefit from
 * spreading), and because we use trees to handle large sets of
 * collisions in bins, we just XOR some shifted bits in the
 * cheapest possible way to reduce systematic lossage, as well as
 * to incorporate impact of the highest bits that would otherwise
 * never be used in index calculations because of table bounds.
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Итак, ваш «простой хеш»целого числа будет немного отличаться при работе с HashMap.

Answer 3

Целочисленное значение - наихудший кандидат на тип данных для ключа при использовании с HashMap, поскольку все последовательные ключи будут размещаться в одной ячейке

Нет, это утверждение неверно.

На самом деле реализация Integer hashCode() является наилучшей из возможных реализаций. Каждое значение Integer отображается на уникальное значение hashCode, что снижает вероятность сопоставления разных ключей в одном и том же сегменте.

Иногда лучше всего использовать простую реализацию.

Из Javadoc hashCode() в Object классе:

Не требуется, чтобы, если два объекта были неравны в соответствии с методом java.lang.Object.equals (java.lang.Object), то вызов метода hashCode для каждого из этих двух объектов должен давать разные целочисленные результаты. Однако программист должен знать, что выдача различных целочисленных результатов для неравных объектов может повысить производительность хеш-таблиц .

Integer - один из немногих классов, который фактически гарантирует, что неравные объекты будут иметь различные hashCode().