guava-library: Безопасно ли столкновение Objects.hashCode (Object [])? - PullRequest
Новая
       38

guava-library: Безопасно ли столкновение Objects.hashCode (Object [])?

6 голосов
/ 28 мая 2011

Рассматривая различные варианты переопределения hashCode(), я был направлен на Objects.hashCode(Object[]) в guava-библиотеках Google ( javadoc ).Javadoc заявляет, что он делегирует Arrays.hashCode(Object[]).Безопасно ли использовать этот метод во многих различных типах объектов?Разве это не склонно к хеш-коллизиям или маловероятно, потому что контейнеры обычно содержат только один тип объекта?

В качестве простого примера рассмотрим следующие классы: 

public class Student {
    private final String name;

    public Student(String name) {
        this.name = name;
    }

    @Override
    public int hashCode() {
        return Objects.hashCode(name);
    }
}

public class Teacher {
    private final String name;

    public Teacher(String name) {
        this.name = name;
    }

    @Override
    public int hashCode() {
        return Objects.hashCode(name);
    }
}

public class HashCodeDriver {
    public static void main(String[] args) {
        final String name = "moe";
        Student s = new Student(name);
        Teacher t = new Teacher(name);

        long studentHash = s.hashCode();
        long teacherHash = t.hashCode();
        System.out.println("studentHash=" + studentHash + " teacherHash=" + teacherHash);
        if(studentHash == teacherHash) {
            System.out.println("hash codes match");
        }
        else {
            System.out.println("hash codes don't match");
        }
    }
}

Вывод: 

studentHash=108322 teacherHash=108322
hash codes match

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

public class Student {
    private final String name;

    public Student(String name) {
        this.name = name;
    }

    @Override
    public int hashCode() {
        return Objects.hashCode(Student.class, name);
    }
}

public class Teacher {
    private final String name;

    public Teacher(String name) {
        this.name = name;
    }

    @Override
    public int hashCode() {
        return Objects.hashCode(Teacher.class, name);
    }
}

. По этой причине javadoc предупреждает о предоставлении только одного объекта этому методу?Из javadoc:

Предупреждение. Когда предоставляется один объект, возвращаемый хэш-код не равен хэш-коду этого объекта.

Ответы [ 3 ]

6 голосов
/ 28 мая 2011

Это не проблема, когда 2 разных объекта 2 разных типов имеют одинаковый хеш-код.

Надеюсь, когда вы собираетесь построить свой HashMap, вы не собираетесь смешивать учеников и учителей в качестве ключей к этой карте. И даже в том случае, если вы хотите сделать HashMap<Object, Object>, вы будете в порядке, потому что 

assertFalse( new Teacher( "John Smith" ).equals( new Student( "John Smith" ) );

Вот почему важно переопределить как hashCode, так и equals.

Единственный недостаток делегирования Arrays.hashCode(Object[]) может заключаться в том, что иногда это может быть слишком дорого с точки зрения производительности.

Например, в вашем случае это был бы гораздо лучший метод хеширования для Учителя или Студента. 

@Override
public int hashCode() {
    return name.hashCode();
}
3 голосов
/ 28 мая 2011

В предупреждениях только сказано, что x.hashCode() != Objects.hashCode(x) верно. (Хорошо, это верно в большинстве случаев. Они все еще могут сталкиваться для некоторых значений. На самом деле это не равно для большинства объектов.)

Допустимая реализация hashCode / equals: 

public class Teacher {
    private final String name;

    public Teacher(String name) {
        this.name = name;
    }

    @Override public equals(Object obj){
        if(obj == this) return true;
        if(!(obj instanceof Teacher)) return false;
        return Objects.equal(name, ((Teacher) obj).getName());
    }

    @Override public hashCode(){
        return 0;
    }
}

Это допустимо, хотя все хеш-значения конфликтуют. Из hashCode () javadoc:

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

Отличие от "нормальной" реализации состоит в том, что производительность этого кода будет намного хуже. Например, HashMaps выродится в списки, такие как производительность для поиска.

Даже с этой реализацией: 

@Override
public int hashCode() {
    return Objects.hashCode(Teacher.class, name);
}

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

Оптимизация такого рода должна быть последним средством, когда * * * * * * * * * * * * * * * * * *1025* экземпляров разных типов с одинаковыми именами *1025* в коллекции, которая использует внутренне hashCode (). . Общий эффект будет ограничен: если у вас n типов, у вас будет не более n коллизий из-за этого сценария. Другие факторы могут доминировать характеристики производительности.

0 голосов
/ 28 мая 2011

Если вы смешиваете много разных типов бетона в одном и том же наборе ключей карты, вы все равно можете использовать Objects.hashCode() и минимизировать коллизии, сохраняя выходные данные с разными значениями для конкретного типа. 

class Class1 {
  public int hashCode() {
    return Object.hashCode(...) ^ 0x12b7eff8;
  }
}

class Class2 {
  public int hashCode() {
    return Object.hashCode(...) ^ 0xe800792b;
  }
}

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

Предупреждение. Когда предоставляется один объект, возвращенный хеш-код не равен хеш-коду этого объекта.

Вот почему javadoc предупреждает о том, что в этот метод можно добавить только один объект? Из Javadoc,

Нет. Это предупреждение не о вероятности коллизий между экземплярами разных конкретных классов, имеющих одинаковые члены. Вместо этого он предупреждает о ложных отрицаниях в совпадениях с хеш-кодом из-за предположения, что хеш одного значения такой же, как у singleValue.hashCode().

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

class Name {
  int cachedHashCode;

  ...
}

class Person {
  int cachedHashCode;  // 0 if not computed

  private final Name name;

  public boolean hasName(Name n) {
    return ((cachedHashCode != 0 && n.cachedHashCode != 0) 
            && cachedHashCode == n.cachedHashCode)
        || n.equals(name);
  }

  public int hashCode() {
    if (cachedHashCode == 0) { cachedHashCode = Object.hashCode(name); }
    return cachedHashCode;
  }
}
...