Плохая идея использовать Строковый ключ в HashMap?

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

Здесь нужно понять пару ключевых моментов:

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

2. Каждое использование хеширования позволяет обрабатывать конфликты, и Коллекции Java (включая HashMap) не являются исключением.

3. Хеширование не участвует в проверке равенства. Верно, что одинаковые объекты должны иметь одинаковые хэш-коды, но обратное неверно: многие значения будут иметь одинаковый хэш-код. Поэтому не пытайтесь использовать сравнение хэш-кода вместо равенства. Коллекции этого не делают. Они используют хеширование для выбора подгруппы (называемой корзиной в мире коллекций Java), но они используют .equals () для фактической проверки равенства.

4. Вам не только не нужно беспокоиться о коллизиях, вызывающих неправильные результаты в коллекции, но для большинства приложений вам также * обычно * не нужно беспокоиться о производительности - хешированные коллекции Java довольно хорошо справляются с управлением хэш-кодами .

5. Еще лучше, если вы спросили о (Строки как ключи), вам даже не нужно беспокоиться о самих хэш-кодах, потому что Java-класс String генерирует довольно хороший хэш-код. То же самое и с большинством поставляемых классов Java.

Некоторые подробности, если вы этого хотите:

Хеширование работает (в частности, в случае хешированных коллекций, таких как Java HashMap, о чем вы спрашивали):

• HashMap хранит значения, которые вы даете ему в коллекции вложенных коллекций, называемых корзинами. Фактически они реализованы в виде связанных списков. Их ограниченное количество: iirc, 16 для запуска по умолчанию, и число увеличивается по мере того, как вы помещаете больше элементов на карту. Ковшей всегда должно быть больше, чем значений. В качестве одного примера, используя значения по умолчанию, если вы добавите 100 записей в HashMap, будет 256 сегментов.

• Каждое значение, которое может использоваться в качестве ключа на карте, должно иметь возможность генерировать целочисленное значение, называемое хэш-код.

• HashMap использует этот хэш-код для выбора сегмента. В конечном итоге это означает принятие целочисленного значения по модулю количества сегментов, но до этого в Java HashMap есть внутренний метод (называемый hash () ), который настраивает хэш-код для уменьшения количества известных источников.

• При поиске значения HashMap выбирает сегмент, а затем выполняет поиск отдельного элемента путем линейного поиска связанного списка с помощью .equals () .

Итак: вам не нужно обходить коллизии для корректности, и вам обычно не нужно беспокоиться о них для производительности, а если вы используете собственные классы Java (например, String), у вас нет также беспокоиться о генерации значений хэш-кода.

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

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

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

Он все равно будет работать , но производительность снизится до уровня связанного списка.

Очевидно, вы не напишете такой ужасный метод hashcode (). Если вы используете достойную среду IDE, она может сгенерировать ее за вас. Поскольку StackOverflow любит код, вот код для класса firstname / lastname выше.

public class SimpleName {
    private String firstName;
    private String lastName;
    public SimpleName(String firstName, String lastName) {
        super();
        this.firstName = firstName;
        this.lastName = lastName;
    }
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result
                + ((firstName == null) ? 0 : firstName.hashCode());
        result = prime * result
                + ((lastName == null) ? 0 : lastName.hashCode());
        return result;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        SimpleName other = (SimpleName) obj;
        if (firstName == null) {
            if (other.firstName != null)
                return false;
        } else if (!firstName.equals(other.firstName))
            return false;
        if (lastName == null) {
            if (other.lastName != null)
                return false;
        } else if (!lastName.equals(other.lastName))
            return false;
        return true;
    }
}