Тестирование строкового равенства с помощью хэш-кода ()

Приведу встречный пример. Попробуйте это,

public static void main(String[] args) {
    String str1 = "0-42L";
    String str2 = "0-43-";

    System.out.println("String equality: " + str1.equals(str2));
    System.out.println("HashCode eqauality: " + (str1.hashCode() == str2.hashCode()));
}

Результат на моем Java,

String equality: false
HashCode eqauality: true

, как многие говорили, hashCode не гарантирует уникальности. на самом деле, он не может этого сделать по очень простой причине.

hashCode возвращает int, что означает, что существует 2 ^ 32 возможных значения (около 4 000 000 000), но наверняка существует более 2 ^ 32 возможных строк, что означает по крайней мере две строки имеют одинаковое значение хэш-кода.

это называется принцип голубятни .

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

Когда вы сравниваете две строки в Java, функция String equals сначала проверяет, являются ли они двумя ссылками на один и тот же объект. Если это так, он немедленно возвращает true. Затем он проверяет, равны ли длины. Если нет, возвращается false. Только после этого начинается посимвольное сравнение.

Если вы манипулируете данными в памяти, сравнение одного и того же объекта может быстро обработать «тот же» случай, и это быстрое, ммм, 4-байтовое целочисленное сравнение Я думаю. (Кто-то поправит меня, если у меня неправильная длина дескриптора объекта.)

Для большинства неравных строк я готов поспорить, что сравнение длины быстро обнаружит, что они не равны. Если вы сравниваете два названия вещей: клиенты, города, продукты, как бы то ни было - обычно они будут разной длины. Таким образом, простое сравнение int быстро избавляется от них.

В худшем случае для производительности будут две длинные, идентичные, но не одинаковые строки объектов. Затем он должен выполнить сравнение дескриптора объекта, false, продолжить проверку. Сравнение длины, правда, продолжайте проверять. Затем посимвольно по всей длине строки, чтобы убедиться, что да, действительно, они равны до конца.

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

Вы можете сравнить возвращаемые значения intern () с помощью оператора == . Если они ссылаются на одну и ту же строку, то исходные строки были эквивалентны (то есть equals () вернули бы true ), и для этого требуется только сравнение указателей (которое имеет такую ​​же стоимость, как и сравнение int .)

String a = "Hello";
String b = "Hel" + "lo";

System.out.println(a.equals(b));
System.out.println(a == b);

String a2 = a.intern();
String b2 = b.intern();

System.out.println(a2.equals(b2));
System.out.println(a2 == b2);

Вывод:

true
false
true
true

Значение hashCode не уникально , что означает, что строки могут не совпадать. Чтобы повысить производительность, часто реализация equals выполняет проверку хэш-кода перед выполнением более трудоемких проверок.

Очень простая причина: опасность столкновения ... У хэш-кода будет намного меньше возможных значений, чем у строки. Это немного зависит от типа генерируемого вами хеша, но давайте возьмем очень простой пример, в котором вы должны добавить порядковые значения букв, умноженные на их позицию: a = 1, b = 2 и т. Д. Таким образом, 'hello' будет перевести на: h: 8x1 = 8, e: 5x2 = 10, l: 12x3 = 36, l: 12x4 = 48, o: 15x5 = 75. 8 + 10 + 36 + 48 + 75 = 177.

Существуют ли другие строковые значения, которые могут заканчиваться хешированием 177? Конечно! Множество вариантов. Не стесняйтесь вычислять несколько.

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

Нет причин не использовать хэш-код, как вы описываете.

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