什么是更好的方法来查找给定的集合是否是集合的完美子集 - 如果给定子集没有排序？

Question

找到给定集合（未排序）是否为主集合的完美子集的最佳方法是什么？我必须在我的程序中进行一些验证，我需要将客户端请求集与已注册的内部功能集进行比较。

我想通过对内部功能集进行排序（一旦注册后不会更改）并对客户端的请求集中的每个元素执行二进制搜索。这是我能得到的最好的吗？我怀疑可能会有更好的方法。

有什么想法？

问候，

微内核

Answer 1

假设您所选择的语言不执行一套类“一组包含”方法已经像Java那样与HashSet ...

一个好的方法是使用hashmaps（aka hashes aka关联阵列）

如果你的超集不是太大，生成一个hashmap映射每个对象的hashmap更大的设置为真正的价值。

然后，遍历子集中的每个元素。尝试在生成的散列映射中查找元素。 如果你失败了，你的小组不是一个子集。如果你完成循环而没有失败，那就是。

Answer 2

它取决于您的设置中有多少个元素。 对于更大的集合，通常使用Hashset为主集展现出最佳性能。

Answer 3

由于您知道内部功能集，因此您可以使用perfect hash function来测试客户端请求集的元素。