Что происходит с поиском в Hashmap или Hashset при изменении объектов Hashcode

В Hashmap хэш-код предоставленного ключа используется для размещения значения в хэш-таблице. В Hashset используется hashcode объектов, чтобы поместить значение в базовую хэш-таблицу. то есть преимущество хэшмапа в том, что у вас есть гибкость в выборе того, что вы хотите в качестве ключа, чтобы вы могли делать такие приятные вещи.

Map<String,Player> players = new HashMap<String,Player>();

Это может отображать строку, такую как имя игрока, самому игроку.

Мой вопрос заключается в том, что происходит с поиском, когда изменяется ключ Hashcode.

Я ожидаю, что это не такая серьезная проблема для Hashmap, как я бы не ожидал и не хотел, чтобы ключ менялся. В предыдущем примере, если имена игроков изменяются, он больше не является игроком. Однако я могу посмотреть на игрока, используя изменение ключа. Другие поля, которые не являются именем, и будущие поисковые запросы будут работать.

Однако в Hashset, поскольку весь объект hashcode используется для размещения элемента, если кто-то слегка изменяет объект, будущие поиски этого объекта больше не будут разрешаться к одной и той же позиции в Hashtable, поскольку он полагается на все объекты Hashcode. Означает ли это, что, как только данные находятся в Hashset, его не следует изменять. Или нужно его перефразировать? или это делается автоматически и т.д.? Что происходит?

Ответ 1

В вашем примере строка является неизменной, поэтому ее хэш-код не может измениться. Но гипотетически, если хэш-код объекта действительно изменился, когда был ключом в хеш-таблице, то он, вероятно, исчез бы до поисков хеш-таблиц. Я подробно рассмотрел этот ответ на соответствующий вопрос: fooobar.com/questions/538442/.... (Первоначальный вопрос касается HashSet, но HashSet действительно является HashMap под обложками, поэтому ответ также охватывает этот случай.)

Можно с уверенностью сказать, что если ключи HashMap или TreeMap мутируются таким образом, что они влияют на их соответствующие контракты hashcode()/equals(Object) или compare(...) или compareTo(...), тогда структура данных будет "сломать".

Означает ли это, что, как только данные находятся в Hashset, это не должно быть изменено.

Да.

Или нужно ли его перефразировать? или это делается автоматически и т.д.

Он не будет автоматически перезагружен. HashMap не заметит, что хэш-код ключа изменился. В самом деле, вы даже не сможете пересчитать хэш-код, когда размер HashMap изменится. Структура данных запоминает исходное значение hashcode, чтобы избежать необходимости пересчитывать все хэш-коды при изменении размера хэш-таблицы.

Если вы знаете, что хэш-код ключа изменится, вам нужно удалить запись из таблицы, прежде чем вы будете мутировать ключ, и добавьте его обратно. (Если вы попытаетесь выполнить remove/put после мутации ключа, есть вероятность, что remove не сможет найти запись.)

Что происходит?

Что происходит, так это то, что вы нарушили контракт, четко изложенный в javadocs HashMap. Не делай этого!

Ответ 2

В вашем примере клавиши String являются неизменяемыми. Таким образом, хэш-код ключей не изменится. Что происходит, когда хэш-код ключей изменяется undefined и приводит к "странному" поведению. См. Пример ниже, который печатает 1, false и 2. Объект остается в наборе, но набор выглядит как он сломан (содержит возвращает false).

Извлечь из Установить javadoc:

Примечание. Следует проявлять большую осторожность, если изменяемые объекты используются в качестве заданных элементов. Поведение набора не указывается, если значение объекта изменяется таким образом, который влияет на равные сравнения, когда объект является элементом в наборе. Особый случай этого запрета состоит в том, что недопустимо, чтобы набор содержал себя как элемент.

public static void main(String args[]) {
    Set<MyObject> set = new HashSet<>();
    MyObject o1 = new MyObject(1);
    set.add(o1);
    o1.i = 2;
    System.out.println(set.size());       //1
    System.out.println(set.contains(o1)); //false
    for (MyObject o : set) {
        System.out.println(o.i);          //2
    }
}

private static class MyObject {
    private int i;

    public MyObject(int i) {
        this.i = i;
    }

    @Override
    public int hashCode() {
        return i;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        final MyObject other = (MyObject) obj;
        if (this.i != other.i) return false;
        return true;
    }
}

Ответ 3

HashSet создается HashMap.

Из javadocs.

Этот класс реализует интерфейс Set, поддерживаемый хэш-таблицей (на самом деле экземпляр HashMap).

Итак, если вы измените хэш-код, я сомневаюсь, что вы можете получить доступ к объекту.

Внутренние параметры реализации

Реализация HashSet HashSet

 public boolean add(E e) {
        return map.put(e, PRESENT)==null;
 }

Ключ - это элемент, а значение - только фиктивный объект, называемый PRESENT

а реализация contains -

public boolean contains(Object o) {
        return map.containsKey(o);
}

Ответ 4

С хэшами Java исходная ссылка просто не найдена. Он искал в ведре соответствующий текущий хэш-код и не нашел.

Чтобы восстановить это после факта, необходимо выполнить итерацию набора ключей Hash, и любой ключ, который не найден методом contains, должен быть удален через итератор. Предпочтительно удалить ключ с карты, а затем сохранить значение с помощью нового ключа.