LinkedHashMap在Java中的实现

Question

我无法理解HashFunction在LinkedHashMap中的用法。

在HashMap实现中，哈希函数的使用是查找内部数组的索引，这可以是合理的，遵循哈希函数契约（相同的键必须具有相同的hashcode，但不同的键可以具有相同的hashcode）。

我的问题是：

1）哈希函数在LinkedHashMap中的用途是什么？

2）放置和获取方法如何适用于LinkedHashMap？

3） 为什么要在内部维护双链接列表？使用HashMap作为内部实现（就像HashSet）并在插入序列中维护条目数组的单独数组/索引列表有什么错？

感谢有用的回应和参考。

Answer 1

匿名用户

LinkedHashMap是数据结构的一个很好的选择，您希望能够在O（1）运行时放置和获取条目，但您还需要LinkedList的行为。内部散列函数允许您使用常数时间放置和获取条目。

以下是您如何使用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。首先，如果您使用此方法，这意味着您将不得不维护两个数据结构，而不是一个。这很容易出错，并使维护代码更加困难。其次，如果您必须使您的数据结构线程安全，这对于两个数据结构来说将是复杂的。另一方面，如果您使用LinkedHashMap，您只需担心使这个单一的数据结构线程安全。

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

Answer 2

LinkedHashMap确实使用了一个HashMap（实际上它是从它扩展而来的），所以hashCode被用来在散列桶数组中识别正确的散列桶，就像HashMap一样put和get的工作方式与HashMap的工作方式相同（除了用于迭代条目的之前的和之后的引用在这两种实现中的更新方式不同）。

原因是插入代码不通过保持<代码>数组或<代码> ARARYLIST/COD>来保存，是在<代码>中间的AARYLIST/<代码>中的添加或删除是<代码> O（n）< /代码>操作，因为您必须将所有后续项沿着一个位置移动。你可以用<代码>链接目录< /COD>这样做，因为在<代码>中间的链接表中添加和删除是<代码> O（1）< /C>（所有你必须做的就是断开几个链接，再做一些新的链接）。然而，使用单独的LinkedList是没有意义的，因为你也可以制作地图。条目对象引用上一个和下一个条目对象，这正是LinkedHashMap的工作方式。

Answer 3

1） LinkedHashMap扩展了HashMap，因此HashMap函数与HashMap相同（如果您检查代码，则HashMap函数继承自HashMap），即该函数计算插入的对象的哈希值，并将其与具有相同密钥哈希的元素一起存储在数据结构中；在get方法中使用hasfunction来检索键指定为param的对象。

2）放置和获取方法的行为方式与HashMap相同，并跟踪元素的插入顺序，因此当您在键集上迭代时，您将按照插入到映射中的顺序获得键值（有关更多详细信息，请参阅此处）

3） LinkedHashMap使用双链接列表而不是数组，因为它更紧凑；对于插入和删除项目的列表，双链接列表是最有效的数据结构；如果主要是插入/追加元素，那么基于数组的实现可能会更好。由于映射语义是一个键值实现，从映射中删除元素可能是一个频繁的操作，所以双链表更适合。内部实现可以通过LinkedList实现，但我的观点是，使用低级数据结构更有效，并且可以将LinkedHashMap与其他类解耦。