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

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

есть несколько ключевых вещей, чтобы понять здесь:

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

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

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

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

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

еще немного подробностей, если хотите:

способ работы хэширования (в частности, в случае хэшированных коллекций, таких как HashMap Java, о котором вы спрашивали) заключается в следующем:

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

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

• HashMap использует этот хэш-код для выбора корзины. В конечном счете, это означает принятие целого значения modulo количество ведер, но до этого у 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;
    }
}