java - LinkedHashMap 基本上是 O(1) '包含'的 LinkedList 吗？

Question

我正面临一个微优化，我contains经常在LinkedList上调用。将其更改为LinkedHashMap是个好主意吗？

注意：我只是添加并检查列表是否包含某个值。

Answer 1

它比“只是一个LinkedList带有平均情况的O(1)包含”要复杂一些，但本质上 - 功能说是的。

ALinkedHashMap允许O(1)包含并保持元素按插入顺序排列 - 与LinkedList. 您可能还想看看LinkedHashSet

但是，如果您想要重复的条目，您可能会遇到问题。A LinkedHashMapandLinkedHashSet是实现Set和Map接口，而不是List接口，所以它们不允许重复。

Answer 2

是的，LinkedHashMap 提供 O(1) 成员资格检查

与 HashMap 一样，它为基本操作（添加、包含和删除）提供恒定时间性能，假设哈希函数在桶中正确分散元素。

另请注意

由于维护链表的额外费用，性能可能略低于 HashMap，但有一个例外：迭代 LinkedHashMap 的集合视图所需的时间与映射的大小成正比，而不管其容量如何. HashMap 的迭代可能更昂贵，需要的时间与其容量成正比。

http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHashMap.html

如果您不需要可预测的排序，则 HashMap 在插入/修改时会稍快一些，因为它不需要维护链表来保持排序。

Answer 3

不; aLinkedList是 a List，而 aLinkedHashMap是 a Map。

除此之外，LinkedHashMap不保证O(1) 包含；实际上，LinkedHashMap.contains是 O(n)。如果使用完美的散列或（大致）均匀分布键到桶（即最佳情况），则恒定时间contains是可能的，但在发生冲突的情况下，它是具有常数因子 0 < k <的平均情况线性时间1.

您似乎想要的是Set平均情况下性能与 相当的插入顺序HashMap.contains，因此我建议您查看LinkedHashSet。

This implementation differs from HashSet in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order).