Java HashMap удалить элемент после изменения его хеша

Question

У меня есть HashMap, где ключи являются непостоянными сложными объектами - хэш-изменения меняются в течение срока их службы.Я точно знаю, какие объекты изменены, но только по факту - их удаление с помощью map.remove(object) не сработает, потому что хеш изменился.Количество объектов на карте примерно в диапазоне [10, 10 000], проблема скорее в количестве изменений и обращений.

Было бы требовательным сделать проверку «вы измените» для каждого объектаперед изменением - удвойте работу, не говоря уже о беспорядке кода, необходимого для этого.

Позже я делаю итерации записей на карте, поэтому я решил, что могу просто пометить объекты для удаления и избавиться от них.они используют iterator.remove(), но, к сожалению, HashMap$HashIterator#remove вызывает hash(key).

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

Другой вариант - написать мой собственный HashMap, который отслеживает, где именно хранится каждый элемент (скажем, карта, образованнаяМассив двухмерных объектов = две координаты типа int).Это было бы более эффективно, но и намного больше для написания и тестирования.

Есть ли более простой способ сделать это, что я пропустил?

Редактировать:

Я использую обертки над сложным объектом, которые предоставляют разные пары хэш / равно в зависимости от подмножества свойств.Каждый объект может быть в нескольких картах.Скажем, я ищу красный объект на карте, который использует обертки с хешем / равнозначными по цвету, создает красный фиктивный объект и выполняет map.get (пустышка).

Реализации hash / equals и конкретных свойств, к которым они относятся, не являются частью моего кода.

Все карты являются объектами, отображаемыми на себя (как и реализация Set, но мне нужны методы доступа к карте).Я могу хранить хэши в этих оболочках, и тогда они будут придерживаться контракта с точки зрения хэширования, но equals все равно меня подведет.

Я понимаю, что при изменении результата hash / equals получается неопределенное поведение, но это действительноне должно иметь значения в теории - я меняю объект, и тогда я не хочу использовать карту, пока измененный объект не исчезнет из нее.Хеш-карта на самом деле не должна вызывать equals () или hash () для объекта, на который она уже указывает с помощью итератора.

Answer 1

Предыдущее состояние:

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

Комплексобъект изменялся в неудобное время, вызывая проблемы с повторной вставкой - объект изменялся, извлекал его, возвращал его с новым хешем.

Текущее решение:

Теоретически можно решить с помощью пользовательской реализации карты хеша(обратите внимание, что НЕ интерфейс хеш-карты, не будет поддерживать его контракт).Эта карта будет кэшировать хеши для своего содержимого в целях перефразирования и сохранять координаты в базовой структуре, так что equals не требуется для удаления с помощью итератора значений.Позже можно будет реализовать его, чтобы уменьшить объем используемой памяти.

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

public class Node {
    public HashMap<Key, Node> map;
    public Data<T> data;
    public Key key;
    public Node parent;
    public void update() {
        if (parent != null) parent.map.remove(key);
        key.update(data);
        if (parent != null) parent.map.put(key, this);
    }
}

public abstract class Key {
    public abstract void update(Data data);
    public abstract int hashCode();
    public abstract boolean equals(Object obj);
}

public class MyKey extends Key {

    private Object value = null;

    public final void update(Data data) {
        value = data.value;
    }

    public final boolean equals(Object obj) {
        IdentityKey that = (IdentityKey)obj;
        return this.value == that.value;
    }

    public final int hashCode() {
        return value == null ? 0 : value.hashCode();
    }
}

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

Answer 2

Все карты являются объектами, отображаемыми на себя (например, реализация Set, но мне нужны методы доступа к карте).Я могу хранить хэши в этих оболочках, и тогда они будут придерживаться контракта с точки зрения хэширования, но все равно меня не получится.

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

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

Но если у вас есть неизменяемые хэши и если у вас есть только один экземпляр на «равный» объект (не хранится ни один экземпляр)на карте и другом, но равном экземпляре, используемом для поиска), вы можете взглянуть на класс IdentityHashMap .