关于HashSet O(1)的问题

来源：2-8 实现邻接表的改进

qq_CodeCC_tvSTZ2

2020-07-29

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

写回答

1回答

liuyubobobo

2020-07-29

已采纳

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

继续加油！：）

liuyubobobo

qq_CodeCC_tvSTZ2

是这个意思：）

2020-07-30

共3条回复

玩转算法系列--图论精讲（Java版）

30+小时系统学习，bobo带你克服被图论支配的恐惧

1591 学习 · 324 问题

相似问题

回答 1

回答 1

回答 1

回答 3

回答 1