从 Set 中获取元素

Question

为什么 Set 不提供获取与另一个元素相等的元素的操作？

Set<Foo> set = ...;
...
Foo foo = new Foo(1, 2, 3);
Foo bar = set.get(foo);   // get the Foo element from the Set that equals foo

我可以问Set是否包含等于bar的元素，那么为什么我无法获取该元素呢？ :(

澄清一下，equals 方法被重写，但它只检查其中一个字段，而不是所有字段。因此，两个被视为相等的 Foo 对象实际上可以具有不同的值，这就是为什么我不能只使用 foo。

Answer 1

要回答这个精确的问题“为什么Set不提供获取与另一个元素相等的元素的操作？”，答案是：因为集合的设计者框架不是很有前瞻性。他们没有预料到您非常合法的用例，天真地尝试“对数学集合抽象进行建模”（来自 javadoc），只是忘记添加有用的 get() 方法。

现在隐含的问题“如何获取元素”：我认为最好的解决方案是使用 Map 而不是 设置，将元素映射到自身。这样，您就可以高效从“集合”中检索元素，因为Map的get()方法将使用高效的哈希表或树来查找元素算法。如果需要，您可以编写自己的 Set 实现，它提供附加的 get() 方法，封装 Map。

我认为以下答案是不好或错误的：

“您不需要获取元素，因为您已经有一个相等的对象”：断言是错误的，正如您在问题中已经表明的那样。两个相等的对象仍然可以具有与对象相等性无关的不同状态。目标是访问 Set 中包含的元素的状态，而不是用作“查询”的对象的状态。

“你别无选择，只能使用迭代器”：这是对集合的线性搜索，对于大型集合来说效率很低（具有讽刺意味的是，Set 在内部被组织为哈希映射或树，可以高效查询）。不要这样做！通过使用这种方法，我在现实系统中看到了严重的性能问题。在我看来，缺少 get() 方法的可怕之处并不在于解决它有点麻烦，而是大多数程序员会使用线性搜索方法而不考虑其含义。

Answer 2

如果元素相等，那么获取元素就没有意义了。 Map 更适合此用例。

---

如果您仍然想查找该元素，您别无选择，只能使用迭代器：

public static void main(String[] args) {

    Set<Foo> set = new HashSet<Foo>();
    set.add(new Foo("Hello"));

    for (Iterator<Foo> it = set.iterator(); it.hasNext(); ) {
        Foo f = it.next();
        if (f.equals(new Foo("Hello")))
            System.out.println("foo found");
    }
}

static class Foo {
    String string;
    Foo(String string) {
        this.string = string;
    }
    @Override
    public int hashCode() { 
        return string.hashCode(); 
    }
    @Override
    public boolean equals(Object obj) {
        return string.equals(((Foo) obj).string);
    }
}

Answer 3

如果你有一个相同的对象，为什么你需要集合中的那个呢？如果仅通过键“相等”，则 Map 将是更好的选择。

无论如何，下面的代码可以做到这一点：

Foo getEqual(Foo sample, Set<Foo> all) {
  for (Foo one : all) {
    if (one.equals(sample)) {
      return one;
    }
  } 
  return null;
}

使用 Java 8，这可以成为一个行：

return all.stream().filter(sample::equals).findAny().orElse(null);

或者（如果 equals() 按预期工作）：

return all.contains(sample) ? sample : null;

Answer 4

不幸的是，Java 中的默认集并非旨在提供“获取”操作，正如 jschreiner 准确解释的那样。

使用迭代器查找感兴趣的元素的解决方案（由dacwe建议）或删除元素并重新添加它的值已更新（由 KyleM），可以工作，但效率可能非常低。

重写 equals 的实现，使非相等的对象“相等”，如 David Ogren，很容易造成维护问题。

恕我直言，使用 Map 作为显式替换（正如许多人所建议的那样）会使代码不太优雅。

如果目标是访问集合中包含的元素的原始实例（希望我正确理解您的用例），那么这是另一个可能的解决方案。

---

我个人在使用 Java 开发客户端-服务器视频游戏时也有同样的需求。就我而言，每个客户端都有存储在服务器中的组件的副本，问题是每当客户端需要修改服务器的对象时。

通过互联网传递对象意味着客户端无论如何都有该对象的不同实例。为了将这个“复制的”实例与原始实例相匹配，我决定使用 Java UUID。

因此，我创建了一个抽象类 UniqueItem，它自动为其子类的每个实例提供一个随机的唯一 id。

此 UUID 在客户端和服务器实例之间共享，因此通过这种方式，只需使用 Map 即可轻松匹配它们。

然而，在类似的用例中直接使用 Map 仍然不优雅。有人可能会争辩说，使用地图的维护和处理可能会更复杂。

由于这些原因，我实现了一个名为 MagicSet 的库，它使 Map 的使用对开发人员来说“透明”。

https://github.com/ricpacca/magicset

---

与原始 Java HashSet 一样，MagicHashSet（它是一个库中提供的 MagicSet 实现的一部分）使用后备 HashMap，但它不是将元素作为键，将虚拟值作为值，而是使用元素的 UUID 作为键，将元素本身作为值。与普通的 HashSet 相比，这不会导致内存使用的开销。

此外，MagicSet 可以完全用作 Set，但还有一些提供附加功能的方法，如 getFromId()、popFromId()、removeFromId() 等。

使用它的唯一要求是您想要的任何元素MagicSet 中的存储需要扩展抽象类 UniqueItem。

---

下面是一个代码示例，设想从 MagicSet 检索城市的原始实例，给定具有相同 UUID（甚至只是其 UUID）的该城市的另一个实例。

class City extends UniqueItem {

    // Somewhere in this class

    public void doSomething() {
        // Whatever
    }
}

public class GameMap {
    private MagicSet<City> cities;

    public GameMap(Collection<City> cities) {
        cities = new MagicHashSet<>(cities);
    }

    /*
     * cityId is the UUID of the city you want to retrieve.
     * If you have a copied instance of that city, you can simply 
     * call copiedCity.getId() and pass the return value to this method.
     */
    public void doSomethingInCity(UUID cityId) {
        City city = cities.getFromId(cityId);
        city.doSomething();
    }

    // Other methods can be called on a MagicSet too
}

Answer 5

使用 Java 8，您可以执行以下操作：

Foo foo = set.stream().filter(item->item.equals(theItemYouAreLookingFor)).findFirst().get();

但要小心，.get() 会抛出 NoSuchElementException，或者您可以操作可选项。

Answer 6

如果您的集合实际上是一个 NavigableSet（例如 TreeSet），并且 Foo 实现了 Comparable，您可以使用

Foo bar = set.floor(foo); // or .ceiling
if (foo.equals(bar)) {
    // use bar…
}

（感谢@eliran-malka 的评论提示。）

Answer 7

原因：

Set 似乎在提供比较手段方面发挥了有用的作用。它被设计为不存储重复元素。

由于这种意图/设计，如果要 get() 对存储对象的引用，然后对其进行变异，则 Set 的设计意图可能会受到阻碍，并可能导致意外行为。

来自 JavaDocs

如果将可变对象用作集合元素，则必须格外小心。如果对象的值以影响等于比较的方式更改，而该对象是集合中的元素，则不会指定集合的​​行为。

方法：

现在已经引入了 Streams，我们可以执行以下操作

mySet.stream()
.filter(object -> object.property.equals(myProperty))
.findFirst().get();

Answer 8

将set转换为list，然后使用list的get方法

Set<Foo> set = ...;
List<Foo> list = new ArrayList<Foo>(set);
Foo obj = list.get(0);

Answer 9

Object objectToGet = ...
Map<Object, Object> map = new HashMap<Object, Object>(set.size());
for (Object o : set) {
    map.put(o, o);
}
Object objectFromSet = map.get(objectToGet);

如果您只执行一次获取，则性能不会很好，因为您将循环所有元素，但是当对一个大集合执行多次检索时，您会注意到差异。

Answer 10

如果您查看 java.util.HashSet 实现的前几行，您将看到：

public class HashSet<E>
    ....
    private transient HashMap<E,Object> map;

因此 HashSet 无论如何都会内部使用 HashMap，这意味着如果您直接使用 HashMap 并使用相同的值作为键和值，您将获得您想要的效果并节省一些内存。

Answer 11

你可以使用迭代器类

import java.util.Iterator;
import java.util.HashSet;

public class MyClass {
 public static void main(String[ ] args) {
 HashSet<String> animals = new HashSet<String>();
animals.add("fox");
animals.add("cat");
animals.add("dog");
animals.add("rabbit");

Iterator<String> it = animals.iterator();
while(it.hasNext()) {
  String value = it.next();
  System.out.println(value);   
 }
 }
}

Answer 12

看起来正确使用的对象是 Interner ：

为其他不可变对象提供与 String.intern() 等效的行为
类型。常见的实现可从 实习生
类。

它还有一些非常有趣的杠杆，例如 concurrencyLevel 或使用的引用类型（可能值得注意的是，它不提供 SoftInterner，我认为它比 WeakInterner 更有用）。

Answer 13

我知道，这个问题很久以前就被问过并回答过，但是如果有人感兴趣，这是我的解决方案 - 由 HashMap 支持的自定义集类：

http://pastebin.com/Qv6S91n9

您可以轻松实现所有其他 Set 方法。

Answer 14

去过那儿做过吗！如果您使用 Guava，将其转换为地图的快速方法是：

Map<Integer,Foo> map = Maps.uniqueIndex(fooSet, Foo::getKey);

Answer 15

如果你想要 HashSet 中的第 n 个元素，你可以使用下面的解决方案，
这里我在HashSet中添加了ModelClass的对象。

ModelClass m1 = null;
int nth=scanner.nextInt();
for(int index=0;index<hashset1.size();index++){
    m1 = (ModelClass) itr.next();
    if(nth == index) {
        System.out.println(m1);
        break;
    }
}

Answer 16

因为 Set 的任何特定实现可能是也可能不是随机访问。

您始终可以获得 迭代器 并单步执行 Set，一旦找到相等的元素，就使用迭代器的 next() 方法返回所需的结果。无论实现如何，这都有效。如果实现不是随机访问（想象一个链表支持的 Set），则接口中的 get(E element) 方法将具有欺骗性，因为它必须迭代集合才能找到元素返回，并且 get(E element) 似乎暗示这是必要的，Set 可以直接跳转到要获取的元素。

当然，contains() 可能需要也可能不需要做同样的事情，具体取决于实现，但这个名称似乎不会引起同样的误解。

Answer 17

是的，使用 HashMap ...但是以一种特殊的方式：我在尝试使用 HashMap 作为伪 Set 时预见到的陷阱是Map/Set 的“实际”元素与“候选”元素（即用于测试equal 元素是否已存在的元素）之间可能存在混淆。这远非万无一失，但可以让您远离陷阱：

class SelfMappingHashMap<V> extends HashMap<V, V>{
    @Override
    public String toString(){
        // otherwise you get lots of "... object1=object1, object2=object2..." stuff
        return keySet().toString();
    }

    @Override
    public V get( Object key ){
        throw new UnsupportedOperationException( "use tryToGetRealFromCandidate()");
    }

    @Override
    public V put( V key, V value ){
       // thorny issue here: if you were indavertently to `put`
       // a "candidate instance" with the element already in the `Map/Set`: 
       // these will obviously be considered equivalent 
       assert key.equals( value );
       return super.put( key, value );
    }

    public V tryToGetRealFromCandidate( V key ){
        return super.get(key);
    }
}

然后这样做：

SelfMappingHashMap<SomeClass> selfMap = new SelfMappingHashMap<SomeClass>();
...
SomeClass candidate = new SomeClass();
if( selfMap.contains( candidate ) ){
    SomeClass realThing = selfMap.tryToGetRealFromCandidate( candidate );
    ...
    realThing.useInSomeWay()...
}

但是...您现在希望候选者以某种方式自毁，除非程序员实际上立即将其放入Map/Set...您希望contains“污染”candidate，以便任何使用它，除非它加入>Map 使它成为“诅咒”。也许您可以让 SomeClass 实现一个新的 Taintable 接口。

更令人满意的解决方案是 GettableSet，如下所示。但是，要实现此目的，您必须负责 SomeClass 的设计，以使所有构造函数不可见（或者......能够并愿意设计和使用包装类it):

public interface NoVisibleConstructor {
    // again, this is a "nudge" technique, in the sense that there is no known method of 
    // making an interface enforce "no visible constructor" in its implementing classes 
    // - of course when Java finally implements full multiple inheritance some reflection 
    // technique might be used...
    NoVisibleConstructor addOrGetExisting( GettableSet<? extends NoVisibleConstructor> gettableSet );
};

public interface GettableSet<V extends NoVisibleConstructor> extends Set<V> {
    V getGenuineFromImpostor( V impostor ); // see below for naming
}

实现：

public class GettableHashSet<V extends NoVisibleConstructor> implements GettableSet<V> {
    private Map<V, V> map = new HashMap<V, V>();

    @Override
    public V getGenuineFromImpostor(V impostor ) {
        return map.get( impostor );
    }

    @Override
    public int size() {
        return map.size();
    }

    @Override
    public boolean contains(Object o) {
        return map.containsKey( o );
    }

    @Override
    public boolean add(V e) {
        assert e != null;
        V result = map.put( e,  e );
        return result != null;
    }

    @Override
    public boolean remove(Object o) {
        V result = map.remove( o );
        return result != null;
    }

    @Override
    public boolean addAll(Collection<? extends V> c) {
        // for example:
        throw new UnsupportedOperationException();
    }

    @Override
    public void clear() {
        map.clear();
    }

    // implement the other methods from Set ...
}

你的 NoVisibleConstructor 类看起来像这样：

class SomeClass implements NoVisibleConstructor {

    private SomeClass( Object param1, Object param2 ){
        // ...
    }

    static SomeClass getOrCreate( GettableSet<SomeClass> gettableSet, Object param1, Object param2 ) {
        SomeClass candidate = new SomeClass( param1, param2 );
        if (gettableSet.contains(candidate)) {
            // obviously this then means that the candidate "fails" (or is revealed
            // to be an "impostor" if you will).  Return the existing element:
            return gettableSet.getGenuineFromImpostor(candidate);
        }
        gettableSet.add( candidate );
        return candidate;
    }

    @Override
    public NoVisibleConstructor addOrGetExisting( GettableSet<? extends NoVisibleConstructor> gettableSet ){
       // more elegant implementation-hiding: see below
    }
}

PS 这样一个 NoVisibleConstructor 类的一个技术问题：可能会反对这样一个类本质上是final，这可能是不可取的。实际上，您始终可以添加一个虚拟无参数受保护的构造函数：

protected SomeClass(){
    throw new UnsupportedOperationException();
}

...这至少可以让子类编译。然后，您必须考虑是否需要在子类中包含另一个 getOrCreate() 工厂方法。

最后一步是一个抽象基类（注意列表的“元素”，集合的“成员”），就像您的集合成员一样（如果可能的话 - 再次，使用包装器的范围类，其中该类不在您的控制之下，或者已经具有基类等），以实现最大程度的实现隐藏：

public abstract class AbstractSetMember implements NoVisibleConstructor {
    @Override
    public NoVisibleConstructor
            addOrGetExisting(GettableSet<? extends NoVisibleConstructor> gettableSet) {
        AbstractSetMember member = this;
        @SuppressWarnings("unchecked") // unavoidable!
        GettableSet<AbstractSetMembers> set = (GettableSet<AbstractSetMember>) gettableSet;
        if (gettableSet.contains( member )) {
            member = set.getGenuineFromImpostor( member );
            cleanUpAfterFindingGenuine( set );
        } else {
            addNewToSet( set );
        }
        return member;
    }

    abstract public void addNewToSet(GettableSet<? extends AbstractSetMember> gettableSet );
    abstract public void cleanUpAfterFindingGenuine(GettableSet<? extends AbstractSetMember> gettableSet );
}

...用法相当明显（在您的 SomeClass 内） s static 工厂方法）：

SomeClass setMember = new SomeClass( param1, param2 ).addOrGetExisting( set );

Answer 18

哈希码的契约明确指出：

“如果根据 Object 方法，两个对象相等，则对这两个对象调用 hashCode 方法必须产生相同的整数结果。”

所以你的假设：

“澄清一下，equals 方法被重写，但它只检查其中之一
田野，不是全部。因此两个被认为相等的 Foo 对象可以
实际上有不同的值，这就是为什么我不能只使用 foo。”

是错误的，你违反了合同。如果我们看一下 Set 接口的“contains”方法，我们会发现：

布尔包含(Object o);
如果此集合包含指定元素，则返回 true。更多的
形式上，当且仅当该集合包含一个元素时返回 true
“e”使得 o==null ？ e==null : o.equals(e)

要完成您想要的任务，您可以使用 Map 来定义键，并使用定义对象彼此不同或相等的键来存储元素。

Answer 19

如果您有一个 NavigableSet（例如 TreeSet），您可以执行以下操作：

public static <E> E get(NavigableSet<E> set, E key) {
    return set.tailSet(key, true).floor(key);
}

对于 HashSet 及其后代（如 ），事情稍微棘手一些>LinkedHashSet：

import java.util.*;
import java.lang.reflect.Field;
import java.lang.reflect.Method;

public class Test {
    private static final Field mapField;
    private static final Method hashMethod;
    private static final Method getNodeMethod;
    private static final Field keyField;
    static {
        try {
            mapField = HashSet.class.getDeclaredField("map");
            mapField.setAccessible(true);
            hashMethod = HashMap.class.getDeclaredMethod("hash", Object.class);
            hashMethod.setAccessible(true);
            getNodeMethod = HashMap.class.getDeclaredMethod("getNode",
                    Integer.TYPE, Object.class);
            getNodeMethod.setAccessible(true);
            keyField = Class.forName("java.util.HashMap$Node").getDeclaredField("key");
            keyField.setAccessible(true);
        } catch (ReflectiveOperationException e) {
            throw new RuntimeException(e);
        }
    }

    public static <E> E get(HashSet<E> set, E key) {
        try {
            Object map = mapField.get(set);
            Object hash = hashMethod.invoke(null, key);
            Object node = getNodeMethod.invoke(map, hash, key);
            if (node == null)
                return null;
            @SuppressWarnings("unchecked")
            E result = (E)keyField.get(node);
            return result;
        } catch (ReflectiveOperationException e) {
            throw new RuntimeException(e);
        }
    }

    public static <E> E get(NavigableSet<E> set, E key) {
        return set.tailSet(key, true).floor(key);
    }

    public static void main(String[] args) {
        HashSet<Integer> s = new HashSet<>();
//      HashSet<Integer> s = new LinkedHashSet<>();
//      TreeSet<Integer> s = new TreeSet<>();
        for (int i = 0; i < 100_000; i++)
            s.add(i);
        Integer key = java.awt.event.KeyEvent.VK_FIND;
        Integer hidden = get(s, key);
        System.out.println(key);
        System.out.println(hidden);
        System.out.println(key.equals(hidden));
        System.out.println(key == hidden);
    }
}

Answer 20

可能解决这种情况的快速帮助方法：

<T> T onlyItem(Collection<T> items) {
    if (items.size() != 1)
        throw new IllegalArgumentException("Collection must have single item; instead it has " + items.size());

    return items.iterator().next();
}

Answer 21

尝试使用数组：

ObjectClass[] arrayName = SetOfObjects.toArray(new ObjectClass[setOfObjects.size()]);

Answer 22

以下可以是一种方法

   SharedPreferences se_get = getSharedPreferences("points",MODE_PRIVATE);
   Set<String> main = se_get.getStringSet("mydata",null);
   for(int jk = 0 ; jk < main.size();jk++)
   {
      Log.i("data",String.valueOf(main.toArray()[jk]));
   }