Доступ к скрытому getEntry (ключу объекта) в HashMap

Question

У меня проблема, аналогичная обсуждаемой здесь , но с более сильным практическим использованием.

Например, у меня есть Map<String, Integer>, и у меня есть некоторая функция, которой присваивается ключ, и в случае, если отображаемое целочисленное значение является отрицательным, помещает NULL на карту:

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

public void nullifyIfNegative(String key) {
    Integer value = map.get(key);

    if (value != null && value.intValue() < 0) {
        map.put(key, null);
    }
}

В этом случае поиск (и, следовательно, hashCode вычисление для ключа) выполняется дважды: один для поиска и один для замены. Было бы неплохо иметь другой метод (который уже есть в HashMap) и позволяет сделать это более эффективным:

public void nullifyIfNegative(String key) {
    Map.Entry<String, Integer> entry = map.getEntry(key);

    if (entry != null && entry.getValue().intValue() < 0) {
        entry.setValue(null);
    }
}

То же самое касается случаев, когда вы хотите манипулировать неизменяемыми объектами, которые могут быть значениями карты:

• Map<String, String>: я хочу добавить что-либо к строковому значению.
• Map<String, int[]>: я хочу вставить число в массив.

Так что дело довольно распространенное. Решения, которые могут работать, но не для меня:

• Отражение. Это хорошо, но я не могу пожертвовать производительностью только ради этой замечательной функции.
• Используйте org.apache.commons.collections.map.AbstractHashedMap (он имеет по крайней мере protected getEntry() метод), но, к сожалению, коллекции commons не поддерживают дженерики.
• Используйте универсальные коллекции-сборники , но эта библиотека (AFAIK) устарела (не синхронизируется с последней версией библиотеки от Apache) и (что важно) недоступна в центральном хранилище maven.
• Использовать упаковщики значений, что означает «превращение значений в изменяемые» (например, использовать изменяемые целые числа [например, org.apache.commons.lang.mutable.MutableInt] или коллекции вместо массивов). Это решение приводит к потере памяти, чего я хотел бы избежать.
• Попробуйте расширить java.util.HashMap с помощью пользовательской реализации класса (которая должна быть в пакете java.util) и поместить ее в одобренную папку (так как java.lang.ClassLoader откажется загружать ее в Class<?> defineClass(String name, byte[] b, int off, int len), см. источники), но я не хочу исправлять JDK, и похоже, что список пакетов, которые могут быть одобрены, не включает java.util.

Подобный вопрос уже поднимался на багтрекер sun.com , но я хотел бы знать, каково мнение сообщества и что может быть выходом с учетом максимальной памяти и производительности эффективность.

Если вы согласны, это полезная и полезная функция, пожалуйста, оцените эту ошибку!

Answer 1

Как логично, вы правы в том, что единственный getEntry спасет вас от поиска хеша. С практической точки зрения, если у вас нет конкретного случая использования, когда у вас есть основания беспокоиться о падении производительности (что кажется довольно маловероятным, поиск хеша является обычным, O (1) и хорошо оптимизирован), то, что вы беспокоитесь вероятно, незначительный.

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

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

Answer 2

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

HashMap<String, String[]> map = ...;

// append value to the current value of key
String key = "key";
String value = "value";

// I use an array to hold a reference - even uglier than the whole idea itself ;)
String[] ref = new String[1]; // lightweigt object
String[] prev = map.put(key, ref);
ref[0] = (prev != null) ? prev[0] + value : value;

Хотя я бы не слишком беспокоился о производительности поиска хеша ( Ответ Стива Б довольно хорошо указывает на причину) Особенно с ключами String, я бы не слишком беспокоился о hashCode(), поскольку его результат кэшируется. Однако вы можете беспокоиться о equals(), так как он может вызываться более одного раза за поиск. Но для коротких строк (которые часто используются в качестве ключей) это тоже незначительно.

Answer 3

В этом предложении нет прироста производительности, поскольку производительность Map в среднем случае равна O (1). Но в этом случае включение доступа к необработанному входу создаст еще одну проблему. Будет возможно изменить ключ ввода (даже если это возможно только через отражение) и, следовательно, нарушить порядок внутреннего массива.