Столкновения HashMap: мой код правильный?

Question

Я хочу иметь один DateWrapper - представляющий дату (созданный для персистентности Hibernate, но это другая история) - максимально существующий одновременно для одной и той же даты.

Я немного озадачен коллизиями и хорошими ключами для хеширования. Я пишу фабрику для DateWrapper объект, и я подумал использовать миллисекунды анализируемой даты в качестве ключа, как я видел, как делают другие. Но что произойдет, если произойдет столкновение?, Миллисекунды всегда отличаются друг от друга, но внутренняя таблица может быть меньше, чем Long, который может существовать. И когда хэш-карта столкнулась, она использует равенства, но как она может отличить два разных объекта от моего Лонга? Может быть, это метод put для удаления (перезаписи) некоторого значения, которое я хотел бы вставить... Итак, этот код безопасен или содержит ошибки??

package myproject.test;

import java.util.HashMap;
import java.util.Map;

import org.joda.time.DateTime;
import org.joda.time.format.DateTimeFormat;
import org.joda.time.format.DateTimeFormatter;

import myproject.utilities.DateWrapper;

public class DateWrapperFactory {

    static Map <Long, DateWrapper> cache = new HashMap<Long, DateWrapper>();
    static DateTimeFormatter parser =
        DateTimeFormat.forPattern("yyyy-MM-dd");

    static DateWrapperFactory instance = new DateWrapperFactory();

    private DateWrapperFactory() {
    }

    public static DateWrapperFactory getInstance() {
        return instance;
    }


    public static DateWrapper get(String source) {
        DateTime d = parser.parseDateTime(source);
        DateWrapper dw = cache.get(d.getMillis());
        if (dw != null) {
            return dw;
        } else {
            dw = new DateWrapper(d);
            cache.put(d.getMillis(), dw);
            return dw;
        }
    }

}

package myproject.test;

import org.joda.time.DateTime;

public class DateWrapper {

    private DateTime date;

    public DateWrapper(DateTime dt) {
        this.date = dt;
    }

}

Answer 1

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

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

Мораль этой истории такова: используйте фактический ключ или что-то, что определенно эквивалентно (например, миллис DateTime в данном случае) в качестве ключа, а не хеш-кода ключа. HashMap делает то, что нужно с хеш-кодом для вас.

Answer 2

equals() будут вызываться на длинные клавиши, а не на значения. Ты в порядке.

Answer 3

С HashMap вы можете хранить только одну запись под любым данным значением ключа (например, Long в вашем случае).

Кроме того, если есть вероятность параллелизма, вы можете использовать ConcurrentHashMap и putIfAbsent() вместо неатомарных вызовов get/if/put.

Answer 4

Учитывая то, чего вы в конечном итоге пытаетесь достичь, это не кажется слишком продуктивным. У вас есть высоко оптимизированная структура данных, специально разработанная для быстрого поиска и обеспечения уникальности, которая называется индексом базы данных. И чрезвычайно надежный кэш в памяти и L2 уже доступен для вас из Hibernate. Который между прочим не имеет проблем с безопасностью потока при размещении HashMap в статическом поле.

Почему бы не сделать это число значением столбца ID в вашей базе данных и позволить надежным технологиям платформы позаботиться о его быстром поиске и кэшировании для вас? Попадание в кэш L2 в оперативной памяти на самом деле не намного медленнее, чем в HashMap. Это было бы довольно редким приложением, где различие - одно из ваших значимых горячих точек.