Странный HashSet содержит () поведение

Question

HashSet в java меня сильно смутил, когда при использовании функции contains () он будет искать результат hashcode () и equals ()?Но в этом случае он не ведет себя нормально.Иногда бывает проблематично, если вы помещаете этот вид кода в большой проект.Проблема в том, почему в последнем утверждении выведите FALSE？ что содержит () под капотом?

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
    }
}

Answer 1

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

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

Answer 2

HashSet сохраняет значения в сегментах , индекс сегмента вычисляется при добавлении элемента в хэш-набор.Идея, лежащая в основе этого: теперь набор может считывать хеш-код объекта и вычислять сегмент за один шаг.Другими словами: contains() является операцией 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) вернет ноль (contains() вернет false), и ваш фактический объект с хэш-кодом -3 будет сохранен там, где должен быть объект с хеш-кодом 5.

Answer 3

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

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

Answer 4

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

---

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

index = hashcode % array.length

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

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

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

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

---

Вот что говорит Java 7 javadoc (см. Java.jang.Object # hashcode ()):

"Общий контракт хэш-кода:

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

• ...

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

---

Может быть, мы должны назвать требование не менять хеш-коды "словесным контрактом"? : -)