java对整数使用哈希集
我有两张单子。我想在两者中找出最小的公共数。我考虑过使用HashSet,因为它不允许重复。在添加两个列表元素时,我可以找到常见的数字。HashSet只需要constant time
进行插入。这可以让我O(n)
找到两个中最小的公共点。但是HashSet如何在constant time
中插入n
元素呢?在这种情况下,添加最后一个元素需要O(n)
时间,因为要找到正确的bucket,在最坏的情况下,它必须将hashcode与n个bucket进行比较。请更正此错误,并提前感谢
# 1 楼答案
你可以在任何算法书中找到答案(例如Corman,Knuth)。 简而言之:bucketIndex=toPositiveInteger(hashcode())%buckets。长度
# 2 楼答案
算法似乎非常简单:
HashSet
包含列表A
的元素李>min
初始化为类似Integer.MAX_VALUE
的大值李>B
中的每个元素,测试它是否在HashSet
中。如果是,并且小于min
,则更新min
李>在任何情况下,哈希算法或多或少都会假设哈希实际上是一个好的哈希函数,并且您不必担心O(n)最坏的情况
# 3 楼答案
查找bucket是一个固定的时间——它只取决于给定对象的哈希值,而不取决于现有对象