В куче JVM может быть несколько объектов с одинаковым хеш-кодом?

Question

Согласно заголовку, может ли быть несколько объектов в куче с одинаковым хеш-кодом?

Answer 1

Да.

public class MyObject {
    @Override
    public int hashCode() {
        return 42;
    }

    public static void main(String[] args) {
        MyObject obj1 = new MyObject();
        MyObject obj2 = new MyObject(); // Ta-da!
    }
}

Для менее легкомысленного ответа рассмотрим Javadocs hashCode :

Общий контракт hashCode:

• ... (отрывок) ...
• Если два объекта равны в соответствии с методом equals (Object), то вызов метода hashCode для каждого из двух объектов должен привести к одинаковому целочисленному результату.

Answer 2

да , поскольку вы можете иметь столько объектов с тем же hashCode, сколько захотите. Например, следующий код, без интернирующих строк , показывает этот факт:

String foo = new String("dfa");
String bar = new String("dfa");
assert foo != bar; // yields false, two distinct objects (references)
assert foo.hashCode() == bar.hashCode(); // yields true

Answer 3

Тривиальное доказательство: hashCode возвращает 32-разрядное целое число.

Выделите 2 ^ 32 + 1 объектов. (Вероятно, для этого понадобится 64-битная виртуальная машина и много оперативной памяти! ;-))

Теперь ваш метод hashCode, каким бы умным он ни был, должен иметь конфликт.

Answer 4

О хэш-кодах: да, они почти, но не уникальны. :) Это зависит от реализации / теории, насколько они почти уникальны.

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

Если вы говорите о результате метода hashCode (), который используется f.e. HashMap, то ответ: это зависит от вашей реализации и количества объектов в вашей JVM.
Это ваш выбор, план и знания, чтобы разрешить этот конфликт самореализованным методом hashCode ().

Если вы говорите о результате метода System.identityHashCode (obj), то он немного другой. Эта реализация не вызывает ваш метод hashCode (). И реализация не уникальна - но она почти уникальна, как и многие другие хеш-функции. :)

public class MyObject {
    @Override
    public int hashCode() {
        return 42;
    }

    public static void main(String[] args) {
        MyObject obj1 = new MyObject();
        MyObject obj2 = new MyObject(); // Ta-da!

        final int obj1Hash = System.identityHashCode( obj1 );
        final int obj2Hash = System.identityHashCode( obj2 );

        if( obj1Hash == obj2Hash ) throw new IllegalStateException();
    }
}

В этом примере вы получите разные хэши, и в большинстве случаев они разные, но не обязательно уникальные ...

С наилучшими пожеланиями!

Answer 5

Конечно, и, очевидно, вы можете написать:

class MyClass{
   ...
   public int hashCode(){
      return 1;
   }
   ...
}

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

Answer 6

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

public int hashCode(){
     return 1;
}

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

На практике, однако, столкновения могут происходить со многими реализациями. Возьмем для примера:

public class OrderedPair{
     private int x;
     private int y;

     public int hashCode(){
          int prime = 31;
          int result=x;
          result =result*prime+y;
          return result; 
     }

     public boolean equals(){...}
}

Это довольно стандартная реализация hashCode() (на самом деле, это довольно близко к выводу, который автоматически генерируется в IDEA и Eclipse), но он может иметь много конфликтов: x = 1, y = 0 и x = 0, y = 1 будет работать для начинающих. Идея хорошо написанной hashCode() реализации состоит в том, чтобы иметь достаточно мало коллизий, чтобы ваша производительность не подвергалась чрезмерному влиянию.

Answer 7

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

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

Answer 8

Object a = new Integer(1);
Object b = new Integer(1);

System.out.printf(" Is the same object?     = %s\n",(a == b ));
System.out.printf(" Have the same hashCode? = %s\n",( a.hashCode() == b.hashCode() ));

Отпечатки:

Is the same object?     = false
Have the same hashCode? = true

Answer 9

Да, у вас может быть несколько объектов с одинаковым хеш-кодом. Однако обычно это не вызывает проблем, поскольку структуры данных java.util. *, Использующие хэш-код объекта, используют его в качестве ключа в «корзине», в которой хранятся все объекты, возвращающие один и тот же хэш.

Answer 10

в 32-битной среде, я сомневаюсь, что любая JVM вернет один и тот же «хэш-код идентичности» для разных объектов. но в 64-битной версии это, безусловно, возможно; вероятность столкновения все еще очень мала, учитывая ограниченную память, которую мы имеем сейчас.