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

Ответ 1

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

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

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

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

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

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

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

Более подробная информация, если вы хотите:

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

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

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

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

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

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

В случае, когда вам нужно написать свой собственный метод hashcode (это означает, что вы написали класс с составным значением, например, имя и фамилия), все становится немного сложнее. Здесь совершенно неправильно, но это не ракетостроение. Во-первых, знайте об этом: единственное, что вы должны сделать, чтобы обеспечить правильность, - обеспечить равные объекты равными хэш-кодами. Поэтому, если вы пишете метод 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;
    }
}

Ответ 2

Я сильно подозреваю, что метод HashMap.put не определяет, является ли ключ одинаковым, просто глядя на String.hashCode.

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

Следовательно, новый ключ String будет считаться одним и тем же ключом String как тот, который уже находится в HashMap тогда и только тогда, когда значение, возвращаемое hashCode равно, а метод equals возвращает true.

Кроме того, эта мысль также будет верна для классов, отличных от String, поскольку сам класс Object уже имеет hashCode и equals.

Edit

Итак, чтобы ответить на вопрос, нет, было бы неплохо использовать String для ключа для HashMap.

Ответ 3

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

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

Это обычно работает очень хорошо, но только если хэш-функция хороша, т.е. не приводит к большему, чем статистически ожидаемое число коллизий для вашего конкретного набора входных данных. String.hashCode() хорош в этом отношении, но это было не всегда так. Предположительно, до появления Java 1.2 он отображал только каждый n-й символ. Это было быстрее, но вызвало предсказуемые коллизии для всех String, разделяющих каждый n-й символ - очень плохо, если вам недостаточно, чтобы иметь такой регулярный ввод, или если кто-то хочет атаковать DOS в вашем приложении.

Ответ 4

Я направляю вас на ответ здесь. Хотя неплохо использовать строки (@CPerkins объясняет, почему, отлично), сохранение значений в хэш-карте с целыми ключами лучше, так как обычно быстрее (хотя и незаметно) и имеет более низкий шанс (фактически, без шансов) коллизий.

Посмотрите на эту диаграмму столкновений, используя 216553 ключа в каждом случае (украденное из этого сообщение, переформатированное для нашего обсуждения)

Hash           Lowercase      Random UUID  Numbers 
=============  =============  ===========  ==============
Murmur            145 ns      259 ns          92 ns
                    6 collis    5 collis       0 collis
FNV-1a            152 ns      504 ns          86 ns
                    4 collis    4 collis       0 collis
FNV-1             184 ns      730 ns          92 ns
                    1 collis    5 collis       0 collis*
DBJ2a             158 ns      443 ns          91 ns
                    5 collis    6 collis       0 collis***
DJB2              156 ns      437 ns          93 ns
                    7 collis    6 collis       0 collis***
SDBM              148 ns      484 ns          90 ns
                    4 collis    6 collis       0 collis**
CRC32             250 ns      946 ns         130 ns
                    2 collis    0 collis       0 collis

Avg Time per key    0.8ps       2.5ps         0.44ps
Collisions (%)      0.002%      0.002%         0%

Конечно, число целых чисел ограничено 2 ^ 32, где, поскольку нет ограничения на количество строк (и теоретического предела для количества ключей, которые могут быть сохранены в HashMap), нет., Если вы используете long (или даже float), столкновения неизбежны и, следовательно, "лучше", чем строка. Однако, даже несмотря на хеш-коллизии, put() и get() всегда будут устанавливать/получать правильную пару "ключ-значение" (см. Править ниже).

В конце концов, это действительно не имеет значения, поэтому используйте все, что более удобно. Но если удобство не имеет значения, и вы не собираетесь иметь более 2 ^ 32 записей, я предлагаю вам использовать ints в качестве ключей.

ИЗМЕНИТЬ

В то время как вышеописанное определенно верно, НИКОГДА не используйте "StringKey".hashCode(), чтобы генерировать ключ вместо исходного ключа String по причинам производительности - две разные строки могут иметь один и тот же хеш-код, вызывая перезапись на put(). Реализация Java HashMap достаточно умен, чтобы обрабатывать строки (любой тип ключа, фактически) с одним и тем же хэш-кодом автоматически, поэтому разумно позволить Java обрабатывать эти вещи для вас.

Ответ 5

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

Не беспокойтесь об этом, если вы не вызываете hashCode самостоятельно. Конфликты хэшей, хотя и редки, не нарушают ничего.