文档章节

Java集合,LinkedHashMap底层实现和原理

郑加威
 郑加威
发布于 2018/02/28 12:58
字数 1834
阅读 1348
收藏 7

概述

文章的内容基于JDK1.7进行分析,之所以选用这个版本,是因为1.8的有些类做了改动,增加了阅读的难度,虽然是1.7,但是对于1.8做了重大改动的内容,文章也会进行说明。

LinkedHashMap,见名知义,带链表的HashMap, 所以LinkedHashMap是有序,LinkedHashMap作为HashMap的扩展,它改变了HashMap无序的特征。它使用了一个双向的链表来会维护key-value对的次序,该链表维护了map的迭代顺序,该迭代顺序和key-value对的插入顺序保持一致。LinkedHashMap重写了父类的一些方法,这些方法也会在下面的文章中进行说明。

数据结构

继承关系

java.lang.Object 
    java.util.AbstractMap<K,V> 
        java.util.HashMap<K,V> 
            java.util.LinkedHashMap<K,V> 

从上面的集成关系中看出,LinkedHashMap集成了HashMap类,所以便拥有了HashMap开放的所有功能,而LinkedList在所有功能的基础上又进行了升级,添加了记住元素添加顺序的职责。

实现接口

Serializable, Cloneable, Map<K,V> 

LinkedHashMap 可序列化,可以被克隆 ,实现了Map接口。

基本属性

private transient Entry<K,V> header;  //双向链表的头节点
private final boolean accessOrder;  //排序的规则,false按插入顺序排序,true访问顺序排序

重要方法深度解析

构造方法

//LinkedHashMap的构造方法,都是通过调用父类的构造方法来实现,大部分accessOrder默认为false
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
public LinkedHashMap() {
    super();
    accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super(m);
    accessOrder = false;
}
public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

上面是LinkedHashMap的构造方法,通过传入初始化参数和代码看出,LinkedHashMap的构造方法和父类的构造方法,是一一对应的。也是通过super()关键字来调用父类的构造方法来进行初始化,唯一的不同是最后一个构造方法,提供了AccessOrder参数,用来指定LinkedHashMap的排序方式,accessOrder =false -> 插入顺序进行排序 , accessOrder = true -> 访问顺序进行排序。

put()方法

LinkedHashMap并没有重写父类的put()方法,说明调用put方法时实际上调用的是父类的put方法。

get()方法

public V get(Object key) {
    Entry<K,V> e = (Entry<K,V>)getEntry(key); //调用父类的getEntry()方法
    if (e == null)
        return null;
    e.recordAccess(this);  //判断排序方式,如果accessOrder = true , 删除当前e节点
    return e.value;
}

 remove()

LinkedHashMap并没有重写父类的remove()方法,说明调用remove方法时实际上调用的是父类的remove()方法。

源码解析

Entry定义

private static class Entry<K,V> extends HashMap.Entry<K,V> {
    //定义Entry类型的两个变量,或者称之为前后的两个指针    
    Entry<K,V> before, after;
    //构造方法与HashMap的没有区别,也是调用父类的Entry构造方法
    Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
    }

    //删除
    private void remove() {
        before.after = after;
        after.before = before;
    }

    //插入节点到指定的节点之前
    private void addBefore(Entry<K,V> existingEntry) {
        after  = existingEntry;
        before = existingEntry.before;
        before.after = this;
        after.before = this;
    }

    //方法重写,HashMap中为空
    void recordAccess(HashMap<K,V> m) {
        LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
        if (lm.accessOrder) {
            lm.modCount++;
            remove();
            addBefore(lm.header);
        }
    }
    //方法重写 ,HashMap中方法为空
    void recordRemoval(HashMap<K,V> m) {
        remove();
    }
}

LinkedHashMap源码解析

public class LinkedHashMap<K,V> extends HashMap<K,V>
    implements Map<K,V>
{
    //可序列化版本号
    private static final long serialVersionUID = 3801124242820219131L;

    //双向链表的头指针
    private transient Entry<K,V> header;

    //双向链表的排序方法,false 插入顺序排序,true访问顺序排序
    private final boolean accessOrder;

    //构造方法,指定初始大小,指定负载因子
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

    //构造方法,指定初始容量
    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

    //无参构造方法k,采用默认参数
    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

    //将指定的m集合转化为LinkedHashmap存储
    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super(m);
        accessOrder = false;
    }

    //构造方法,指定初始容量,负载因子和排序方式
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

    //重写父类init方法,init方法在父类构造函数被调用,初始化双向链表
    //header的前驱和后继都是指向它自己
    @Override
    void init() {
        header = new Entry<>(-1, null, null, null);
        header.before = header.after = header;
    }

    //重写父类的transfer方法,在HashMap执行扩容操作时被调用,HashMap中的是通过遍历Entry[]数组的方式来实现数据的拷贝复制,重写后是通过遍历双向链表的方式来进行数据的复制。遍历双向链表的方式效率上更高一些
    @Override
    void transfer(HashMap.Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e = header.after; e != header; e = e.after) {
            if (rehash)
                e.hash = (e.key == null) ? 0 : hash(e.key);
            int index = indexFor(e.hash, newCapacity);
            e.next = newTable[index];
            newTable[index] = e;
        }
    }

    //重写父类的containsValue, 由遍历数组的方式修改为遍历列表的方式
    public boolean containsValue(Object value) {
        // Overridden to take advantage of faster iterator
        if (value==null) {
            for (Entry e = header.after; e != header; e = e.after)
                if (e.value==null)
                    return true;
        } else {
            for (Entry e = header.after; e != header; e = e.after)
                if (value.equals(e.value))
                    return true;
        }
        return false;
    }

    //重写父类的get方法
    public V get(Object key) {
        Entry<K,V> e = (Entry<K,V>)getEntry(key); //返回实体
        if (e == null)
            return null;
        e.recordAccess(this); //如果是访问顺序排序,则将e移动到链表的末尾处
        return e.value;
    }

    //清除集合
    public void clear() {
        super.clear();
        header.before = header.after = header;
    }
    //内部类实现了迭代方法
    private abstract class LinkedHashIterator<T> implements Iterator<T> {
        Entry<K,V> nextEntry    = header.after;
        Entry<K,V> lastReturned = null;

        
        int expectedModCount = modCount;

        public boolean hasNext() {
            return nextEntry != header;
        }

        public void remove() {
            if (lastReturned == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();

            LinkedHashMap.this.remove(lastReturned.key);
            lastReturned = null;
            expectedModCount = modCount;
        }

        Entry<K,V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (nextEntry == header)
                throw new NoSuchElementException();

            Entry<K,V> e = lastReturned = nextEntry;
            nextEntry = e.after;
            return e;
        }
    }

    private class KeyIterator extends LinkedHashIterator<K> {
        public K next() { return nextEntry().getKey(); }
    }

    private class ValueIterator extends LinkedHashIterator<V> {
        public V next() { return nextEntry().value; }
    }

    private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
        public Map.Entry<K,V> next() { return nextEntry(); }
    }

    // These Overrides alter the behavior of superclass view iterator() methods
    Iterator<K> newKeyIterator()   { return new KeyIterator();   }
    Iterator<V> newValueIterator() { return new ValueIterator(); }
    Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }

    //重写父类的addEntry方法
    void addEntry(int hash, K key, V value, int bucketIndex) {
        super.addEntry(hash, key, value, bucketIndex);

        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        }
    }

    //重写createEntry方法
    //执行两步操作:
    // 1. 添加到table数组中, 2 . 插入到双向链表中
    void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMap.Entry<K,V> old = table[bucketIndex];
        Entry<K,V> e = new Entry<>(hash, key, value, old);
        table[bucketIndex] = e;
        e.addBefore(header);
        size++;
    }
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }
}

下面详细的分析一下LinkedHashMap中操作的实现:

HashMap h = new LinkedHashMap();
h.put("张三", 18);

上面是简短的两句代码,来看一下到底包含了何种的操作。

上面的图片已经描述的很清楚了,在此不再添加文字的表述。
关于删除方法,感兴趣的可以自行研究。

总结

LinkedHashMap继承了HashMap类,重写了部分方法,在HashMap中一些空的实现,LinkedHashMap都做了实现,扩展了HashMap类的功能,LinkedHashMap可以保存元素的插入顺序,顺序有两种方式一种是按照插入顺序排序,一种按照访问做排序。默认以插入顺序排序,性能比HashMap略低,线程也是不安全的。

至此,Java集合的源码系列就分析完了,像HashTable,stack等集合从开发者的角度上已经不建议在使用,因为已经是比较古老的类,有了更好类做了替代。

 

© 著作权归作者所有

郑加威
粉丝 175
博文 183
码字总数 387300
作品 0
杭州
架构师
私信 提问
再谈Java数据结构—分析底层实现与应用注意事项

在回顾js数据结构,写《再谈js对象数据结构底层实现原理-object array map set》系列的时候,在来整理下java的数据结构。 java把内存分两种:一种是栈内存,另一种是堆内存 基本类型在栈区分...

zhoulujun
05/17
54
0
搞懂 HashSet & LinkedHashSet 源码以及集合常见面试题目

HashSet & LinkedHashSet 源码分析以及集合常见面试题目 经过上两篇的 HashMap 和 LinkedHashMap 源码分析以后,本文将继续分析 JDK 集合之 Set 源码,由于有了之前的 Map 源码分析的铺垫,S...

群星纪元
03/31
40
0
java.util包中集合详解

本文只是集合的概述,介绍集合之间的关系,以及各种集合的异同,不会深入介绍具体的实现,具体实现的介绍,可以参见文中提供的链接。 java集合概述 java集合整体分为collection和map两种,接...

jacksu在简书
2018/01/25
0
0
BAT面试必备——Java 集合类

本文首发于我的个人博客:尾尾部落 1. Iterator接口 Iterator接口,这是一个用于遍历集合中元素的接口,主要包含hashNext(),next(),remove()三种方法。它的一个子接口LinkedIterator在它的基...

繁著
2018/09/09
0
0
聊聊LinkedHashMap

LinkedHashMap简介 LinkedHashMap是一个根据某种规则有序的hashmap。根据名字,我们也可以看出这个集合是有hash散列的功能的同时也有顺序。hashmap是无法根据某种顺序来访问数据的,例如放入...

xpbob
2018/11/12
500
0

没有更多内容

加载失败,请刷新页面

加载更多

关于AsyncTask的onPostExcute方法是否会在Activity重建过程中调用的问题

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://blog.csdn.net/XG1057415595/article/details/86774575 假设下面一种情况...

shzwork
今天
6
0
object 类中有哪些方法?

getClass(): 获取运行时类的对象 equals():判断其他对象是否与此对象相等 hashcode():返回该对象的哈希码值 toString():返回该对象的字符串表示 clone(): 创建并返此对象的一个副本 wait...

happywe
今天
6
0
Docker容器实战(七) - 容器中进程视野下的文件系统

前两文中,讲了Linux容器最基础的两种技术 Namespace 作用是“隔离”,它让应用进程只能看到该Namespace内的“世界” Cgroups 作用是“限制”,它给这个“世界”围上了一圈看不见的墙 这么一...

JavaEdge
今天
8
0
文件访问和共享的方法介绍

在上一篇文章中,你了解到文件有三个不同的权限集。拥有该文件的用户有一个集合,拥有该文件的组的成员有一个集合,然后最终一个集合适用于其他所有人。在长列表(ls -l)中这些权限使用符号...

老孟的Linux私房菜
今天
7
0
面试套路题目

作者:抱紧超越小姐姐 链接:https://www.nowcoder.com/discuss/309292?type=3 来源:牛客网 面试时候的潜台词 抱紧超越小姐姐 编辑于 2019-10-15 16:14:56APP内打开赞 3 | 收藏 4 | 回复24 ...

MtrS
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部