java对整数使用哈希集

Question

我有两张单子。我想在两者中找出最小的公共数。我考虑过使用HashSet，因为它不允许重复。在添加两个列表元素时，我可以找到常见的数字。HashSet只需要constant time进行插入。这可以让我O(n)找到两个中最小的公共点。但是HashSet如何在constant time中插入n元素呢？在这种情况下，添加最后一个元素需要O(n)时间，因为要找到正确的bucket，在最坏的情况下，它必须将hashcode与n个bucket进行比较。请更正此错误，并提前感谢

Answer 1

你可以在任何算法书中找到答案（例如Corman，Knuth）。 简而言之：bucketIndex=toPositiveInteger（hashcode（））%buckets。长度

Answer 2

算法似乎非常简单：

1. 构造一个HashSet包含列表A的元素
2. 将min初始化为类似Integer.MAX_VALUE的大值
3. 对于B中的每个元素，测试它是否在HashSet中。如果是，并且小于min，则更新min

在任何情况下，哈希算法或多或少都会假设哈希实际上是一个好的哈希函数，并且您不必担心O（n）最坏的情况

Answer 3

查找bucket是一个固定的时间——它只取决于给定对象的哈希值，而不取决于现有对象