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

37

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

Ваш Ответ

11   ответов
8

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

  • 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;)

Каков набор символов для строк, которые они там тестировали?
6

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

Ниже из исходного кода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;
}
8

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

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

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

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


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

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

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

Да (не только в 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

21

ДА. Много.

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

  • "FB" and "Ea"

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

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

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

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

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

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

// Вы можете запустить приведенный ниже код с -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"); 
    }
}

`

5

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

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

2

Да, это возможно, потому что один из контрактов между 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
Потому что это один из контрактов между методами equals () и hashCode (). Если два объекта не равны в соответствии с методом equals (), тогда нет гарантии, что их hashCode будет одинаковым. Пожалуйста, посмотрите документ Javadocs.oracle.com/javase/7/docs/api/java/lang/…
Можете ли вы объяснить, почему это так
2

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

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

4

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

Похожие вопросы