该类为基本操作(添加、删除、包含和大小)提供了恒定时间性能
这让我非常困惑,因为我不明白如何可能对比较操作进行恒定时间,即 O(1)。以下是我的想法:
如果这是真的,那么无论我往我的 HashSet 中倾倒多少数据,我都能以恒定时间访问任何元素。也就是说,如果我将一个元素放入我的 HashSet,则查找它将花费与我有 googolplex 元素相同的时间。
然而,如果我有恒定数量的桶或者一致的哈希函数,这是不可能的,因为对于任意固定数量的桶,该桶中的元素数量将随着集合中的元素数量呈线性增长(如果数字足够大,则增长速度较慢)。
那么,这只有在每次插入元素时(或每隔一段时间)更改哈希函数才能实现。一个永远没有冲突的简单哈希函数将满足这个需求。对于字符串的一个玩具示例可以是:取字符串的 ASCII 值并将它们连接在一起(因为添加可能导致冲突)。
然而,对于足够大的字符串或数字等,这个哈希函数和任何其他类似的哈希函数都很可能失败。你可以形成的桶的数量立即受到堆栈/堆空间的限制等的影响。因此,无法无限地跳过内存位置,因此您最终必须填补间隙。
但是,如果在某个时刻重新计算哈希函数,则此操作所需的时间只能与找到通过 N 个点的多项式相同,即 O(nlogn)。
因此,我感到困惑。虽然我相信 HashSet 可以在 O(n/B) 时间内访问元素,其中 B 是它决定使用的桶的数量,但我不明白 HashSet 如何可能在 O(1) 时间内执行添加或获取函数。
注意:这篇文章和这篇文章都没有解决我所列举的问题。