LinkedHashMap的内部实现与HashMap实现有何不同?
我读到HashMap具有以下实现:
main array ↓ [Entry] → Entry → Entry ← linked-list implementation [Entry] [Entry] → Entry [Entry] [null ]
因此,它有一个Entry对象数组。
问题:
-
我想知道如果相同的hashCode但不同的对象,这个数组的索引如何存储多个Entry对象。
-
这与
LinkedHashMap
实现有何不同? 它是map的双链表实现,但它是否像上面那样维护一个数组,它如何存储指向下一个和前一个元素的指针?
因此,它有一个
Entry
对象数组。
不完全是。 它有一个Entry
对象链数组。 HashMap.Entry
对象具有next
字段,允许将Entry
对象链接为链接列表。
我想知道如果相同的hashCode但不同的对象,这个数组的索引如何存储多个
Entry
对象。
因为(如问题中的图片所示) Entry
对象是链接的。
这与
LinkedHashMap
实现有何不同? 它是map的双链表实现,但它是否像上面那样维护一个数组,它如何存储指向下一个和前一个元素的指针?
在LinkedHashMap
实现中, LinkedHashMap.Entry
类通过添加字段before
和之after
扩展HashMap.Entry
类。 这些字段用于将LinkedHashMap.Entry
对象组装到一个记录插入顺序的独立双向链接列表中。 因此,在LinkedHashMap
类中,条目对象位于两个不同的链中:
-
通过主哈希数组访问的单链接哈希链,和
-
在条目插入顺序中保留的所有条目的单独的双向链接列表。
HashMap不维护插入顺序,因此不维护任何双向链表。
LinkedHashMap最突出的特点是它维护键值对的插入顺序。 LinkedHashMap使用双重链接列表来执行此操作。
LinkedHashMap的输入看起来像这样 –
static class Entry { K key; V value; Entry next; Entry before, after; //For maintaining insertion order public Entry(K key, V value, Entry next){ this.key = key; this.value = value; this.next = next; } }
通过使用之前和之后 – 我们在LinkedHashMap中跟踪新添加的条目,这有助于我们维护插入顺序。
在引用之前的条目之前和之后引用LinkedHashMap中的下一个条目。
有关图表和分步说明,请参阅http://www.javamadesoeasy.com/2015/02/linkedhashmap-custom-implementation.html
谢谢..!!
看看你自己。 为了将来参考,你可以谷歌:
java LinkedHashMap源码
HashMap
使用LinkedList
来处理collission,但HashMap
和LinkedHashMap
之间的区别在于LinkedHashMap
具有可预测的迭代顺序,这是通过一个额外的双向链表实现的,该列表通常保持键的插入顺序。 例外情况是重新插入密钥时,在这种情况下它会返回到列表中的原始位置。
作为参考,迭代LinkedHashMap
比迭代HashMap
更有效,但LinkedHashMap
的内存效率更低。
如果从上面的解释中不清楚,散列过程是相同的,那么你可以获得正常散列的好处,但是你也可以获得如上所述的迭代优势,因为你使用的是双向链接列表保持Entry
对象的顺序,这与在冲突的哈希过程中使用的链表无关,如果不明确的话。
编辑:(回应OP的评论):
HashMap
由数组支持,其中一些插槽包含Entry
对象链以处理冲突。 要遍历所有(键,值)对,您需要遍历数组中的所有插槽,然后浏览LinkedLists
; 因此,您的总时间将与容量成比例。
使用LinkedHashMap
,您需要做的就是遍历双向链表,因此总时间与大小成正比。
由于其他答案都没有实际解释如何实现这样的事情我会给它一个机会。
一种方法是在用户看不到的值(键 – >值对)中有一些额外的信息,这些信息引用了插入到哈希映射中的上一个和下一个元素。 好处是您仍然可以在常量时间中删除元素从哈希映射中删除是恒定时间,并且在这种情况下从链接列表中删除是因为您有对该条目的引用。 您仍然可以在常量时间插入,因为哈希映射插入是常量,链表不是正常的,但在这种情况下,您可以持续时间访问链表中的某个点,这样您就可以在恒定时间内插入,最后检索是恒定时间因为你只需处理结构的哈希映射部分。
请记住,像这样的数据结构并非没有成本。 由于所有额外的引用,哈希映射的大小将显着增加。 每个主要方法都会稍微慢一些(如果重复调用则可能很重要)。 并且数据结构的间接性(不确定这是一个真正的术语:P)是否会增加,尽管这可能不是那么大,因为引用可以保证指向哈希映射中的内容。
由于这种结构的唯一优点是在使用它时保持顺序要小心。 另外,在阅读答案时请记住,我不知道这是它的实现方式,但如果给出任务,我就是这样做的。
在oracle文档上有一个引用证实了我的一些猜测。
此实现与HashMap的不同之处在于它维护了一个贯穿其所有条目的双向链表。
来自同一网站的另一个相关报价。
此类提供所有可选的Map操作,并允许null元素。 与HashMap一样,它为基本操作(添加,包含和删除)提供了恒定时间性能,假设哈希函数在桶之间正确地分散元素。 由于维护链表的额外费用,性能可能略低于HashMap的性能,但有一个例外:对LinkedHashMap的集合视图进行迭代需要与映射大小成比例的时间,无论其容量如何。 对HashMap的迭代可能更昂贵,需要与其容量成比例的时间。
hashCode
将通过散列函数映射到任何存储桶。 如果hashCode
存在冲突而不是HashMap
通过链接来解决此冲突,即它会将值添加到链表中。 下面是执行此操作的代码:
for (Entry e = table[i]; e != null; e = e.next) { 392 Object k; 393 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 394 `enter code here` V oldValue = e.value; 395 e.value = value; 396 e.recordAccess(this); 397 return oldValue; 398 } 399 }
您可以清楚地看到它遍历链接列表,如果找到密钥,则将其替换旧值,并将新的else附加到链接列表。
但是LinkedHashMap
和HashMap
之间的区别是LinkedHashMap
维护了插入顺序。 来自docs :
此链接列表定义迭代排序,通常是键插入映射的顺序(插入顺序)。 请注意,如果将键重新插入地图,则不会影响插入顺序。 (如果m.containsKey(k)在调用之前立即返回true,则调用m.put(k,v)时,将密钥k重新插入映射m中。