登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 业界 ›9.Java SDK源码分析系列笔记-LinkedHashMap

9.Java SDK源码分析系列笔记-LinkedHashMap

挺喽蹂 2025-6-30 17:02:27
目录

  • 1. 是什么
  • 2. 使用
  • 3. 实现

    • 3.1. uml
    • 3.2. 构造方法
    • 3.3. put

      • 3.3.1. 创建LinkedHashMap增强的节点--Entry【既是Node数组的节点又是双向链表的节点】

        • 3.3.1.1. 创建的时候就把节点插入到双向链表尾部

      • 3.3.2. put的节点（不是新插入的而是更新value），需要维护双向链表的顺序【输出的顺序】

        • 3.3.2.1. 把这个节点移动到双向链表尾部

      • 3.3.3. put的节点（不管是新插入的还是更新value）后判断是否需要删除头节点【最少访问的节点】

    • 3.4. get

      • 3.4.1. get节点后需要维护双向链表的顺序【输出的顺序】

        • 3.4.1.1. 把访问的当前节点放到链表的末尾


    • 3.5. containsKey
    • 3.6. containsValue
    • 3.7. remove

      • 3.7.1. remove节点后需要从双向链表删除该节点

    • 3.8. entrySet

      • 3.8.1. 要研究的代码
      • 3.8.2. LinkedHashMap.entrySet()返回的是LinkedEntrySet
      • 3.8.3. LinkedHashMap.entrySet().iterator()返回的是LinkedEntryIterator

        • 3.8.3.1. LinkedEntryIterator继承了LinkedHashIterator



  • 4. 总结
  • 5. 参考

1. 是什么


  • 使用双向链表+HashMap（数组+链表+红黑树）实现
  • 相比于HashMap保存了顺序

    • 迭代时输出的顺序是

      • 按照插入节点的顺序来输出
      • 也可以指定成按照访问的顺序输出(LRU)


2. 使用


  • 按照插入节点的顺序来输出
  1. public class LinkedHashMapTest
  2. {
  3.     public static void main(String[] args)
  4.     {
  5.         LinkedHashMap<String,Object> map = new LinkedHashMap<>();
  6.         map.put("name","zsk");
  7.         map.put("age",24);
  8.         map.put("height", 172L);
  10.         Iterator<Map.Entry<String, Object>> iterator = map.entrySet().iterator();
  11.         while (iterator.hasNext())
  12.         {
  13.             Map.Entry<String, Object> entry = iterator.next();
  14.             /*插入的顺序是怎样那么输出就是怎样
  15.             *   name=zsk
  16.                 age=24
  17.                 height=172
  18.             * */
  19.             System.out.println(entry);
  20.         }
  21.         //上面的输出跟这个一样
  23.         for (Map.Entry<String, Object> entry : map.entrySet())
  24.         {
  25.             /*插入的顺序是怎样那么输出就是怎样
  26.             *   name=zsk
  27.                 age=24
  28.                 height=172
  29.             * */
  30.             System.out.println(entry);
  31.         }
  33.         System.out.println(map.containsKey("name"));//true
  34.         System.out.println(map.get("name"));//zsk
  35.         map.remove("name");
  36.         System.out.println(map.containsKey("name"));//false
  37.     }
  38. }
复制代码

  • 按照访问的顺序输出
  1. public class LinkedHashMapTest
  2. {
  3.     public static void main(String[] args)
  4.     {
  5.         LinkedHashMap<String, Object> map = new LinkedHashMap<>(2, 0.75F, true);
  6.         map.put("1", "a");
  7.         map.put("2", "b");
  8.         map.put("3", "c");
  11.         Iterator<Map.Entry<String, Object>> iterator = map.entrySet().iterator();
  12.         while (iterator.hasNext())
  13.         {
  14.             Map.Entry<String, Object> entry = iterator.next();
  15.             //            1=a
  16.             //            2=b
  17.             //            3=c
  18.             System.out.println(entry);
  19.         }
  20.         //上面的输出跟这个一样
  22.         for (Map.Entry<String, Object> entry : map.entrySet())
  23.         {
  24.             //            1=a
  25.             //            2=b
  26.             //            3=c
  27.             System.out.println(entry);
  28.         }
  30.         System.out.println(map.get("1"));//访问了1，那么1所在的节点被移到链表末尾
  31.         for (Map.Entry<String, Object> entry : map.entrySet())
  32.         {
  33.             //最近被访问的节点被放到链表末尾
  34.             //            2=b
  35.             //            3=c
  36.             //            1=a
  37.             System.out.println(entry);
  38.         }
  39.     }
  40. }
复制代码
3. 实现

3.1. uml

1.png

继承了HashMap，可克隆，可序列化
3.2. 构造方法
  1. public class LinkedHashMap<K,V>
  2.     extends HashMap<K,V>//继承HashMap
  3.     implements Map<K,V>
  4. {
  5.         //链表的节点。双向链表
  6.          static class Entry<K,V> extends HashMap.Node<K,V> {
  7.                     Entry<K,V> before, after;
  8.                     Entry(int hash, K key, V value, Node<K,V> next) {
  9.                         super(hash, key, value, next);
  10.                     }
  11.                 }
  14.     //双向链表的头尾节点
  15.     transient LinkedHashMap.Entry<K,V> head;
  16.     transient LinkedHashMap.Entry<K,V> tail;
  18.     //true的话保持访问的顺序，false的话保持插入的顺序
  19.     final boolean accessOrder;
  20.         public LinkedHashMap() {
  21.                 //调用HashMap的构造方法
  22.             super();
  23.             accessOrder = false;
  24.         }
  25. }
复制代码
LinkedHashMap继承了HashMap，所以map的get、set、remove等方法都是调用的HashMap的方法，而且LinkedHashMap还增强了HashMap的Node，定义了自己的Entry，加入了双向链表
3.3. put

其实就是调用的HashMap的put方法把插入新的节点或者替换value，只不过多了一些其他操作

  • HashMap.put
  1. public V put(K key, V value) {
  2.     return putVal(hash(key), key, value, false, true);
  3. }
  5. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  6.                boolean evict) {
  7.     Node<K,V>[] tab; Node<K,V> p; int n, i;
  8.     if ((tab = table) == null || (n = tab.length) == 0)
  9.         n = (tab = resize()).length;
  10.     if ((p = tab[i = (n - 1) & hash]) == null)
  11.         //LinkedHashMap重写了newNode方法
  12.         tab[i] = newNode(hash, key, value, null);
  13.     else {
  14.         Node<K,V> e; K k;
  15.         if (p.hash == hash &&
  16.             ((k = p.key) == key || (key != null && key.equals(k))))
  17.             e = p;
  18.         else if (p instanceof TreeNode)
  19.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  20.         else {
  21.             for (int binCount = 0; ; ++binCount) {
  22.                 if ((e = p.next) == null) {
  23.                     p.next = newNode(hash, key, value, null);
  24.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  25.                         treeifyBin(tab, hash);
  26.                     break;
  27.                 }
  28.                 if (e.hash == hash &&
  29.                     ((k = e.key) == key || (key != null && key.equals(k))))
  30.                     break;
  31.                 p = e;
  32.             }
  33.         }
  34.         //节点已经存在，只是更新value的情况
  35.         if (e != null) { // existing mapping for key
  36.             V oldValue = e.value;
  37.             if (!onlyIfAbsent || oldValue == null)
  38.                 e.value = value;
  39.             //需要维护双向链表中的顺序
  40.             afterNodeAccess(e);
  41.             return oldValue;
  42.         }
  43.     }
  44.     ++modCount;
  45.     if (++size > threshold)
  46.         resize();
  47.     //removeEldest方法返回true的时候，需要删除头节点【最少访问的节点】
  48.     afterNodeInsertion(evict);
  49.     return null;
  50. }
复制代码
需要注意的以下几点：

  • 12行：LinkedHashMap重写了newNode方法
  • 35-42行：更新value之后要维护双向链表中的顺序
  • 48行：不管是插入了新的节点还是更新了value，都需要根据情况（removeEldest方法是否返回true）删除链表头节点
3.3.1. 创建LinkedHashMap增强的节点--Entry【既是Node数组的节点又是双向链表的节点】


  • LinkedHashMap.newNode
  1. Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
  2.     //创建的是LinkedHashMap增强的Entry
  3.     LinkedHashMap.Entry<K,V> p =
  4.         new LinkedHashMap.Entry<K,V>(hash, key, value, e);
  5.     //插入到链表尾部
  6.     linkNodeLast(p);
  7.     return p;
  8. }
复制代码
3.3.1.1. 创建的时候就把节点插入到双向链表尾部


  • linkNodeLast
  1. private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
  2.     LinkedHashMap.Entry<K,V> last = tail;
  3.     tail = p;
  4.     //把当前节点插入到链表的末尾的操作
  5.     if (last == null)
  6.         head = p;
  7.     else {
  8.         p.before = last;
  9.         last.after = p;
  10.     }
  11. }
复制代码
3.3.2. put的节点（不是新插入的而是更新value），需要维护双向链表的顺序【输出的顺序】
  1. //节点已经存在，只是更新value的情况
  2.     if (e != null) { // existing mapping for key
  3.         V oldValue = e.value;
  4.         if (!onlyIfAbsent || oldValue == null)
  5.             e.value = value;
  6.         //需要维护双向链表中的顺序
  7.         afterNodeAccess(e);
  8.         return oldValue;
  9.     }
复制代码
3.3.2.1. 把这个节点移动到双向链表尾部


  • afterNodeAccess
  1. void afterNodeAccess(Node<K,V> e) { // move node to last
  2.     LinkedHashMap.Entry<K,V> last;
  3.     //指定了访问顺序 并且 当前节点不是尾巴节点【即不是新插入的节点】
  4.     if (accessOrder && (last = tail) != e) {
  5.         LinkedHashMap.Entry<K,V> p =
  6.             (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
  7.         //以下的操作把当前节点移动到双向链表的末尾
  8.         p.after = null;
  9.         if (b == null)
  10.             head = a;
  11.         else
  12.             b.after = a;
  13.         if (a != null)
  14.             a.before = b;
  15.         else
  16.             last = b;
  17.         if (last == null)
  18.             head = p;
  19.         else {
  20.             p.before = last;
  21.             last.after = p;
  22.         }
  23.         tail = p;
  24.         ++modCount;
  25.     }
  26. }
复制代码
3.3.3. put的节点（不管是新插入的还是更新value）后判断是否需要删除头节点【最少访问的节点】


  • afterNodeInsertion
  1. void afterNodeInsertion(boolean evict) { // possibly remove eldest
  2.     LinkedHashMap.Entry<K,V> first;
  3.     //removeEldestEntry返回true的时候【场景：比如定义LRU算法超过一定容量删除最少访问的节点】
  4.     if (evict && (first = head) != null && removeEldestEntry(first)) {
  5.        //删除头节点
  6.         K key = first.key;
  7.         removeNode(hash(key), key, null, false, true);
  8.     }
  9. }
复制代码
3.4. get

其实就是调用HashMap的getNode方法获取节点，然后在调用LinkedHashMap的afterNodeAccess把访问的当前节点放到链表的末尾

  • LinkedHashMap.get
  1. public V get(Object key) {
  2.     Node<K,V> e;
  3.         //调用HashMap的getNode获取节点
  4.     if ((e = getNode(hash(key), key)) == null)
  5.         return null;
  6.     //如果设置按照访问顺序的话，那么
  7.     if (accessOrder)
  8.         afterNodeAccess(e);
  9.    
  10.     return e.value;
  11. }
复制代码

  • 7-8行：如果设置按照访问顺序的话，那么调用LinkedHashMap的afterNodeAccess把当前访问的节点移动到双向链表的末尾（最新的节点）
3.4.1. get节点后需要维护双向链表的顺序【输出的顺序】
  1. //如果设置按照访问顺序的话，那么
  2. if (accessOrder)
  3.     afterNodeAccess(e);
复制代码
3.4.1.1. 把访问的当前节点放到链表的末尾


  • LinkedHashMap afterNodeAccess
    同put操作一样，就是把访问的当前节点放到链表的末尾
  1. void afterNodeAccess(Node<K,V> e) { // move node to last
  2.     LinkedHashMap.Entry<K,V> last;
  3.     if (accessOrder && (last = tail) != e) {
  4.             //p代表当前节点，a代表后一个节点，b代表前一个节点
  5.         LinkedHashMap.Entry<K,V> p =
  6.             (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
  7.         //前面节点的next指向后一个节点
  8.         p.after = null;
  9.         if (b == null)
  10.             head = a;
  11.         else
  12.             b.after = a;
  14.         //后一个节点的prev指向前一个节点
  15.         if (a != null)
  16.             a.before = b;
  17.         else
  18.             last = b;
  20.         //当前节点的prev指向尾节点，尾节点的next指向当前节点
  21.         if (last == null)
  22.             head = p;
  23.         else {
  24.             p.before = last;
  25.             last.after = p;
  26.         }
  27.         //更新尾节点为当前节点
  28.         tail = p;
  29.         ++modCount;
  30.     }
  31. }
复制代码
3.5. containsKey

就是调用HashMap的containsKey方法
  1. public boolean containsKey(Object key) {
  2.     //依然是HashMap.getNode,没什么特殊的地方
  3.     return getNode(hash(key), key) != null;
  4. }
复制代码
3.6. containsValue

重写了HashMap的方法，效率更高
  1. public boolean containsValue(Object value) {
  2.         //遍历双向链表，效率O（N）,不同于HashMap的O(N2)
  3.     for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
  4.         V v = e.value;
  5.         if (v == value || (value != null && value.equals(v)))
  6.             return true;
  7.     }
  8.     return false;
  9. }
复制代码
3.7. remove

其实就是调用HashMap的remove方法删除节点，再调用LinkedHashMap的afterNodeRemoval把当前节点从双向链表中删除

  • HashMap.remove
  1. public V remove(Object key) {
  2.     Node<K,V> e;
  3.     return (e = removeNode(hash(key), key, null, false, true)) == null ?
  4.         null : e.value;
  5. }
  7. final Node<K,V> removeNode(int hash, Object key, Object value,
  8.                            boolean matchValue, boolean movable) {
  9.     Node<K,V>[] tab; Node<K,V> p; int n, index;
  10.     if ((tab = table) != null && (n = tab.length) > 0 &&
  11.         (p = tab[index = (n - 1) & hash]) != null) {
  12.         Node<K,V> node = null, e; K k; V v;
  13.         if (p.hash == hash &&
  14.             ((k = p.key) == key || (key != null && key.equals(k))))
  15.             node = p;
  16.         else if ((e = p.next) != null) {
  17.             if (p instanceof TreeNode)
  18.                 node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
  19.             else {
  20.                 do {
  21.                     if (e.hash == hash &&
  22.                         ((k = e.key) == key ||
  23.                          (key != null && key.equals(k)))) {
  24.                         node = e;
  25.                         break;
  26.                     }
  27.                     p = e;
  28.                 } while ((e = e.next) != null);
  29.             }
  30.         }
  31.         if (node != null && (!matchValue || (v = node.value) == value ||
  32.                              (value != null && value.equals(v)))) {
  33.             if (node instanceof TreeNode)
  34.                 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
  35.             else if (node == p)
  36.                 tab[index] = node.next;
  37.             else
  38.                 p.next = node.next;
  39.             ++modCount;
  40.             --size;
  41.             //删除了节点后需要维护双向链表
  42.             afterNodeRemoval(node);
  43.             return node;
  44.         }
  45.     }
  46.     return null;
  47. }
复制代码
3.7.1. remove节点后需要从双向链表删除该节点


  • LinkedHashMap afterNodeRemoval
  1. void afterNodeRemoval(Node<K,V> e) { // unlink
  2.     //以下的操作把当前删除的节点从双向链表中删除
  3.         //p是当前被删除的节点，b是p的前一个节点，a是p的后一个节点
  4.     LinkedHashMap.Entry<K,V> p =
  5.         (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
  6.     p.before = p.after = null;
  7.     //修改前一个节点的next指针
  8.     if (b == null)
  9.         head = a;
  10.     else
  11.         b.after = a;
  12.     //修改后一个节点的prev指针
  13.     if (a == null)
  14.         tail = b;
  15.     else
  16.         a.before = b;
  17. }
复制代码
3.8. entrySet

3.8.1. 要研究的代码
  1. Iterator<Map.Entry<String, Object>> iterator = map.entrySet().iterator();
复制代码

  • LinkedHashMap entrySet
  1. public Set<Map.Entry<K,V>> entrySet() {
  2.     Set<Map.Entry<K,V>> es;
  3.     //这个entrySet属性什么时候set的？
  4.     //返回LinkedEntrySet
  5.     return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
  6. }
复制代码
调用map.entrySet()返回的是LinkedEntrySet，如下
3.8.2. LinkedHashMap.entrySet()返回的是LinkedEntrySet


  • LinkedEntrySet
[code]final class LinkedEntrySet extends AbstractSet {    public final int size()                 { return size; }    public final void clear()               { LinkedHashMap.this.clear(); }    public final Iterator iterator() {        //遍历器是LinkedEntryIterator        return new LinkedEntryIterator();    }    public final boolean contains(Object o) {        if (!(o instanceof Map.Entry))            return false;        Map.Entry e = (Map.Entry) o;        Object key = e.getKey();        Node candidate = getNode(hash(key), key);        return candidate != null && candidate.equals(e);    }    public final boolean remove(Object o) {        if (o instanceof Map.Entry) {            Map.Entry e = (Map.Entry) o;            Object key = e.getKey();            Object value = e.getValue();            return removeNode(hash(key), key, value, true, true) != null;        }        return false;    }    public final Spliterator spliterator() {        return Spliterators.spliterator(this, Spliterator.SIZED |                                        Spliterator.ORDERED |                                        Spliterator.DISTINCT);    }    public final void forEach(Consumer

使用道具 举报
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
挺喽蹂
2025-6-30 17:02:27

0

粉丝关注

13

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫