Реализация Java HashMap put(). Почему бы не сначала проверить ссылки?

java.util.HashMap имеет реализацию метода put, который имеет следующий код внутри него:

if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    V oldValue = e.value;
    e.value = value;
    e.recordAccess(this);
    return oldValue;
}

В приведенном выше коде почему первая контрольная проверка не была выполнена (поскольку два объекта, имеющие одну и ту же ссылку, будут иметь одинаковый хэш и equals())?

то есть. что-то вроде этого:

if ((k = e.key) == key) {
    V oldValue = e.value;
    e.value = value;
    e.recordAccess(this);
    return oldValue;
} else if ( compare hash and equals) {
    // do something again with the value
}

Разве это не спасло бы сравнение?

Ответы

Ответ 1

Я не знаю, почему, но наивный микрообъект предполагает, что на Oracle VM (Intel, 32 или 64 бит) сравнение двух ссылок занимает примерно в четыре раза больше, чем сравнение двух int (как в хэш-кодах). Я бы предположил, что сравнение двух 32-битных целых чисел и двух указателей адресов должно было иметь аналогичную стоимость исполнения на современном оборудовании, но я, вероятно, просто не рассматриваю что-то очевидное здесь.

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

Методы, используемые для бенчмаркинга:

public static int c1(int a, int b, int iter) {
    int r = 0;
    while((iter--)>0) {
        if(a == b) {
            r++;
        }
    }
    return r;
}

public static int c2(Object a, Object b, int iter) {
    int r = 0;
    while((iter--)>0) {
        if(a == b) {
            r++;
        }
    }
    return r;
}

Ответ 2

Операции if_icmpne (сравнение целого) и if_acmpne (сравните ссылку) используйте тот же метод для получения результата [1, 2, 3, 4].

Оба подготовили значения в стеке и потребляют его одинаково. Не должно быть существенных различий в необходимых операциях. Оба будут выполняться в одном цикле процессора.

Чтобы указать, что карта может хранить объект в том же ведре, необходимо проверить два правила.

  • Их хэш-код должен быть равен
  • Обязательно возвращает true, когда x.equals(y)

IMHO код отражает эти правила, и я мог бы быть записан как

if (e.hash == hash && key.equals(k))

Чтобы удовлетворить требованиям к карте, мы всегда должны проверять хэши и равенства.

Таким образом, по соображениям производительности часть key.equals(k) была оптимизирована с помощью (k = e.key) == key, давая

((k = e.key) == key || key.equals(k))

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