2012-02-27 4 views
4

HashSet в java сильно смутил меня, при использовании contains() он будет искать hashcode() и equals() result? Но в этом случае он не ведет себя нормально. Когда-нибудь это проблематично, если вы поместите этот вид кода в большой проект. Проблема в том, почему последний оператор печатает FALSE? Что содержит() делать под капотом?Weird HashSet содержит() поведение

class R 
{ 
    int count; 
    public R(int count) 
    { 
     this.count = count; 
    } 
    public String toString() 
    { 
     return "R(count attribution:" + count + ")"; 
    } 
    public boolean equals(Object obj) 
    { 
     if (obj instanceof R) 
     { 
      R r = (R)obj; 
      if (r.count == this.count) 
      { 
       return true; 
      } 
     } 
     return false; 
    } 
    public int hashCode() 
    { 
     return this.count; 
    } 
} 
public class TestHashSet2 
{ 
    public static void main(String[] args) 
    { 
     HashSet hs = new HashSet(); 
     hs.add(new R(5)); 
     hs.add(new R(-3)); 
     hs.add(new R(9)); 
     hs.add(new R(-2)); 

     System.out.println(hs); 

     //change first element 
     Iterator it = hs.iterator(); 
     R first = (R)it.next(); 
     first.count = -3; 
     System.out.println(hs); 
     //remove 
     hs.remove(new R(-3)); 
     System.out.println(hs); 

     R r1 = new R(-3); 
     System.out.println(r1.hashCode()); 
     Iterator i = hs.iterator(); 
     R r2 = (R)i.next(); 
     System.out.println(r2.hashCode()); //same hashcode -3 
     System.out.println(r1.equals(r2)); //equals true 

     System.out.println("hs contains object which count=-3 ?" + hs.contains(new R(-3))); //false 
    } 
} 
+0

первый взгляд на http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html Я думаю, вы пропустили концепцию HashMaps. – niklas

ответ

2

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

Представьте себе тривиальный хэш набор:

bucket object(hashcode) 
#1  5 
#2  -3 
#3  6 

с хэш-функцией для вычисления ведер, как:

f(hashcode) := | 5 -> 1 
       | -3 -> 2 
       | 6 -> 3 

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

Новая функция выглядит так:

f(hashcode) := | 5 -> 1 
       | 6 -> 3 

f(-3) возвратит нуль (возвращает ложь) и ваш реальный объект с хэш-кодом -3 хранятся где объект с хэш-кодом 5 должен быть.

1

Проблема заключается в том, что хэш-код из R объекта может изменения. Это является нарушением договора, согласно которому должен соблюдаться метод hashCode().

Чтобы понять, почему это имеет значение, вам нужно понять, как работает хеш-таблица. Java HashSet имеет в своем сердце массив списков записей. Когда вы помещаете объект в хеш-таблицу, он сначала вычисляет хэш-код объекта. Тогда это уменьшает хэш-код для индекса в массиве путем вычисления

index = hashcode % array.length 

Затем он ищет цепочку, начиная с array[index], и если объект не присутствует в списке, это добавляет его.

И чтобы проверить, содержит ли HashSet объект, он выполняет те же вычисления и ищет одну и ту же цепочку хеширования.

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

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


Вот что Java 7 Javadoc говорит (см java.jang.Object # хэш-код()):

«Общий договор является хэш-код:

  • Всякий раз, когда он вызывается на одном и том же объекте более одного раза во время выполнения приложения Java, метод hashCode должен последовательно возвращать одно и то же целое число, если никакая информация, используемая в eq Условные сравнения на объекте изменены. Это целое число не должно оставаться согласованным с одним исполнением приложения на другое выполнение одного и того же приложения.

  • ...

"не представила никакой информации ..." нюанс озадачивает меня. Я думаю, что это работает только в том случае, если есть правило о том, что не следует изменять хэш-коды объекта, когда они находятся в хеш-таблице. К сожалению, это правило не указано ни в одном из мест, которые вы ожидаете найти. Ошибка в документации?


Возможно, нам следует назвать требование о том, чтобы не менять хэш-коды «словесный договор»?:-)

+0

Фактически это не нарушает контракт 'hashCode()' (который требует только согласованности с 'equals()'), и API-документ 'HashSet' или' HashMap', похоже, не упоминает об этом. –

6

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

Как правило, плохая идея использовать изменяемые объекты в качестве ключей для любой карты или значений для набора. К счастью, используемые для этой цели классы (String, Integer) неизменяемы.

2

Именно поэтому вы не должны использовать изменяемые объекты в качестве ключей в HashSets и HashMaps.

Первый итератор возвратил объект R с hashCode 5. Затем вы изменили свойство этого объекта (количество). Но это не заставляет хэш пересчитываться. Итак, что касается HashSet, объект, для которого вы изменили счет до -3, все еще находится в ведре, соответствующем хеш-коду 5. Затем вы удалили объект, который находится в ведре, соответствующем хеш-коду -3, который был исходным объектом R (-3). Поэтому после этой операции в ведре нет хэша кода 3, поэтому contains(new R(-3)) возвращает false.

+0

Глядя на реализацию HashMap, это именно то, что происходит – assylias