java - 发生冲突时从 LinkedHashMap 检索元素的时间复杂度是多少？

Question

假设我有一个 LinkedHashMap 对象，它只有 8 个从 0 到 7 编号的桶。
现在我想添加元素。我添加了7个元素，结果如下:

1) Element_1: Bucket number 2. 这成为LinkedHashMap维护插入顺序的链表的开始。
1) Element_2:桶号 3。这链接到 Element_1
2) Element_3:桶号 1。这链接到 Element_2
3) Element_4:桶号 4。这链接到 Elemetn_3
4) Element_5:桶号 5。这链接到 Element_4
5) Element_6: Bucket Number 3. 这与 Element_5 相关联(发生了碰撞)
6) Element_7:桶号 3。这与 Element_6 相关联(再次碰撞)

现在假设我想检索 Element_7。这个元素的散列给了我 桶号 3 .现在 中的元素桶号 3 是 元素_2 , 元素_6 , 元素_7 .
那么下面两个的遍历顺序是什么:
a) Element_2-> Element_3->Element_4->Element_5->Element_6->Element_7。
或
b) Element_2->Element_6->Element_7。

我认为答案是 (a) 因为 LinkedHashMap 维护一个链表来维护插入顺序。因此，如果顺序是 (b)，则意味着特定元素存储了两个引用，一个用于按插入顺序排列的下一个元素，另一个用于同一存储桶中的下一个元素。

如果答案是 (b)，特定元素如何决定访问哪个元素，即在两个引用中，选择哪一个。

用例场景是假设的，它可能与元素数量少于桶数的事实无关，冲突的机会更少。
请记住上述情况回答。
提前致谢。

Answer 1

LinkedHashMap 扩展了 HashMap，因此链接与 get 无关。 ，因此添加链接后，它们不应该使 LinkedHashMap 在 get 上的效率降低- 因为 get 不需要那个链接。