找出给定集合（未排序）是否是主集合的完美子集的最佳方法是什么。我必须在我的程序中进行一些验证，在那里我必须将客户端请求集与注册的内部能力集进行比较。
我想通过对内部能力集进行排序（一旦注册就不会改变）并对客户端请求集中的每个元素进行二进制搜索。这是我能得到的最好的吗？我怀疑可能有更好的方法。
任何的想法？
问候，
微内核
问问题
155 次
3 回答
3
假设您选择的语言没有像 Java 对HashSet那样实现具有“包含在集合中”方法的集合类......
一个好的方法是使用哈希图（又名哈希又名关联数组）
如果您的超集不是太大，请生成一个哈希映射，将较大集中的每个对象映射到一个真值。
然后，遍历子集中的每个元素。尝试在生成的 hashmap 中查找元素。如果你失败了，你的小集合就不是一个人的子集。如果您完成循环而没有失败，那就是。
于 2010-05-24T18:39:49.567 回答
1
这取决于你的集合中有多少元素。对于较大的集合，通常使用 Hashset 作为主集，结果是最佳性能。
于 2010-05-24T18:41:29.113 回答
0
由于您知道内部能力集，您可以使用完美的散列函数来测试客户端请求集的元素。
于 2010-05-24T18:45:42.700 回答