为 Java 中的可变对象设置集合

Question

在Java中，集合仅在插入时检查对象与集合中已有对象的相等性。这意味着如果一个对象已经存在于集合中之后，它变得等于集合中的另一个对象，集合将保持两个相等的对象而不会抱怨。

编辑：例如，考虑一个简单的对象，并假设 hashCode 和 equals 是按照最佳实践定义的/

class Foo {
    int foo;

    Foo(int a){ foo = a; }
    //+ equals and hashcode based on "foo"
}

Foo foo1 = new Foo(1);
Foo foo2 = new Foo(2);
Set<Foo> set = new HashSet<Foo>();
set.add(foo1);
set.add(foo2);
//Here the set has two unequal elements.
foo2.foo = 1;
//At this point, foo2 is equal to foo1, but is still in the set 
//together with foo1.

如何为可变对象设计集合 class？我期望的行为如下：如果在任何时候集合中的一个对象变得等于集合中的另一个对象，则该对象将从集合中删除。已经有了吗？有没有一种编程语言可以使这更容易完成？

Answer 1

Set 确实使用了 hashCode 和 equals 方法。但是当你说

it becomes equal to another object in the set, the set will keep both equal objects without complaining.

事实并非如此。如果你 运行 通过添加已经存在的元素来添加方法，它会 return 你错误地说嘿你已经有一个对象在集合中。

Set 是一个不允许重复的数学术语，Java Set 就是这种情况。 Set 不知道您要插入其中的对象是可变的还是不可变的。它就像一个包含值的集合。

编辑： 根据代码，当您将元素插入 Set 时，将完成 set 中的检查，然后如果它发生变化，它不会关心它。

Answer 2

我不认为这可以在一般意义上在 Java 中可靠地完成。没有通用的机制来确保对对象的变异采取某种行动。

有几种方法可能足以满足您的用例。

1.观察元素变化

• 您需要控制进入集合的类型的实现
• 集合中的对象更新时性能消耗小

您可以尝试强制执行 observer like construction where your Set class is registered as an Observer to all its items. This implies you'd need to control the types of objects that can be put into the Set (only Observable 个对象）。此外，您需要确保 Observables 通知观察者 每个 可能影响 hashcode 和 equals 的变化。我不知道已经存在这样的 class。正如 Ray 在下面提到的那样，您还需要注意潜在的并发问题。 示例：

package collectiontests.observer;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Observable;
import java.util.Observer;
import java.util.Set;

public class ChangeDetectingSet<E extends Observable> implements Set<E>, Observer {

    private HashSet<E> innerSet;

    public void update(Observable o, Object arg) {
        innerSet.remove(o);
        innerSet.add((E)o); 
    }
    public int size() {
        return innerSet.size();
    }
    public boolean isEmpty() {
        return innerSet.isEmpty();
    }
    public boolean contains(Object o) {
        return innerSet.contains(o);
    }
    public Iterator<E> iterator() {
        return innerSet.iterator();
    }
    public Object[] toArray() {
        return innerSet.toArray();
    }
    public <T> T[] toArray(T[] a) {
        return innerSet.toArray(a);
    }
    public boolean add(E e) {
        e.addObserver(this);
        return innerSet.add(e);
    }
    public boolean remove(Object o) {
        if(o instanceof Observable){
            ((Observable) o).deleteObserver(this);
        }
        return innerSet.remove(o);
    }
    public boolean containsAll(Collection<?> c) {
        return innerSet.containsAll(c);
    }
    public boolean addAll(Collection<? extends E> c) {
        boolean result = false;
        for(E el: c){
            result = result || add(el);
        }
        return result;
    }
    public boolean retainAll(Collection<?> c) {
        Iterator<E> it = innerSet.iterator();
        E el;
        Collection<E> elementsToRemove = new ArrayList<E>();
        while(it.hasNext()){
            el = it.next();
            if(!c.contains(el)){
                elementsToRemove.add(el); //No changing the set while the iterator is going. Iterator.remove may not do what we want.
            }
        }
        for(E e: elementsToRemove){
            remove(e);
        }
        return !elementsToRemove.isEmpty(); //If it's empty there is no change and we should return false
    }
    public boolean removeAll(Collection<?> c) {
        boolean result = false;
        for(Object e: c){
            result = result || remove(e);
        }
        return result;
    }
    public void clear() {
        Iterator<E> it = innerSet.iterator();
        E el;
        while(it.hasNext()){
            el = it.next();
            el.deleteObserver(this);
        }
        innerSet.clear();
    }
}

每当可变对象发生变化时，这都会导致性能下降。

2。使用 Set 时检查变化

• 适用于您想要放入集合中的任何现有对象
• 每次需要有关集合的信息时都需要扫描整个集合（如果集合变得非常大，性能成本可能会显着增加）。

如果您的集合中的对象经常更改，但集合本身却很少使用，您可以尝试下面乔的解决方案。他建议在调用方法时检查 Set 是否仍然正确。作为奖励，他的方法将适用于 any 对象集（不必将其限制为可观察对象）。在性能方面，他的方法对于大型集合或经常使用的集合会有问题（因为在每次方法调用时都需要检查整个集合）。

Joe 方法的可能实现：

package collectiontests.check;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

public class ListBasedSet<E> {

    private List<E> innerList;

    public ListBasedSet(){
        this(null);
    }

    public ListBasedSet(Collection<E> elements){
        if (elements != null){
            innerList = new ArrayList<E>(elements);
        } else {
            innerList = new ArrayList<E>();
        }
    }

    public void add(E e){
        innerList.add(e);
    }

    public int size(){
        return toSet().size();
    }

    public Iterator<E> iterator(){
        return toSet().iterator();
    }

    public void remove(E e){
        while(innerList.remove(e)); //Keep removing until they are all gone (so set behavior is kept)
    }

    public boolean contains(E e){
        //I think you could just do innerList.contains here as it shouldn't care about duplicates
        return innerList.contains(e);
    }

    private Set<E> toSet(){
        return new HashSet<E>(innerList);
    }
}

以及检查始终方法的另一个实现（这个基于现有集）。如果您想尽可能多地重复使用现有的集合，这是可行的方法。

package collectiontests.check;

import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NavigableSet;
import java.util.SortedSet;
import java.util.TreeSet;

public class ChangeDetectingSet<E> extends TreeSet<E> {

    private boolean compacting = false;

    @SuppressWarnings("unchecked")
    private void compact(){
        //To avoid infinite loops, make sure we are not already compacting (compact also gets called in the methods used here)
        if(!compacting){ //Warning: this is not thread-safe
            compacting = true;
            Object[] elements = toArray();
            clear();
            for(Object element: elements){
                add((E)element); //Yes unsafe cast, but we're rather sure
            }
            compacting = false;
        }
    }
    @Override
    public boolean add(E e) {
        compact();
        return super.add(e);
    }
    @Override
    public Iterator<E> iterator() {
        compact();
        return super.iterator();
    }
    @Override
    public Iterator<E> descendingIterator() {
        compact();
        return super.descendingIterator();
    }
    @Override
    public NavigableSet<E> descendingSet() {
        compact();
        return super.descendingSet();
    }
    @Override
    public int size() {
        compact();
        return super.size();
    }
    @Override
    public boolean isEmpty() {
        compact();
        return super.isEmpty();
    }
    @Override
    public boolean contains(Object o) {
        compact();
        return super.contains(o);
    }
    @Override
    public boolean remove(Object o) {
        compact();
        return super.remove(o);
    }
    @Override
    public void clear() {
        compact();
        super.clear();
    }
    @Override
    public boolean addAll(Collection<? extends E> c) {
        compact();
        return super.addAll(c);
    }
    @Override
    public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) {
        compact();
        return super.subSet(fromElement, fromInclusive, toElement, toInclusive);
    }
    @Override
    public NavigableSet<E> headSet(E toElement, boolean inclusive) {
        compact();
        return super.headSet(toElement, inclusive);
    }
    @Override
    public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
        compact();
        return super.tailSet(fromElement, inclusive);
    }
    @Override
    public SortedSet<E> subSet(E fromElement, E toElement) {
        compact();
        return super.subSet(fromElement, toElement);
    }
    @Override
    public SortedSet<E> headSet(E toElement) {
        compact();
        return super.headSet(toElement);
    }
    @Override
    public SortedSet<E> tailSet(E fromElement) {
        compact();
        return super.tailSet(fromElement);
    }
    @Override
    public Comparator<? super E> comparator() {
        compact();
        return super.comparator();
    }
    @Override
    public E first() {
        compact();
        return super.first();
    }
    @Override
    public E last() {
        compact();
        return super.last();
    }
    @Override
    public E lower(E e) {
        compact();
        return super.lower(e);
    }
    @Override
    public E floor(E e) {
        compact();
        return super.floor(e);
    }
    @Override
    public E ceiling(E e) {
        compact();
        return super.ceiling(e);
    }
    @Override
    public E higher(E e) {
        compact();
        return super.higher(e);
    }
    @Override
    public E pollFirst() {
        compact();
        return super.pollFirst();
    }
    @Override
    public E pollLast() {
        compact();
        return super.pollLast();
    }
    @Override
    public boolean removeAll(Collection<?> c) {
        compact();
        return super.removeAll(c);
    }
    @Override
    public Object[] toArray() {
        compact();
        return super.toArray();
    }
    @Override
    public <T> T[] toArray(T[] a) {
        compact();
        return super.toArray(a);
    }
    @Override
    public boolean containsAll(Collection<?> c) {
        compact();
        return super.containsAll(c);
    }
    @Override
    public boolean retainAll(Collection<?> c) {
        compact();
        return super.retainAll(c);
    }
    @Override
    public String toString() {
        compact();
        return super.toString();
    }
}

3。使用 Scala 集合

您可以在您的集合中作弊并取消可变对象（从某种意义上说，您不会改变，而是创建一个 属性 已更改的新对象）。您可以查看 Scala 中的集合（我认为可以从 Java 调用 Scala，但我不是 100% 确定）：http://www.scala-lang.org/api/current/scala/collection/immutable/IndexedSeq.html

Answer 3

你不会找到一个通用的数据结构可以为此目的只接受任何对象。那种集合必须不断地监控它的元素，除其他外，这会导致很多关于并发性的问题。

但是，我可以根据实际未知的情况想象一些东西 class java.util.Observable。你可以例如写一个class ChangeAwareSet implements Set<? extends Observable>, Observer。当一个元素被添加到这个 Set 中时，它会注册为一个观察者，因此会收到对该对象的所有更改的通知。 （但不要指望这会非常高效，在这种情况下你也可能会遇到并发问题。）

Answer 4

您可以通过使用另一个集合（例如 ArrayList）来获得您想要的行为。 contains 和 remove 方法 List 不假设对象保持不变。

由于随时可能发生变化，因此没有太多优化空间。任何操作都需要对所有内容执行全面扫描，因为自上次操作以来任何对象都可能发生变化。

您可能希望也可能不希望覆盖 add 以检查对象当前是否存在。然后，在使用或打印时，使用new HashSet(list)消除当前重复的对象。

Answer 5

您的问题是对象的身份 与状态。 identity 不会随时间变化，state 是。在你的集合中，你应该最好依赖 identity 因为这是不通过突变引入重复的唯一保证，或者你必须在每次有元素突变时重建 Set .从技术上讲，equals() 和 hashCode() 应该随着时间的推移保持不变，以反映 身份 。

正如@assylias 评论的那样，如果您需要一个组合了 identity 和 state 的集合，当然有一个替代方案。

• 有 Map<TheObject, List<State>> 而不是 Set<TheObjectWithState>
• 从变异前的Set中移除对象，变异后检查是否存在，如果不存在则添加。

Answer 6

你在这里有两个广泛的策略，我预计两者都不会提供很好的性能（但这对你的使用来说可能不是问题）。

1. 让您的集合注册对象进行更改。
2. 而不是不断地修改设置，只在使用时更新它。

请注意，这些解决方案的行为会略有不同。

注册更改

这涉及向集合中存储的所有对象添加一个 Observable 模式（或者一个侦听器）。

当对象在 Set 中时，Set 将注册更改。当对象发生变化时，它会向 Set 发出信号，它已发生变化，并且 Set 也会相应地发生变化。

最天真的实现是只删除所有 equals 对象，然后在任何更改时重新添加该对象。简单的实现总是一个好的开始，这样你就可以编写一个合适的测试集，然后你可以逐步提高性能。

线程安全

从多个线程使用此 Set 或其中的对象时要小心。像这样的解决方案存在很多死锁风险，因此对于 Set 和存储在其中的对象，您可能最终得到一个 ReadWriteLock。

用到就更新

另一种方法是惰性策略：仅在使用时更新集合。当对象有很多变化但集合不经常使用时，这非常有用。

它使用了以下设置思路（这让我想起了薛定谔的猫）：

If nobody is looking at the Set, does it matter what is in it?

对象仅由其接口上的行为定义。因此，您可以在使用信息时评估您的集合（并相应地更新它）。

一般备注

以下是适用于两种选择的一些说明。

期望的行为

请注意，您可能会 运行 遇到像这样的集合时非常奇怪的行为。当你从 Set 中删除一个对象时，因为它已经等于另一个对象，外界将不知道你已经删除了那个对象。

请参阅以下示例，起诉您的 Foo class:

Foo foo1 = new Foo(1);
Foo foo2 = new Foo(2);
Set<Foo> set = new MySet<Foo>();
set.add(foo1);
set.add(foo2);

foo2.foo = 1; // foo or foo2 is removed from the set.
foo2.foo = 3; // now the set contains with a foo or with 1 or with 3.

作为替代方案，您可以将存储在列表中的对象转换为您使用时设置的对象。

Answer 7

这是一个很好的问题！也许它是许多错误的来源！这不仅仅是重复的问题。即使没有重复，几乎所有方法都会 return 错误答案。考虑一个哈希集。如果即使没有创建副本，哈希值也会发生变化，contains 方法现在将 return 不正确的结果，因为对象位于错误的哈希桶中。同样，删除将无法正常工作。对于排序集，迭代器顺序将不正确。

我喜欢@Thirler 提到的 Observable 模式。其他解决方案似乎效率低下。在那里提到的可观察方法中，存在一个依赖项，即要添加到集合中的元素的实现者会在更新发生时正确地通知集合。我在这里提到的方法在某种程度上更具限制性，但将正确实现的责任传递给了集合创建者。因此，只要正确实施该集合，它就可以为该集合的所有用户工作。 （更多关于观察者模式难以实现的原因见下文）

这里是基本思路：假设你想创建一组foo对象。我们将创建一个名为 SetFoo 的 class。 foo 对象的所有方面都由集合本身维护，包括构造和对其的任何更改。任何其他用户都无法直接创建 Foo 对象，因为它是 SetFoo 的内部 class 并且构造函数是私有的或受保护的。例如，假设我们实现了一个 class SetFoo，其中 Foo 具有方法 void setX(int x) 和 Foo int getX()。 class SetFoo 会有如下方法：

Foo instance(int x)  //Returns the instance of foo if it exists, otherwise creates a new one and returns it.

假设 SetFoo 在内部维护 Foo 对象的哈希集。

现在 Foo 的 setX 方法将被定义为在 x 的值发生变化时删除元素并将其重新添加到哈希集中。

我们可以将 SetFoo 的思想扩展为包含任意数量的元素，所有这些元素都由集合维护。这对于任何类型的对象都非常容易实现，但是，它确实要求元素全部由集合维护（包括构造和所有 setter 方法）。当然，让它成为多线程安全的需要更多的工作。

从 SetFoo 的任何用户的角度来看 class 事情会很简单：

 Foo f = setFoo.instance(1);
 ....
 f.setX(2);
 ...
 f.setX(3)

 f = setFoo.instance(1);  // Would internally create a new one since it was changed.
 f= setFoo.instance(3)   // Already in the set so no new one is created.

现在我们还可以向 SetFoo 添加其他方法，例如

boolean contains (int x);
Iterator<Integer> iterator();
boolean remove(int x);
etc...

或者我们可以为 Foo 添加各种方法：

remove()  // removes foo from the set.
exists()  // if foo still in the set?
add() // add foo back to the set

在元素可以包含许多字段的情况下，我们可以使用 FooSpec class。假设 Foo 包含一个 int x 和 int y。然后 FooSpec 将有 getX, SetX, getY, setY 方法，并且可以使用 new FooSpec 构造。现在 setFoo 会有这样的方法：

 Foo instance(FooSpec fooSpec)
 Collection<Foo> instanceAll(Collection<FooSpec> col)
 ...etc

现在您可能想知道为什么观察者模式方法容易出错。使用这种方法，集合的用户必须在集合发生变化时正确地通知集合。这实际上与实现深度不可变对象的难度相同（这可能并不容易）。例如，如果集合的元素本身是集合或集合的集合，那么您需要确保在集合中的任何内容（深度）发生变化时通知集合。

将 "deeply" 通知集合的责任留给集合的用户，会给开发人员带来很多负担。最好实施一个框架，为 "deeply" 通知的对象提供。

Answer 8

我仍然不确定你是否理解其中的含义。如果您有 2 个对象，它们在任何时间点都可以彼此相等，但在另一个时间点可能不相等，因此默认情况下它们被视为单独的对象，即使此时它们看起来是相同的。

我会从不同的角度着手，并检查该集合是否包含执行更改时对象将变成的对象，如果您不希望它存在于该集合中，因为它等于另一个对象。

Answer 9

使用安全发布：不允许访问集合或其元素；改为发布深层副本。

您需要一种复制 Foo 的方法；我假设有一个复制构造函数。

private Set<Foo> set;

public Set<Foo> getFoos() {
    // using java 8
    return set.stream().map(Foo::new).collect(Collectors.toSet());
}

您还应该保存 Foo 的副本，而不是保存 foo，因为调用者将引用添加的 Foos，因此客户端可以改变它们。为此添加访问器方法：

public boolean addFoo(Foo foo) {
    return set.add(new Foo(foo));
}

Answer 10

以下是我看到的一种方法的几个方面

使用 'Dynamic Element Set'

最好明确区分 mutable 设置 class 用于 immutable 元素，以及另一组 class 用于 mu table 个元素

mutable 元素的集合 class 将是 'dynamic element sets'，并且要求每个元素都有一个指向包含集合

的指针

元素本身在修改时注册更改

您可能必须为集合中包含的元素提供相应的包装器 class，以便它可以注册到包含的元素

用于快速单线程唯一性检查的哈希 table

将元素添加到集合时，集合将计算该元素的散列，并将其添加到 table（我确信这就是集合的工作方式）

用它来检查唯一性并在 O(1) 时间内进行消除

多线程情况下的脏/干净状态

更新元素时​​，将包含集标记为 'dirty'

当包含集变脏时，您可以在某个时候重新运行唯一性测试以查看是否所有元素都是唯一的。

当发生这种情况时，它可能应该阻止对元素的任何修改，直到它完成

有了这个，您可能 偏离了完全唯一性 属性。

考虑一下：列表中有 3 个元素：A、B 和 C，每个元素都具有唯一值

您将元素 B 更改为与 A 相同的值 标记为脏

将元素 A 更改为不同的唯一值 仍标记为脏

运行唯一性检查

因此，如果您不需要 绝对值 设置 属性，而只是一个近似值，这可能有效

否则，如果您需要绝对集 属性，在多线程情况下可能无法工作

更新似乎很便宜，所以您也许可以侥幸逃脱

这真的是'set'吗？

所以，这有点假设元素只从为集合提供的接口修改

当您将元素的基 class 包装到集合中时，它可能应该对元素进行深度复制以帮助防止元素从未注册的引用对象中获得修改

所以它不仅仅是一个 'set'，而是对传递的元素类型提出了要求

为元素添加界面层class

因此，我猜元素本身在某种意义上是新对象的一部分

其他想法

所以当然，如果一次元素可以与另一个元素相同，那么将来它也可能再次变为不同

您是在暗示 a 正在搜索的解决方案将需要在需要那种 属性 的特定问题中：暂时重复的元素需要淘汰