LinkedHashMap源码阅读 爱被打了一巴掌 2022-12-20 13:58 68阅读 0赞 ### 文章目录 ### * * 回顾一下使用 * LinkedHashMap结构 * 继承结构 * 存放的key-value的Node节点 * 核心属性 * 构造方法 * 核心方法 public V get(Object key) * 核心方法 public V put(K key, V value) * 总结 [建议看之前先看HashMap][HashMap] ## 回顾一下使用 ## LinkedHashMap是有序的HashMap。节点的存放或者访问维持着其中的顺序。**支持两种顺序** 1. 插入顺序 按照插入的前后顺序,先插入的在双向链表前,后插入的在双向链表后。修改已存在的节点不会改变顺序 2. 访问顺序 在插入顺序的基础上,增加了访问顺序。不存在访问的情况,依然按照插入顺序排序,节点被访问后,最新访问的节点会被放在双向链表的尾部。如果这个时候再插入个元素的话,插入的元素放在双向链表尾部,即在插入顺序的基础上。 Map<String, Integer> map = new LinkedHashMap<>(); map.put("c",100); map.put("d",200); map.put("a",300); for(Entry<String,Integer> entry:map.entrySet()){ System.out.println(entry.getKey()+" "+entry.getValue()); } 控制台按插入顺序输出 > c 100 > d 200 > a 300 Map<String, Integer> accessMap = new LinkedHashMap<>(16,0.75f,true); accessMap.put("c",100); accessMap.put("d",200); accessMap.put("a",300); for(Map.Entry<String,Integer> entry:accessMap.entrySet()){ System.out.println(entry.getKey()+" "+entry.getValue()); } accessMap.get("c"); for(Map.Entry<String,Integer> entry:accessMap.entrySet()){ System.out.println(entry.getKey()+" "+entry.getValue()); } 控制台输出 > c 100 > d 200 > a 300 访问了c之后 > d 200 > a 300 > c 100 ## LinkedHashMap结构 ## 数组+链表+红黑树+双向链表。可以可看到他的结构和HashMap几乎一样,只是多了更多的指针。 (下图几个小问题修正一下,两个单链表和树的根节点是在数组中存放的。两个节点的链表两个节点中间少了两个箭头) ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center] 对比一下HashMap的结构,几乎一样,看源码就明白为什么了。 ![在这里插入图片描述][20201024225357324.png_pic_center] ## 继承结构 ## LinkedHashMap继承了HashMap,是对HashMap做了增强。具体哪里做了增加后续分析 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 1] ## 存放的key-value的Node节点 ## 相对HashMap在节点上Entry继承Node并且增加了before, after指针,正是有这两个指针维护了节点间的顺序。结构图中灰色和红色的指针。 static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } } ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 2] ## 核心属性 ## * LinkedHashMap.Entry<K,V> head; 双向链表的头指针 * LinkedHashMap.Entry<K,V> tail; 双向链表的尾指针 * boolean accessOrder; 是否按照访问顺序排序,默认为false ## 构造方法 ## 基本上过一眼就行了,前面两个accessOrde都赋值为false。只有第三个是可以按照访问顺序存放的,accessOrder参数传true即可。 public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false; } public LinkedHashMap() { super(); accessOrder = false; } public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; } ## 核心方法 public V get(Object key) ## 似乎也没什么好说的,调HashMap的getNode方法获取元素跟HashMap一样。但是前文说了LinkedHashMap可以按照访问顺序存放的,节点被访问后,最新访问的节点会被放在双向链表的尾部。往下看当accessOrder为true时(构造LinkedHashMap时构造函数参数传true)便会调用afterNodeAccess方法。 public V get(Object key) { Node<K,V> e; if ((e = getNode(hash(key), key)) == null) return null; if (accessOrder) afterNodeAccess(e); return e.value; } 将节点移向双向链表的末尾 * 节点是头结点 头指针指向节点的后继,节点的前驱指向尾节点,尾节点的后继指向节点。节点的后继为Null。尾指针指向节点 * 节点是尾节点 不用做处理。 * 节点是中间节点 首先移除节点:节点前驱的后继指向节点的后继,节点的后继的前驱指向节点的前驱。 在尾节点后增加节点:节点的前驱指向尾节点,尾节点的后继指向节点。节点的后继为Null。尾指针指向节点。 //accessOrder属性为true时,新访问的节点需要放在双向链表的尾部 void afterNodeAccess(Node<K,V> e) { //临时记录尾节点 LinkedHashMap.Entry<K,V> last = tail; //如果已经是尾节点,则不需要移动 if (accessOrder && last != e) { //hashMap传递的引用是个Node,对象是Entry LinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e; //前驱 LinkedHashMap.Entry<K,V> b = p.before; //后继 LinkedHashMap.Entry<K,V> a = p.after; //节点的后继先设置为null,节点必定为尾节点,后继为Null p.after = null; //节点为头结点 if (b == null) //头指针移动到节点的后继 head = a; else //节点不为头节点,要么中间要么尾节点 //前驱的后继指向节点后继 b.after = a; //后继不为null,不为尾节点(其实我不是很懂为什么要有这个判断) //最外层if已经判断了节点不为尾节点了,a恒不为Null if (a != null) //后继的前驱指向节点的前驱 a.before = b; else last = b; if (last == null) head = p; else { //节点的前驱指向尾节点 p.before = last; //尾节点的后继指向节点,让节点成为尾节点 last.after = p; } //让尾指针指向尾节点 tail = p; ++modCount; } } ## 核心方法 public V put(K key, V value) ## put方法,LinkedHashMap没有重写put方法,而是重写了newNode方法来维护节点的先后顺序。 先看看HashMap的put方法,其中在构造节点时,调用了newNode方法构造节点。看看LinkedHashMap重写的newNode ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 3] Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e); //把节点链接在双向链表尾部 linkNodeLast(p); return p; } TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) { TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next); linkNodeLast(p); return p; } private void linkNodeLast(LinkedHashMap.Entry<K,V> p) { LinkedHashMap.Entry<K,V> last = tail; //尾指针移动向新节点 tail = p; //尾节点为null,那么这是第一个节点,头节点指针也指向该节点 if (last == null) head = p; else { //新节点的前驱指向尾节点 p.before = last; //尾节点后继指向新节点 last.after = p; } } remove时,linkedHashMap重写了void afterNodeRemoval(Node<K,V> p) \{ \}方法 把节点从双向链表中删除。 在HashMap中当节点删除后,调用了afterNodeRemoval方法,HashMap中是个空方法,LinkedHashMap重写了该方法。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 4] 完成节点的移除工作。 * 头节点 * 尾节点 * 中间节点 void afterNodeRemoval(Node<K,V> e) { // unlink LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e; LinkedHashMap.Entry<K,V> b = p.before; LinkedHashMap.Entry<K,V> a = p.after; //前驱后继置为null p.before = p.after = null; //节点E为头节点 if (b == null) //头指针指向后继 head = a; else //不为头节点 //前驱的后继指向后继 b.after = a; //E为尾节点 if (a == null) //尾指针前移 tail = b; else //后继前驱等于前驱 a.before = b; } ## 总结 ## linkedHashMap继承HashMap,在HashMap的基础上做了增加,增加了双向链表的结构用来维护各个节点之间的顺序,其中可以按照插入顺序或者访问顺序。 1. 插入顺序 按照插入的前后顺序,先插入的在双向链表前,后插入的在双向链表后。修改已存在的节点不会改变顺序 2. 访问顺序 不存在访问的情况,依然按照插入顺序排序,节点被访问后,最新访问的节点会被放在双向链表的尾部。 在插入元素时,调用newNode或者newTreeNode构造节点时会调整双向链表之间节点的顺序。如果只是改变某个节点的value则不会。因为并没有构造节点的过程。 如果开启访问顺序,在调用get方法时会调整节点间的顺序。 [HashMap]: https://blog.csdn.net/wsdfym/article/details/109232470 [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/e41a5b402fec4b4ba429a225f1372830.png [20201024225357324.png_pic_center]: /images/20221120/e1756ba3918f453d82cd895655de3824.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/bbe608af71474784b7888064762710f4.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/8ae48a895c3748029c3d11a6b68abc07.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/6bb00c7acd2e4036a529640d61614e31.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221120/4df7c25b44e7456197ee971f835c775d.png
还没有评论,来说两句吧...