Teo*_*tus 12 theory algorithm hash hashset
当我看到有趣的声明时,我正在阅读HashSet上的javadoc:
此类为基本操作提供恒定的时间性能(添加,删除,包含和大小)
这让我很困惑,因为我不明白人们如何能够获得恒定的时间,O(1),比较操作的性能.这是我的想法:
如果这是真的,那么无论我将多少数据转储到我的HashSet中,我都能够在恒定时间内访问任何元素.也就是说,如果我在我的HashSet中放入1个元素,它将花费相同的时间来查找它,就好像我有一个googolplex元素.
但是,如果我有一个恒定数量的桶或一致的散列函数,这是不可能的,因为对于任何固定数量的桶,该桶中的元素数量将线性增长(尽管数量很大,但速度很慢) (足够)与集合中的元素数量.
然后,这种方法的唯一方法是每次插入元素时(或每隔几次)更改一个哈希函数.一个简单的哈希函数,永远不会发生任何冲突,满足这种需求.字符串的一个玩具示例可能是:获取字符串的ASCII值并将它们连接在一起(因为添加可能会导致冲突).
但是,这种散列函数以及此类任何其他散列函数可能会因足够大的字符串或数字等而失败.您可以形成的存储桶数量会立即受到您拥有的堆栈/堆空间量等因素的限制. ,不能无限期地跳过内存中的位置,所以你最终必须填补空白.
但是如果在某个时刻重新计算哈希函数,这只能与找到通过N个点的多项式或O(nlogn)一样快.
因此到了我的困惑.虽然我会相信HashSet可以在O(n/B)时间内访问元素,其中B是它决定使用的桶的数量,但我没有看到HashSet如何在O中执行添加或获取函数( 1次.
ami*_*mit 18
桶的数量是动态的,大约是〜2n,其中n是集合中元素的数量.
请注意,HashSet给出了摊销和平均时间表现O(1),而不是最坏情况.这意味着,我们可能会O(n)不时遭受操作.
因此,当垃圾箱太紧张时,我们只需创建一个更大的新数组,然后将元素复制到其中.
这使得n操作成本增加,并且当集合中的元素数量超过时2n/2=n,这意味着,该操作的平均成本受到限制n/n=1,这是一个常数.
此外,HashMap提供的冲突次数平均也是不变的.
假设您要添加元素x.h(x)被一个元素填满的概率是〜n/2n = 1/2.它被3个元素填充的概率是〜(n/2n)^2 = 1/4(对于大的值n),依此类推.
这给你平均运行时间1 + 1/2 + 1/4 + 1/8 + ....由于此总和收敛2,意味着此操作平均需要恒定时间.