Может ли хэш-код Java создавать одно и то же значение для разных строк?

Возможно ли иметь один и тот же хеш-код для разных строк, используя функцию хеширования java? Или, если это возможно, то каков% его возможностей?

Ответы на вопрос(11)

// Вы можете запустить приведенный ниже код с -Xmx2100m и получить несколько результатов, достаточных для заполнения консоли

`

import java.util.HashMap;

public class TestHashCollision {
        public static void main(String[] args) {
        final String TEXT = "was stored earlier had the same hash as";
        HashMap<Integer,String> hs=new HashMap<>();
        long t1=System.currentTimeMillis();
        long t2=System.currentTimeMillis();
        for(long l=0;l<Long.MAX_VALUE;l++) {
            String key="d"+l;
            if(hs.containsKey(key.hashCode())) {
                System.out.println("'"+hs.get(key.hashCode())+"' "+TEXT+" '"+key+"'");//System.exit(0);
            } else {
                hs.put(key.hashCode(),key);
            }
            t2=System.currentTimeMillis();
            if(t2-t1>10000) {
                t1=System.currentTimeMillis();
                System.out.println("10 seconds gone! size is:"+hs.size());
            }
        }
        System.out.println("Done"); 
    }
}

`

Решение Вопроса

Хэш-код Java составляет 32 бита. Количество возможных строк, которые он хэширует, бесконечно.

Так что да, будут столкновения. Процент не имеет смысла - существует бесконечное количество элементов (строк) и конечное количество возможных хэшей.

 09 окт. 2014 г., 19:41
& quot; Количество возможных строк, которые он хэширует, бесконечно. & quot; Строки в Java имеют максимальный размер, потому что они используютchar массив иarrays in Java (using the standard JVM) have a maximum size, Поэтому количество возможных строк не бесконечно.
 Xara11 апр. 2012 г., 10:31
Итак, могу ли я сказать, что он может производить 2 ^ 32 различных хешей и после этого он будет повторять хеш-коды?
 12 апр. 2012 г., 00:07
С другой стороны, это называется принципом голубиного отверстияen.wikipedia.org/wiki/Pigeonhole_principle
 11 апр. 2012 г., 10:32
Если вам удастся идентифицировать 2 ^ 32 строки, которые имеют разные хеш-коды, то да, любая другая строка, отсутствующая в этом списке, будет иметь такой же хеш-код, что и в этом списке.
 31 мая 2013 г., 01:16
Вы, вероятно, пройдете намного меньше, чем 2 ^ 32 строки (около 2 ^ 16 строк), прежде чем столкнетесь с коллизией. Причина, по которой связан парадокс дня рождения:betterexplained.com/articles/understanding-the-birthday-paradox

Это не даст прямого ответа на ваш вопрос, но я надеюсь, что это поможет.

Ниже из исходного кодаjava.lang.String.

/**
 * Returns a hash code for this string. The hash code for a
 * <code>String</code> object is computed as
 * <blockquote><pre>
 * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
 * </pre></blockquote>
 * using <code>int</code> arithmetic, where <code>s[i]</code> is the
 * <i>i</i>th character of the string, <code>n</code> is the length of
 * the string, and <code>^</code> indicates exponentiation.
 * (The hash value of the empty string is zero.)
 *
 * @return  a hash code value for this object.
 */
public int hashCode() {
    int h = hash;
    int len = count;
    if (h == 0 && len > 0) {
    int off = offset;
    char val[] = value;

        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return h;
}

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

Процент столкновений заrandom Строки должны быть минимальными. Однако, если вы хешируете строки из внешних источников, злоумышленник может легко создать сотни тысяч строк с одинаковым хеш-кодом. В java HashMap все они будут отображаться в одно и то же ведро и эффективно превращать карту в связанный список. Время доступа к карте будет пропорционально размеру карты, а не постоянному, что приведет к атаке типа «отказ в обслуживании».

Смотрите эту страницу наЭффективные DoS-атаки на платформы веб-приложений для получения дополнительной информации ссылки на презентацию.

if it is possible then what is the % of its possibility?

Это не особо значимый вопрос.

Тем не менее, если нет некоторого системного смещения вString::hashcode функция или способ, которым вы генерируетеString объекты, вероятность того, что любые два разных (не равных)String объекты будут иметь одинаковый хеш-код будет 1 в 232.

Это предполагает, что строки выбираются случайным образом из набора всех возможных значений строки. Если вы ограничите набор различными способами, вероятность будет отличаться от приведенного выше числа. (Например, наличие коллизии «FB» / «Ea» означает, что вероятность коллизии во множестве всех двухбуквенных строк выше нормы).

Еще одна вещь, которую стоит отметить, это то, что шанс 232 различные строки, выбранные случайным образом (из гораздо большего несмещенного набора строк), не имеющие хеш-коллизий,vanishingly маленький. Чтобы понять почему, прочитайте страницу Википедии наДень рождения парадокс.

На самом деле, единственный способ получить хеш-коллизии в наборе 232 разные строки, если вы выбираете или генерируете строки. Даже формирование множества путем выбора случайно сгенерированных строк будет вычислительно дорогостоящим. Чтобы создать такой набор эффективно, вам необходимо использовать свойстваString::hashCode алгоритм, который (к счастью) указан.

 12 апр. 2012 г., 03:20
@ Зара На самом деле это даже говорит об обратном! Имея 2 ^ 32 разных строк, вы, скорее всего, столкнетесь (или даже несколько ..).
 12 апр. 2012 г., 04:04
@jory - да, ты прав. Это пример парадокса дня рождения. (Не совсем невозможно, чтобы 2 ^ 32 разных случайно сгенерированных строки имели разные хеш-коды. Просто невероятно невероятно.)
 Xara11 апр. 2012 г., 11:18
Итак, могу ли я сказать, что для 2 ^ 32 разных строк функция хеширования всегда будет производить разные хеш-коды?

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

Two same strings/value must have the same hashcode, but the converse is not true.

пример в питоне

>>> hash('same-string')
-5833666992484370527
>>> hash('same-string')
-5833666992484370527

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

The reason for two different string to have the same hash-code is due to the collision. enter image description here

Да, две строки могут иметь один и тот же хэш-код. Если вы посмотрите наСтатья в википедии, вы увидите, что оба"FB" а также"Ea" иметь тот же хэш-код. В договоре о методах ничего не сказаноhashCode() следует использовать для сравнения на равенство, которое вы хотите использоватьequals() для этого.

Начиная с Java 1.2, String реализуетhashCode() отиспользуя алгоритм суммы произведений по всему тексту строки.

Да, это возможно, потому что один из контрактов между equals () и amp; Метод hashCode () класса Object - это .......... If two object are not equal according to equals() method then there is no guaranty that their hashCode will be same, the hashCode may/may not be equal. i.e, if obj1.equals(obj2) return false then obj1.hashCode()==obj2.hashCode() may/may not return true. Пример:

    String str1 = "FB";
    String str2 = "Ea";
    System.out.println(str1.equals(str2));// false
    System.out.println(str1.hashCode() == str2.hashCode()); // true
 05 дек. 2018 г., 10:47
Можете ли вы объяснить, почему это так
 21 февр. 2019 г., 14:08
Потому что это один из контрактов между методами equals () и hashCode (). Если два объекта не равны в соответствии с методом equals (), тогда нет гарантии, что их hashCode будет одинаковым. Пожалуйста, посмотрите документ Javadocs.oracle.com/javase/7/docs/api/java/lang/…

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

With a set of size ~9,000, you'll have a 1% chance of two strings colliding with a hash in the set With a set of size ~30,000, you'll have a 10% chance of two strings colliding with a hash in the set With a set of size ~77,000, you'll have a 50% chance of two strings colliding with a hash in the set

Сделаны следующие предположения:

The hashCode function has no bias Each string in the aforementioned set is unique

Этот сайт объясняет это ясно:http://eclipsesource.com/blogs/2012/09/04/the-3-things-you-should-know-about-hashcode/ (Посмотрите на & quot; второе, что вы должны знать & quot;)

 09 сент. 2015 г., 14:32
Каков набор символов для строк, которые они там тестировали?

ДА. Много.

Посмотрите на следующую пару

"FB" and "Ea"

может вернуть тот же хэш-код, даже если символы в нем не совпадают.

В основном это сумма символов в строке, умноженная на целое число.

 11 апр. 2012 г., 10:33
Извините, это моя ошибка! Исправлено с помощью общего примера.
 Xara11 апр. 2012 г., 11:26
Зачем же хеш-код для них? Это две разные строки ...: S
 11 апр. 2012 г., 11:47
@Zara ссылается на метод String.hashcode (), размещенный adarshr ниже
 11 апр. 2012 г., 10:27
Это неверно. Каждый символ умножается на другое число, поэтому анаграммы не обязательно возвращают одно и то же значение.

Ваш ответ на вопрос