是否存在集合中的任何一个成员都可以解决的集合？

Question

我试图在 Java（或 Groovy）中找到一个数据结构，它可以像这样工作：MemberAdressableSetsSet mass = new MemberAdressableSetsSet();mass.addSet(["a","b"]);mass.addSet(["c","d","e"]);mass.get("d").add("f");String output = Arrays.toString(mass.get("e").toArray());System.out.println(output); // [ "c", "d", "e", "f" ] (ordering irrelevant)有没有这样的东西？如果没有，有没有办法用普通的 Java 代码来实现这样的东西，而不会给 CPU 或数周的内存带来噩梦？编辑：更严格MemberAdressableSetsSet mass = new MemberAdressableSetsSet();Set<String> s1 = new HashSet<String>();s1.add("a");Set<String> s2 = new HashSet<String>();s2.add("c");s2.add("d");s2.add("e");mass.addSet(s1);mass.addSet(s2);Set<String> s3 = new HashSet<String>();s3.add("a");s3.add("z");mass.addSet(s3);/* s3 contains "a", which is already in a subset of mass, so: * Either *   - does nothing and returns false or throws Exception *   - deletes "a" from its previous subset before adding s3 *      => possibly returns the old subset *      => deletes the old subset if that leaves it empty *      => maybe requires an optional parameter to be set *   - removes "a" from the new subset before adding it *      => possibly returns the new subset that was actually added *      => does not add the new subset if purging it of overlap leaves it empty *      => maybe requires an optional parameter to be set *   - merges all sets that would end up overlapping *   - adds it with no overlap checks, but get("a") returns an array of all sets containing it */mass.get("d").add("f");String output = Arrays.toString(mass.get("e").toArray());System.out.println(output); // [ "c", "d", "e", "f" ] (ordering irrelevant)mass.get("d")将返回Set<T>包含mass. "d"类似于 get() 的工作方式，例如HashMap：HashMap<String,LinkedList<Integer>> map = new HashMap<>();LinkedList<Integer> list = new LinkedList<>();list.add(9);map.put("d",list);map.get("d").add(4);map.get("d"); // returns a LinkedList with contents [9,4]

Answer 1

到目前为止我能想到的最好的看起来像这样：

import java.util.HashMap;

import java.util.Set;

public class MemberAdressableSetsSet {

    private int next_id = 1;

    private HashMap<Object,Integer> members = new HashMap();

    private HashMap<Integer,Set> sets = new HashMap();

    public boolean addSet(Set s) {

        if (s.size()==0) return false;

        for (Object member : s) {

            if (members.get(member)!=null) return false;

        }

        sets.put(next_id,s);

        for (Object member : s) {

            members.put(member,next_id);

        }

        next_id++;

        return true;

    }

    public boolean deleteSet(Object member) {

        Integer id = members.get(member);

        if (id==null) return false;

        Set set = sets.get(id);

        for (Object m : set) {

            members.remove(m);

        }

        sets.remove(id);

        return true;

    }

    public boolean addToSet(Object member, Object addition) {

        Integer id = members.get(member);

        if (id==null) throw new IndexOutOfBoundsException();

        if (members.get(addition)!=null) return false;

        sets.get(id).add(addition);

        members.put(addition,id);

        return true;

    }

    public boolean removeFromSet(Object member) {

        Integer id = members.get(member);

        if (id==null) return false;

        Set s = sets.get(id);

        if (s.size()==1) sets.remove(id);

        else s.remove(member);

        members.remove(member);

        return true;

    }

    public Set getSetClone(Object member) {

        Integer id = members.get(member);

        if (id==null) throw new IndexOutOfBoundsException();

        Set copy = new java.util.HashSet(sets.get(id));

        return copy;

    }

}

这有一些缺点：

• 集合不可直接访问，这使得所有Set未通过显式定义的转换方法公开的方法和属性都不可访问，除非克隆是可接受的选项

• 类型信息丢失。

• 说Set<Date>加了一个。
  它不会抱怨试图添加，例如，一个File对象到那个集合。

至少丢失的 Sets 类型信息没有扩展到它们的成员：它们Set.contains()仍然按预期工作，尽管双方Object在被比较之前都被类型转换为contains()。因此，当被问及是否包含时，包含的集合(Object)3不会返回 true (Object)3L，反之亦然。

Answer 2

您需要多久访问一个元素？可能值得使用地图并将相同的Set引用存储在多个键下。

我会防止地图和子集的外部突变，并提供辅助方法来完成所有更新：

public class MemberAdressableSets<T> {

    Map<T, Set<T>> data = new HashMap<>();

    public void addSet(Set<T> dataSet) {

        if (dataSet.stream().anyMatch(data::containsKey)) {

            throw Exception("Key already in member addressable data");

        }

        Set<T> protectedSet = new HashSet<>(dataSet);

        dataSet.forEach(d -> data.put(d, protectedSet));

    }

    public void updateSet(T key, T... newData) {

        Set<T> dataSet = data.get(key);

        Arrays.stream(newData).forEach(dataSet::add);

        Arrays.stream(newData).forEach(d -> data.put(d, dataSet));

    }

    public Set<T> get(T key) {

        return Collections.unmodifiableSet(data.get(key));

    }

}

或者，如果密钥不存在，您可以更新addSet和updateSet创建新实例并创建never 。您还需要扩展此类以处理合并集的情况。即处理用例：SetupdateSetthrow

mass.addSet(["a","b"]);

mass.addSet(["a","c"]);

Answer 3

该解决方案允许诸如mass.get("d").add("f");影响存储在 中的子集之类的事情mass，但有很大的缺点。

import java.util.Iterator;

import java.util.LinkedHashSet;

import java.util.Set;

public class MemberAdressableSetsSetDirect {

    private LinkedHashSet<Set> sets;

    public void addSet(Set newSet) {

        sets.add(newSet);

    }

    public Set removeSet(Object member) {

        Iterator<Set> it = sets.iterator();

        while (it.hasNext()) {

            Set s = it.next();

            if (s.contains(member)) {

                it.remove();

                return s;

            }

        }

        return null;

    }

    public int removeSets(Object member) {

        int removed = 0;

        Iterator<Set> it = sets.iterator();

        while (it.hasNext()) {

            Set s = it.next();

            if (s.contains(member)) {

                it.remove();

                removed++;

            }

        }

        return removed;

    }

    public void deleteEmptySets() {

        sets.removeIf(Set::isEmpty);

    }

    public Set get(Object member) {

        for (Set s : sets) {

            if (s.contains(member)) return s;

        }

        return null;

    }

    public Set[] getAll(Object member) {

        LinkedHashSet<Set> results = new LinkedHashSet<>();

        for (Set s : sets) {

            if (s.contains(member)) results.add(s);

        }

        return (Set[]) results.toArray();

    }

}

没有针对重叠的内置保护，因此我们的访问不可靠，并且引入了无数空集的可能性，这些空集需要通过手动调用定期清除，因为此解决方案无法检测子集是否被deleteEmptySets()修改直接访问。

MemberAdressableSetsSetDirect massd = new MemberAdressableSetsSetDirect();

Set s1 = new HashSet();Set s2 = new HashSet();Set s3 = new HashSet();

s1.add("a");s1.add("b");

s2.add("c");s2.add("d");

s3.add("e");

massd.addSet(s1);massd.addSet(s2);

massd.get("c").add("a");

// massd.get("a") will now either return the Set ["a","b"] or the Set ["a","c","d"]

// (could be that my usage of a LinkedHashSet as the basis of massd

//  at least makes it consistently return the set added first)

massd.get("e").remove("e");

// the third set is now empty, can't be accessed anymore,

// and massd has no clue about that until it's told to look for empty sets

massd.get("c").remove("d");

massd.get("c").remove("c");

// if LinkedHashSet makes this solution act as I suspected above,

// this makes the third subset inaccessible except via massd.getAll("a")[1]

此外，此解决方案也无法保留类型信息。

这甚至不会发出警告：

MemberAdressableSetsSetDirect massd = new MemberAdressableSetsSetDirect();

Set<Long> s = new HashSet<Long>();

s.add(3L);

massd.addSet(s);

massd.get(3L).add("someString");

// massd.get(3L) will now return a Set with contents [3L, "someString"]