• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

LinkedHashMap 底层分析

技术杂谈 勤劳的小蚂蚁 2个月前 (02-03) 57次浏览 已收录 0个评论 扫描二维码

众所周知 HashMap 是一个无序的 Map,因为每次根据 keyhashcode 映射到 Entry 数组上,所以遍历出来的顺序并不是写入的顺序。
因此 JDK 推出一个基于 HashMap 但具有顺序的 LinkedHashMap 来解决有排序需求的场景。
它的底层是继承于 HashMap 实现的,由一个双向链表所构成。
LinkedHashMap 的排序方式有两种:
  • 根据写入顺序排序。
  • 根据访问顺序排序。
其中根据访问顺序排序时,每次 get 都会将访问的值移动到链表末尾,这样重复操作就能的到一个按照访问顺序排序的链表。

数据结构

  1.    @Test
  2.    publicvoid test(){
  3.        Map<String,Integer> map =newLinkedHashMap<String,Integer>();
  4.        map.put("1",1);
  5.        map.put("2",2);
  6.        map.put("3",3);
  7.        map.put("4",4);
  8.        map.put("5",5);
  9.        System.out.println(map.toString());
  10.    }
调试可以看到 map 的组成:
打开源码可以看到:
  1.    /**
  2.     * The head of the doubly linked list.
  3.     */
  4.    privatetransientEntry<K,V> header;
  5.    /**
  6.     * The iteration ordering method for this linked hash map: <tt>true</tt>
  7.     * for access-order, <tt>false</tt> for insertion-order.
  8.     *
  9.     * @serial
  10.     */
  11.    privatefinalboolean accessOrder;
  12.    privatestaticclassEntry<K,V>extendsHashMap.Entry<K,V>{
  13.        // These fields comprise the doubly linked list used for iteration.
  14.        Entry<K,V> before, after;
  15.        Entry(int hash, K key, V value,HashMap.Entry<K,V> next){
  16.            super(hash, key, value, next);
  17.        }
  18.    }  
其中 Entry 继承于 HashMapEntry,并新增了上下节点的指针,也就形成了双向链表。
还有一个 header 的成员变量,是这个双向链表的头结点。
上边的 demo 总结成一张图如下:
第一个类似于 HashMap 的结构,利用 Entry 中的 next 指针进行关联。
下边则是 LinkedHashMap 如何达到有序的关键。
就是利用了头节点和其余的各个节点之间通过 Entry 中的 afterbefore 指针进行关联。
其中还有一个 accessOrder 成员变量,默认是 false,默认按照插入顺序排序,为 true 时按照访问顺序排序,也可以调用:
  1.    publicLinkedHashMap(int initialCapacity,
  2.                         float loadFactor,
  3.                         boolean accessOrder){
  4.        super(initialCapacity, loadFactor);
  5.        this.accessOrder = accessOrder;
  6.    }
这个构造方法可以显示的传入 accessOrder

构造方法

LinkedHashMap 的构造方法:
  1.    publicLinkedHashMap(){
  2.        super();
  3.        accessOrder =false;
  4.    }
其实就是调用的 HashMap 的构造方法:
HashMap 实现:
  1.    publicHashMap(int initialCapacity,float loadFactor){
  2.        if(initialCapacity <0)
  3.            thrownewIllegalArgumentException("Illegal initial capacity: "+
  4.                                               initialCapacity);
  5.        if(initialCapacity > MAXIMUM_CAPACITY)
  6.            initialCapacity = MAXIMUM_CAPACITY;
  7.        if(loadFactor <=0||Float.isNaN(loadFactor))
  8.            thrownewIllegalArgumentException("Illegal load factor: "+
  9.                                               loadFactor);
  10.        this.loadFactor = loadFactor;
  11.        threshold = initialCapacity;
  12.        //HashMap 只是定义了改方法,具体实现交给了 LinkedHashMap
  13.        init();
  14.    }
可以看到里面有一个空的 init(),具体是由 LinkedHashMap 来实现的:
  1.    @Override
  2.    void init(){
  3.        header =newEntry<>(-1,null,null,null);
  4.        header.before = header.after = header;
  5.    }
其实也就是对 header 进行了初始化。

put() 方法

LinkedHashMapput() 方法之前先看看 HashMapput 方法:
  1.    public V put(K key, V value){
  2.        if(table == EMPTY_TABLE){
  3.            inflateTable(threshold);
  4.        }
  5.        if(key ==null)
  6.            return putForNullKey(value);
  7.        int hash = hash(key);
  8.        int i = indexFor(hash, table.length);
  9.        for(Entry<K,V> e = table[i]; e !=null; e = e.next){
  10.            Object k;
  11.            if(e.hash == hash &&((k = e.key)== key || key.equals(k))){
  12.                V oldValue = e.value;
  13.                e.value = value;
  14.                //空实现,交给 LinkedHashMap 自己实现
  15.                e.recordAccess(this);
  16.                return oldValue;
  17.            }
  18.        }
  19.        modCount++;
  20.        // LinkedHashMap 对其重写
  21.        addEntry(hash, key, value, i);
  22.        returnnull;
  23.    }
  24.    // LinkedHashMap 对其重写
  25.    void addEntry(int hash, K key, V value,int bucketIndex){
  26.        if((size >= threshold)&&(null!= table[bucketIndex])){
  27.            resize(2* table.length);
  28.            hash =(null!= key)? hash(key):0;
  29.            bucketIndex = indexFor(hash, table.length);
  30.        }
  31.        createEntry(hash, key, value, bucketIndex);
  32.    }
  33.    // LinkedHashMap 对其重写
  34.    void createEntry(int hash, K key, V value,int bucketIndex){
  35.        Entry<K,V> e = table[bucketIndex];
  36.        table[bucketIndex]=newEntry<>(hash, key, value, e);
  37.        size++;
  38.    }      
主体的实现都是借助于 HashMap 来完成的,只是对其中的 recordAccess(),addEntry(),createEntry()进行了重写。
LinkedHashMap 的实现:
  1.        //就是判断是否是根据访问顺序排序,如果是则需要将当前这个 Entry 移动到链表的末尾
  2.        void recordAccess(HashMap<K,V> m){
  3.            LinkedHashMap<K,V> lm =(LinkedHashMap<K,V>)m;
  4.            if(lm.accessOrder){
  5.                lm.modCount++;
  6.                remove();
  7.                addBefore(lm.header);
  8.            }
  9.        }
  10.    //调用了 HashMap 的实现,并判断是否需要删除最少使用的 Entry(默认不删除)    
  11.    void addEntry(int hash, K key, V value,int bucketIndex){
  12.        super.addEntry(hash, key, value, bucketIndex);
  13.        // Remove eldest entry if instructed
  14.        Entry<K,V> eldest = header.after;
  15.        if(removeEldestEntry(eldest)){
  16.            removeEntryForKey(eldest.key);
  17.        }
  18.    }
  19.    void createEntry(int hash, K key, V value,int bucketIndex){
  20.        HashMap.Entry<K,V> old = table[bucketIndex];
  21.        Entry<K,V> e =newEntry<>(hash, key, value, old);
  22.        //就多了这一步,将新增的 Entry 加入到 header 双向链表中
  23.        table[bucketIndex]= e;
  24.        e.addBefore(header);
  25.        size++;
  26.    }
  27.        //写入到双向链表中
  28.        privatevoid addBefore(Entry<K,V> existingEntry){
  29.            after  = existingEntry;
  30.            before = existingEntry.before;
  31.            before.after =this;
  32.            after.before =this;
  33.        }  

get 方法

LinkedHashMap 的 get() 方法也重写了:
  1.    public V get(Object key){
  2.        Entry<K,V> e =(Entry<K,V>)getEntry(key);
  3.        if(e ==null)
  4.            returnnull;
  5.        //多了一个判断是否是按照访问顺序排序,是则将当前的 Entry 移动到链表末尾  
  6.        e.recordAccess(this);
  7.        return e.value;
  8.    }
clear() 清空就要比较简单了:
  1.    //只需要把指针都指向自己即可,原本那些 Entry 没有引用之后就会被 JVM 自动回收。
  2.    publicvoid clear(){
  3.        super.clear();
  4.        header.before = header.after = header;
  5.    }

总结

总的来说 LinkedHashMap 其实就是对 HashMap 进行了拓展,使用了双向链表来保证了顺序性。
因为是继承与 HashMap 的,所以一些 HashMap 存在的问题 LinkedHashMap 也会存在,比如不支持并发等。

丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:LinkedHashMap 底层分析
喜欢 (0)
[247507792@qq.com]
分享 (0)
勤劳的小蚂蚁
关于作者:
温馨提示:本文来源于网络,转载文章皆标明了出处,如果您发现侵权文章,请及时向站长反馈删除。

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00