Наихудшая временная сложность для HashMap после Java 8 по-прежнему равна O (n), а не O (log n)?
Сегодня я столкнулся с вопросом на собеседовании, связанным с Java HashMaps, и мне нужны разъяснения по нескольким моментам, касающимся временной сложности определенных операций и сравнений ключей в Java 8 и более поздних версиях.
Учитывая следующий фрагмент кода, какова временная сложность строки map.get(new Key(1));, учитывая улучшения HashMap в Java 8?
import java.util.*;
class Key {
int v;
public Key(int v) {
this.v = v;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Key key = (Key) o;
return v == key.v;
}
@Override
public int hashCode() {
return 0; // always hash collision
}
}
class Solution {
public static void main(String[] args) {
int n = 1_000_000;
Map<Key, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
Key key = new Key(i);
map.put(key, i);
}
map.get(new Key(1)); // What's the time complexity of this line?
}
}
Сначала я ответил O(log n), упомянув, что Java 8 автоматически преобразует длинные связанные списки в сегментах в красно-черные деревья для повышения эффективности.
Вопрос 1: Однако затем интервьюер поинтересовался, как выполняется сравнение в дереве RB, когда класс Key не реализует интерфейс Comparable.
Я ответил, что hashCode сначала используется для сравнения, так как даже в одном ведре он просто означает, что h1 % length == h2 % length. При дальнейшем вопросе о сценарии, в котором хэш-коды идентичны, я упомянул использование System.identityHashCode. Мой ответ такой же, как https://stackoverflow.com/a/43911638/10969942
Вопрос 2: Это приводит к обсуждению случая, когда два ключа equals, но, вероятно, имеют разные System.identityHashCode значения:
Key k1 = new Key(1);
Key k2 = new Key(1);
Я предположил, что это может потребовать обхода всех записей поддерева с одним и тем же хэш-кодом. Затем интервьюер спросил, означает ли это, что временная сложность в худшем случае равна O(n)? Я не знаю, так как всегда слышал, что после Java8 HashMap может гарантировать наихудшую временную сложность O(log n).
Вопрос 3: Затем интервьюер задал вопрос, как можно вставить в карту два разных ключа с одинаковым System.identityHashCode, учитывая, что дерево RB не допускает дублирования ключей:
Key k1 = new Key(1); // same identityHashCode
Key k2 = new Key(2); // same identityHashCode
Я помню, что разные объекты могли иметь один и тот же System.identityHashCode https://stackoverflow.com/a/1063100/10969942, но мне неясно, как HashMap управляет этими вставками, не нарушая ограничений дерева RB. при отсутствии повторяющихся ключей, которые обрабатывают конфликты hashCode иidentHashCode.
@LouisWasserman Однако я всегда слышал, что после Java8 гарантирована производительность в худшем случае O (log n). Это неправильно?
Да. Вы ослышались неправильно.
@LouisWasserman Однако из ответа stackoverflow.com/questions/43911369/… действительно говорится, что он будет использовать хеш-код идентификации для сравнения, если класс ключа не реализует интерфейс Comparable. Какой смысл это делать, если нельзя оптимизировать временную сложность.
См., например. вот . identityHashCode нельзя использовать для получения get O(log n).
Ответы 1
Учитывая следующий фрагмент кода, какова временная сложность Map.get(new Key(1)); строка, учитывая улучшения HashMap в Java 8?
Оно включено).
Сначала я ответил O(log n), отметив, что Java 8 автоматически преобразует длинные связанные списки в сегментах в красно-черные деревья для эффективность.
Да. В этом случае каждый ключ имеет один и тот же хэш-код, поэтому будет только один хэш-блок. При достаточном количестве записей оно будет организовано в виде сбалансированного дерева.
Вопрос 1: Однако затем интервьюер поинтересовался, как проводится сравнение. выполняется в дереве RB, когда класс Key не реализует
Comparableинтерфейс.
Как вы сказали, порядок дерева возвращается к идентификационному хэш-коду, когда хэш-коды равны, а тип ключа не имеет естественного порядка.
Вопрос 2: Это приводит к обсуждению случая, когда два ключа
equalsно, вероятно, имеют разныеSystem.identityHashCodeзначения:
Это действительно проблема для HashMap. Если ключ, который нужно найти, является тем же объектом, что уже есть на карте, то он будет найден за O(log n) шагов, но если это не так, то на карте все равно придется искать один equals() для него. . Это займет O(n) шагов, если такой ключ присутствует, и Θ(n) шагов, если нет.
Затем интервьюер спросил, означает ли это, что временная сложность в худшем случае равна O(n)?
Да, это так.
Я не знаю, так как всегда слышал, что после Java8 HashMap может гарантировать наихудшую временную сложность O(log n).
Надеюсь, ты этого не говорил. Хороший интервьюер не ожидает, что вы будете знать все, и люди могут получить дезинформацию самыми разными способами. Но, приведя вас к такому выводу, они вполне могли ожидать, что вы его примете. Как минимум, чтобы признать, что вывод кажется обоснованным.
Вопрос 3: Затем интервьюер задал вопрос, как два разных ключа с тот же самый
System.identityHashCodeможно вставить в карту, учитывая, что Дерево RB не допускает дублирования ключей:
Я думаю, здесь имеется в виду предположение
разные объекты могут иметь один и тот же System.identityHashCode
Это правда, что Java не гарантирует различные идентификационные хэш-коды, но указывает:
Насколько это практически возможно, метод
hashCode, определенный классомObject, возвращает разные целые числа для разных объектов.
(Реализация ObjecthashCode() — это, конечно же, идентификационный хэш-код.)
Мне неясно, как HashMap управляет этими вставками, не нарушая ограничений RB Tree на отсутствие повторяющихся ключей, то есть обрабатывает коллизии как hashCode, так иidentHashCode.
Я не знаю, что пришло мне в голову, и быстрая проверка документов не дала ответа. Но предполагая, что HashMap действительно обрабатывает этот случай, я ожидаю, что он сделает это со связанным списком в каждом узле дерева или чем-то подобным. Здесь это не представляет той же проблемы, что и использование связанного списка на уровне корзины, поскольку можно положиться на реализацию стандартной библиотеки для обеспечения достаточно хороших идентификационных хеш-кодов (см. выше).
Даже если HashMap на самом деле это не так, я подозреваю, что интервьюер был бы этим доволен. Опять же, они не ожидают, что вы будете знать все, но, скорее всего, они ищут людей, готовых думать.
Если идентификационные хеш-коды одинаковы, дерево станет несбалансированным (что так же хорошо, как связанный список). Это может произойти, если у вас много несопоставимых ключевых объектов с одинаковым хеш-кодом, поскольку в зависимости от реализации и среды только несколько битов в заголовке объекта могут быть зарезервированы для идентификационного хеш-кода (намного меньше 32). Но тогда необходимо исправить реализацию хэш-кода вашего ключевого класса. Идентификационный хеш-код здесь не поможет; он не проверяется во время поиска, поскольку при поиске ключа ниже такого узла необходимо проверять обе ветви.
Да, конечно, это означает, что временная сложность в худшем случае равна O (n). Использование System.identityHashCode несовместимо с альтернативными определениями
equalsиhashCode, поэтому его нельзя использовать.