Java集合框架源码剖析:LinkedHashSet 和 LinkedHashMap
CarpenterLee《深入理解Java集合框架》系列文章
- Java Collections Framework概览
- Java ArrayList源码剖析
- Java LinkedList源码剖析
- Java ArrayDeque源码剖析
- 史上最清晰的红黑树讲解(上)
- 史上最清晰的红黑树讲解(下)
- Java HashSet和HashMap源码剖析
- Java集合框架源码剖析:LinkedHashSet 和 LinkedHashMap
- 深入理解Java PriorityQueue
- 浅谈WeakHashMap
GITHUB地址:https://github.com/CarpenterLee/JCFInternals
Java LinkedHashMap和HashMap有什么区别和联系?为什么LinkedHashMap会有着更快的迭代速度?LinkedHashSet跟LinkedHashMap有着怎样的内在联系?本文从数据结构和算法层面,结合生动图解为读者一一解答。
总体介绍
如果你已看过前面关于HashSet和HashMap,以及TreeSet和TreeMap的讲解,一定能够想到本文将要讲解的LinkedHashSet和LinkedHashMap其实也是一回事。LinkedHashSet和LinkedHashMap在Java里也有着相同的实现,前者仅仅是对后者做了一层包装,也就是说LinkedHashSet里面有一个LinkedHashMap(适配器模式)。因此本文将重点分析LinkedHashMap。
LinkedHashMap实现了Map接口,即允许放入key
为null
的元素,也允许插入value
为null
的元素。从名字上可以看出该容器是linked list和HashMap的混合体,也就是说它同时满足HashMap和linked list的某些特性。可将LinkedHashMap看作采用linked list增强的HashMap。
事实上LinkedHashMap是HashMap的直接子类,二者唯一的区别是LinkedHashMap在HashMap的基础上,采用双向链表(doubly-linked list)的形式将所有entry
连接起来,这样是为保证元素的迭代顺序跟插入顺序相同。上图给出了LinkedHashMap的结构图,主体部分跟HashMap完全一样,多了header
指向双向链表的头部(是一个哑元),该双向链表的迭代顺序就是entry
的插入顺序。
除了可以保迭代历顺序,这种结构还有一个好处:迭代LinkedHashMap时不需要像HashMap那样遍历整个table
,而只需要直接遍历header
指向的双向链表即可,也就是说LinkedHashMap的迭代时间就只跟entry
的个数相关,而跟table
的大小无关。
有两个参数可以影响LinkedHashMap的性能:初始容量(inital capacity)和负载系数(load factor)。初始容量指定了初始table
的大小,负载系数用来指定自动扩容的临界值。当entry
的数量超过capacity*load_factor
时,容器将自动扩容并重新哈希。对于插入元素较多的场景,将初始容量设大可以减少重新哈希的次数。
将对象放入到LinkedHashMap或LinkedHashSet中时,有两个方法需要特别关心:hashCode()
和equals()
。hashCode()
方法决定了对象会被放到哪个bucket
里,当多个对象的哈希值冲突时,equals()
方法决定了这些对象是否是“同一个对象”。所以,如果要将自定义的对象放入到LinkedHashMap
或LinkedHashSet
中,需要@OverridehashCode()
和equals()
方法。
通过如下方式可以得到一个跟源Map 迭代顺序一样的LinkedHashMap:
void foo(Map m) { Map copy = new LinkedHashMap(m); ... }
出于性能原因,LinkedHashMap是非同步的(not synchronized),如果需要在多线程环境使用,需要程序员手动同步;或者通过如下方式将LinkedHashMap包装成(wrapped)同步的:
Map m = Collections.synchronizedMap(new LinkedHashMap(...));
方法剖析
get()
get(Object key)
方法根据指定的key
值返回对应的value
。该方法跟HashMap.get()
方法的流程几乎完全一样,读者可自行参考前文,这里不再赘述。
put()
put(K key, V value)
方法是将指定的key, value
对添加到map
里。该方法首先会对map
做一次查找,看是否包含该元组,如果已经包含则直接返回,查找过程类似于get()
方法;如果没有找到,则会通过addEntry(int hash, K key, V value, int bucketIndex)
方法插入新的entry
。
注意,这里的插入有两重含义:
- 从
table
的角度看,新的entry
需要插入到对应的bucket
里,当有哈希冲突时,采用头插法将新的entry
插入到冲突链表的头部。- 从
header
的角度看,新的entry
需要插入到双向链表的尾部。
addEntry()
代码如下:
// LinkedHashMap.addEntry() void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length);// 自动扩容,并重新哈希 hash = (null != key) ? hash(key) : 0; bucketIndex = hash & (table.length-1);// hash%table.length } // 1.在冲突链表头部插入新的entry HashMap.Entry<K,V> old = table[bucketIndex]; Entry<K,V> e = new Entry<>(hash, key, value, old); table[bucketIndex] = e; // 2.在双向链表的尾部插入新的entry e.addBefore(header); size++; }
上述代码中用到了addBefore()
方法将新entry e
插入到双向链表头引用header
的前面,这样e
就成为双向链表中的最后一个元素。addBefore()
的代码如下:
// LinkedHashMap.Entry.addBefor(),将this插入到existingEntry的前面 private void addBefore(Entry<K,V> existingEntry) { after = existingEntry; before = existingEntry.before; before.after = this; after.before = this; }
上述代码只是简单修改相关entry
的引用而已。
remove()
remove(Object key)
的作用是删除key
值对应的entry
,该方法的具体逻辑是在removeEntryForKey(Object key)
里实现的。removeEntryForKey()
方法会首先找到key
值对应的entry
,然后删除该entry
(修改链表的相应引用)。查找过程跟get()
方法类似。
注意,这里的删除也有两重含义:
- 从
table
的角度看,需要将该entry
从对应的bucket
里删除,如果对应的冲突链表不空,需要修改冲突链表的相应引用。- 从
header
的角度来看,需要将该entry
从双向链表中删除,同时修改链表中前面以及后面元素的相应引用。
removeEntryForKey()
对应的代码如下:
// LinkedHashMap.removeEntryForKey(),删除key值对应的entry final Entry<K,V> removeEntryForKey(Object key) { ...... int hash = (key == null) ? 0 : hash(key); int i = indexFor(hash, table.length);// hash&(table.length-1) Entry<K,V> prev = table[i];// 得到冲突链表 Entry<K,V> e = prev; while (e != null) {// 遍历冲突链表 Entry<K,V> next = e.next; Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {// 找到要删除的entry modCount++; size--; // 1. 将e从对应bucket的冲突链表中删除 if (prev == e) table[i] = next; else prev.next = next; // 2. 将e从双向链表中删除 e.before.after = e.after; e.after.before = e.before; return e; } prev = e; e = next; } return e; }
LinkedHashSet
前面已经说过LinkedHashSet是对LinkedHashMap的简单包装,对LinkedHashSet的函数调用都会转换成合适的LinkedHashMap方法,因此LinkedHashSet的实现非常简单,这里不再赘述。
public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable { ...... // LinkedHashSet里面有一个LinkedHashMap public LinkedHashSet(int initialCapacity, float loadFactor) { map = new LinkedHashMap<>(initialCapacity, loadFactor); } ...... public boolean add(E e) {//简单的方法转换 return map.put(e, PRESENT)==null; } ...... }
原文地址:http://www.cnblogs.com/CarpenterLee/p/5541111.html
相关推荐
-
SpringBoot源码篇:Spring5内置tomcat实现code-based的web.xml实现 Java框架
2019-9-17
-
Spring 源码(九)@Autowired注解实现理(Spring Bean的自动装配) Java框架
2020-6-1
-
Spring消息之WebSocket Java框架
2019-8-16
-
spring+atomikos+mytatis+jpa实现分布式事务管理实战篇 Java框架
2019-7-4
-
[Spring Cloud Stream]1 流式微服务核心概念 Java框架
2020-6-1
-
Spring Boot中使用@Scheduled创建定时任务 Java框架
2019-3-27
-
Spring Security(三)–核心配置解读 Java框架
2019-3-27
-
Apache Arrow 内存数据 Java框架
2019-3-25
-
spring cloud下用nacos做配置中心的初步探究,替换spring config server Java框架
2019-5-6
-
疯狂Spring Cloud连载(13)——Feign第三方注解与注解翻译器 Java框架
2020-6-8