java - 如何使用 HashMap 在常数时间内从 Java 的 LinkedList 中获取元素

Question

在 Java 中，有什么方法可以从 LinkedList 集合中获取一个元素在固定时间，如果我可以存储元素插入列表的位置？我不能使用 ArrayList，因为我想在恒定时间从列表中间删除项目。

LinkedList 的 get接受 int 作为参数，复杂度为 O(N)。

在 C++ 中，我可以使用映射来存储列表的迭代器。要在恒定时间访问任何元素，我可以在哈希表中查找该元素并获取指向它的迭代器。使用迭代器，我可以到达列表中的那个条目。

1. 如何在 Java 中实现类似的功能？
2. 我们可以将迭代器存储在 HashMap 的值中并使用它来直接访问元素吗？

这是一个代码片段，展示了我如何在 C++ 中完成它。这个程序不需要 LinkedList 和 HashMap。但是想象一下像 LRU 缓存这样的东西，或者我想维护一个列表和一个映射的不同场景。

list<string> namesList;
unordered_map<string, list<string>::iterator> namesMap;

namesList.push_front("hello");
namesMap["hello"] = namesList.begin();

namesList.push_front("hi");
namesMap["hi"] = namesList.begin();

namesList.push_front("abc");
namesMap["abc"] = namesList.begin();

// Now to access "hi" on the list, I can just look it up on the map
// Get iterator to "hi" from the map and access it
auto itr = namesMap.find("hi");
if (itr != namesMap.end())
{
    // This is a simple case where my list is just storing the key
    cout << *(itr->second) << endl;
}

Answer 1

java.util.LinkedHashMap 听起来正是您想要的(包括 LRU 案例)。对于更精细的缓存情况，您可能需要 Guava 库中的 com.google.common.cache.Cache。

没有办法在 Java LinkedList 中存储指向特定节点的指针，事实上 LinkedList 是一个非常无用的实现——即使是 Josh Bloch它不再推荐它了。如果您的需求比 LinkedList 和 LinkedHashMap 可以处理的更专业，那么您可能应该构建自己的链表实现——它实际上是实现起来最简单的数据结构。