Java 中的 LinkedHashMap 实现

Question

我无法理解 HashFunction 在 LinkedHashMap.

中的用法

在HashMap实现中，使用hashFunction是为了找到内部数组的索引，可以说得过去，跟在hashfunction 合同（相同的密钥必须具有相同的哈希码，但不同的密钥可以具有相同的哈希码）。

我的问题是：

1) LinkedHashMap中的hashfunction有什么用?

2) put 和 get 方法如何用于 LinkedHashMap？

3) 为什么它内部维护双向链表？使用 HashMap 作为内部实现（就像 HashSet 一样）并维护单独的 Array/List 索引有什么问题入口数组在插入顺序?

感谢有用的回复和参考。

Answer 1

答案。 2) 当我们调用 linkedhashmap 的 put(map,key) 时。在内部它调用 createEntry

void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
table[bucketIndex] = e;
e.addBefore(header);
size++;

答案 3) 为了有效地维护一个 linkedHashmap，你实际上需要一个双重 linked 列表。

按顺序考虑三个条目

A ---> B ---> C

假设你想删除 B。显然 A 现在应该指向 C。但是除非你知道 B 之前的条目，否则你不能有效地说出现在应该指向 C 的条目。要解决这个问题，你需要条目指向两个方向像这样

---> --->

A B C

<--- <---

这样，当您删除 B 时，您可以查看 B 之前和之后的条目（A 和 C）并进行更新，以便 A 和 C 相互指向对方。类似 post 在此 link 之前讨论过

why linkedhashmap maintains doubly linked list for iteration

Answer 2

A LinkedHashMap 确实使用了HashMap（实际上它是从它延伸出来的），所以hashCode用于识别哈希桶数组中的右哈希桶，与 HashMap 相同。 put 和 get 的工作方式与 HashMap 相同（除了用于遍历条目的 before 和 after 引用对于两个实现的更新不同）。

保持 Array 或 ArrayList 不保持插入顺序的原因是 ArrayList 中间的添加或删除是 O(n) 操作，因为您必须将所有后续项目移动到一个地方。您可以使用 LinkedList 来执行此操作，因为在 LinkedList 中间添加和删除是 O(1)（您所要做的就是断开一些链接并创建一些新链接）。但是，使用单独的 LinkedList 没有意义，因为您还可以使 Map.Entry 对象引用前一个和下一个 Entry 对象，这正是 LinkedHashMap 的工作方式。

Answer 3

LinkedHashMap 是一个很好的数据结构选择，您希望在 put 和 get 条目中包含 O(1) 运行时间，但您还需要 LinkedList 的行为。内部散列函数允许您 put 和 get 具有恒定时间的条目。

这里是你如何使用LinkedHashMap:

Map<String, Double> linkedHashMap = new LinkedHashMap<String, String>();
linkedHashMap.put("today", "Wednesday");
linkedHashMap.put("tomorrow", "Thursday");
String today = linkedHashMap.get("today"); // today is 'Wednesday'

有几种观点反对使用简单的 HashMap 并为插入顺序维护单独的 List。首先，如果你走这条路，这意味着你将不得不维护 2 个数据结构而不是一个。这很容易出错，并且使维护代码更加困难。其次，如果你必须让你的数据结构线程安全，这对于 2 个数据结构来说会很复杂。另一方面，如果您使用 LinkedHashMap，您只需要担心使这个单一数据结构成为线程安全的。

至于实现细节，当您将 put 转换为 LinkedHashMap 时，JVM 将获取您的密钥并使用加密映射函数最终将该密钥转换为您所在位置的内存地址值将被存储。使用给定键执行 get 还将使用此映射函数来查找内存中存储值的确切位置。 entrySet() 方法 returns 一个 Set 由 LinkedHashMap 中的所有键和值组成。根据定义，集合是无序的。 entrySet() 不保证是线程安全的。

Answer 4

1) LinkedHashMap extends HashMap 所以hashfunction和HashMap是一样的（如果你检查代码，hash函数是继承自HashMap），即函数计算插入对象的哈希值，它用于存储在一个数据结构以及具有相同键散列的元素；在 get 方法中使用 hasfunction 来检索具有指定为参数的键的对象。

2)Put 和 Get 方法的行为方式与 HashMap 相同，加上跟踪元素的插入顺序，因此当您遍历键集时，您将按照插入映射的顺序获取键值（请参阅here 了解更多详情）

3)LinkedHashMap使用双链表而不是数组，因为它更紧凑；双链表是最有效的列表数据结构，您可以在其中插入和删除项目；如果您主要使用 insert/append 个元素，那么基于数组的实现可能会更好。由于地图语义是一个键值实现，并且从地图中删除元素可能是一项频繁的操作，因此双链表更适合。可以使用 LinkedList 进行内部实现，但我的意见是使用低级数据结构更有效，并将 LinkedHashMap 与其他类.

分离

Java 中的 LinkedHashMap 实现

LinkedHashMap Implementation in Java

java

linkedhashmap