代码之家 › 专栏 › 技术社区 › user7993435

Java LinkedHashSet remove(Object obj)方法常数/线性时间复杂度?

collections algorithm java

user7993435 · 技术社区 · 7 年前

与哈希集类似,[LinkedHashSet]为基本操作(添加、包含和)提供恒定时间性能去除 ),假设哈希函数将元素正确地分散在桶中。

我理解HashSet如何为remove(Object obj)提供恒定的时间性能,但由于LinkedHashSet也需要维护一个链表,并且删除一个特定的元素需要遍历链表,因此在我看来,remove(Object obj)应该需要线性时间。我错过什么了吗?

我能想到的唯一解释是,哈希表(由LinkedHashSet维护)中的每个条目都包含对链接列表中相应节点的引用,因此在链接列表中定位节点需要恒定的时间。但我不确定这是否真的是实施。。。

谢谢

1 回复 | 直到 7 年前

Hulk 7 年前

LinkedHashSet 除了哈希表之外,还维护节点之间的链接。删除时不需要遍历整个列表,只需要更新列表的邻居。访问特定元素并不比 HashSet .

推荐文章

SkyWalker · 在JavaScript中,合并日期-时间序列的有效算法是什么?

1 年前

root · 计数算法

1 年前

André Silveira · 使用循环将数组的每个槽递增1。数组的大小是传递给函数的参数

2 年前

danial · 如何在多个字符串的每个位置找到最频繁的字符

2 年前

Manny · 如何比较Perl中的字符串?

2 年前

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Diret · 获取范围内每个数字的子倍数的算法

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

TryingToLearn · 我如何为通用遥控器构造一个类,该遥控器向连接到它的各种设备发送开/关命令?

2 年前

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前