HashSet.remove 不起作用

Question

我试图从 HashSet 中删除一个元素，但它不会。

调用 时.contains(obj)，它返回 true，因此.contains知道对象在 中HashSet。但是当我调用 时.remove(obj)，对象不会从 中删除HashSet，它返回false。

对象代码 - https://gist.github.com/rincew1nd/f97f11d21ba41d2f4197f9a9da02fea1

Answer 1

这是因为您没有Object#hashCode()在您的班级中进行覆盖。

hashCode()in Object的实现返回一个从调用对象内存地址计算的值。因此，除非您传递对地图中包含的对象的引用，否则remove(Object o)HashSet 将无法定位该对象。
注意：引用与由定义的相等对象不同o1.equals(o2)

请参阅帖子底部以解释为什么即使存储在地图中的对象没有被覆盖，“HashSet#contains(Object o)”仍然有效 Object#hashCode()

说我有一类MyClass是没有重写hashCode()
MyClass instance1 = new MyClass(); // Memory Address = 0x01
MyClass instance2 = new MyClass(); // Memory Address = 0x02
instance1.equals(instance2) == false

我可以毫无问题地将这些唯一对象添加到 HashSet，因为添加到 HashSet 仅依赖于equals(Object o)，而不依赖于hashCode()。

现在假设我想从 Set 中删除它们，但我丢失了对它们的原始引用，但我确实有以下引用：
instance3 // Memory Address = 0x03
instance4 // Memory Address = 0x04
instance1.equals(instance3) == true
instance2.equals(instance4) == true

调用将从集合中nonHashSet.remove(instance3)删除instance1。但是基于哈希的集合的工作方式完全不同：哈希代码（自我们使用以来从内存地址计算的值Object#hashCode()）用于定位项目。因此，当我要求 HashSet 删除instance3它时，它告诉我该哈希索引处没有元素。这是因为instance1和instance3的内存地址不同，所以各自的hash意义不同。

这真是糟糕，现在唯一可靠的方法来去除instance1或instance2从集是清除整个集或课程的重新初始化它。

在引擎盖下会发生什么HashSet：

当您首先尝试添加一个元素时，HashSet 会检查是否已经包含另一个被认为与要添加的元素相等的元素。如果添加的元素对于所有其他元素是唯一的，则将其添加到集合中。

aHashSet与 say a的不同之处在于NonHashSet元素的存储和检索方式。

在 a 中HashSet，在将元素添加到集合后（如add(E element)返回 true 时），该元素的散列通过调用element.hashCode(). 在非常宽松的术语中，您可以将散列视为元素将存储在的索引。

取自https://en.wikipedia.org/wiki/Hash_table

其中key == element, hash function == element.hashCode(),buckets == indexes以我上面描述的方式

关于 Buckets 的注意事项：与每个元素都有自己的索引的传统存储不同，两个不同的元素（不认为彼此相等）产生相同的 hash并不少见。发生这种情况时，会使用冲突处理机制来存储具有相同哈希值的元素。这超出了本问题的范围，但处理此问题的一种常见且简单的方法是在冲突哈希索引处创建一个 List，以存储包含相同哈希的所有元素。

从基于散列的集合中删除元素时，我们作为要删除的参数传递的元素会计算其散列值，然后使用该散列值来定位元素。如果哈希索引处有多个元素（当存在具有相同哈希的元素时发生），则HashSet 使用的冲突处理机制用于找到我们正在寻找的确切项目。在上面指定的机制中（在碰撞索引处存储一个List来存储每个碰撞的元素）elements.equals(collidedElement)

在一般合同一hashCode()实施应符合： 哈希代码合同的Java SE 8

更多信息：为什么我需要覆盖 Java 中的 equals 和 hashCode 方法？

实现有效散列函数的简单方法：hashCode 方法的最佳实现

如何contains(Object o)仍然有效：

我们来看一下确定contains(Object o)HashSet类中返回值的代码（Java版本7u40-b43）。我添加了评论来描述正在发生的事情：

// contains(Object o) will return true if this method returns non-null
// NOTE: Entry<K,V> seems out of place as we are dealing with a Set not a 
//       Map. But in fact the backing structure for HashSet is a type of Map
final Entry<K,V> getEntry(Object key) {
        if (size == 0) { // Set is empty, search element can't be contained
            return null;
        }

        // Calculate the hash of the search key:
        // IF the search key == null --> hash = 0
        // ELSE calculate and assign the hashCode for key inside method 
        //      hash()
        int hash = (key == null) ? 0 : hash(key);

        // Start at hash calculated, after each iteration set e to be 
        // the element that comes after e  (defined by e.next field). Stop 
        // iterating when e is null
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            // IF (the hash calculated from the search key and the hash 
            //     calculated from this Entries key are equal AND
            //     this Entries key equals the search key) OR
            //    (search key != null AND the search key equals this Entries 
            //     key)
            // then return entry --> contains returns true
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }