Столкновения 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

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

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

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