IT人生

  • 首页
  • 归档
  • kafka
  • Java
  • Spring
  • Golang
  • SQL
  • Spark
  • ElasticSearch
  • 关于

  • 搜索
Phoenix HBase Kudu ElasticSearch Spring 数据结构 操作系统 Kettle Azkaban Sqoop Hive Yarn Redis Mybatis Impala Cloudera 大数据 HDFS mycat shell Linux 架构 并发 mysql sql golang java 工具 spark kafka 人生

JDK源码分析-LinkedHashMap

发表于 2017-01-27 | 分类于 java | 0 | 阅读次数 202

系列文章:

  1. JDK源码分析-transient关键字
  2. JDK源码分析-transient关键字
  3. JDK源码分析-String
  4. JDK源码分析-AbstractStringBuilder
  5. JDK源码分析-StringBuffer和StringBuilder
  6. JDK源码分析-RandomAccess
  7. JDK源码分析-ArrayList
  8. JDK源码分析-LinkedList
  9. JDK源码分析-HashMap
  10. JDK源码分析-HashSet
  11. JDK源码分析-LinkedHashMap
  12. JDK源码分析-ConcurrentHashMap

类申明

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>

LinkedHashMap集成了HashMap,实现了Map接口 image.png

数据结构

LinkedHashMap的结构图如下: image.png 对于HashMap,LinkedHashMap多出了一个链表,而链表的顺序是按照数据插入的顺序排列的,所以当我们希望有顺序地去存储key-value时,就需要使用LinkedHashMap了。

LinkedHashMap的Entry源码如下:

    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);
        }
    }

Entry定义了前后指针,确保LinkedHashMap中数据能够双向遍历 但是LinkedHashMap并没有重写put方法是直接调用了HashMap的put方法,那如何保证按照插入数据的顺序遍历LinkedHashMap呢? 查看HashMap的put方法代码如下:

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            //此处是关键
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                //此处是关键
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                         //此处是关键
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) {
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        
        afterNodeInsertion(evict);
        return null;
    }

LinkedHashMap重写了newNode和newTreeNode方法,而构建顺序插入的链表结构就是通过这两个方法完成的:

   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;
    }

两个方法都调用了linkNodeLast,也就是插入新节点到链表的尾部:

    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }
  • 本文作者: Randy
  • 本文链接: http://www.itrensheng.com/archives/LinkedHashMap
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
# Phoenix # HBase # Kudu # ElasticSearch # Spring # 数据结构 # 操作系统 # Kettle # Azkaban # Sqoop # Hive # Yarn # Redis # Mybatis # Impala # Cloudera # 大数据 # HDFS # mycat # shell # Linux # 架构 # 并发 # mysql # sql # golang # java # 工具 # spark # kafka # 人生
JDK源码分析-HashSet
JDK源码分析-ConcurrentHashMap
  • 文章目录
  • 站点概览
Randy

Randy

技术可以暂时落后,但任何时候都要有上进的信念

80 日志
27 分类
31 标签
RSS
Github E-mail
Creative Commons
© 2021 备案号:沪ICP备19020689号-1
Randy的个人网站