关于HashSet O(1)的问题

Question

bobo老师，我想问一下，HashSet如果Hash运算重复的话是以链表或者红黑树的形式挂接的。
那查询或者添加删除操作怎么会是O(1)级别的呢？
不应该是链表的长度，如果说是红黑树的话是O(logn)级别的吗？

Answer 1

liuyubobobo 2020-07-29 14:07:17

准确的说是 O(logk)，k 是所有产生哈希冲突的元素数量。但因为对于哈希表来说，哈希冲突是一个常数，冲突高到一定程度，会重新扩展哈希表。所以是 O(1) 的。

继续加油！：）

• 提问者 qq_CodeCC_tvSTZ2 #1

  非常感谢！

• 提问者 qq_CodeCC_tvSTZ2 #2

  就是说对于哈希表的每个桶来说，这个桶的大小有限制，如果大于某一个阈值，就会重新扩展哈希表？而阈值是不变的，所以logk是一个常数，不会随着总数据量N的大小变化而变化，所以是O(1)的对吗？

• liuyubobobo 回复 提问者 qq_CodeCC_tvSTZ2 #3

  是这个意思：）