Coin163

首页 > 史上最详细的LinkedHashMap详解--源码分析

史上最详细的LinkedHashMap详解--源码分析

2021腾讯云限时秒杀,爆款1核2G云服务器298元/3年!(领取2860元代金券),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1062

2021阿里云最低价产品入口+领取代金券(老用户3折起),
入口地址https://www.aliyun.com/minisite/goods

相关推荐:源码分析-Android中的消息机制详解

本人原创,转载请注明出处哈:http://blog.csdn.net/tyhj_sf/article/details/51105453 1 引言 个人认为,不亲自阅读和熟悉Android的源码,不了解Android源码背后的实现机理,就不能真正成为Android开发的高手。前两天为了了解android的消息处理机制,我阅读

史上最详细的LinkedHashMap详解–源码分析

ps.本文所有源码都是基于jdk1.6

LinkedHashMap数据结构

由下面代码可知,LinkedHashMap继承自HashMap。所以它保留了HashMap的数据结构,但是与之不同的是,它自己维护了一个双向循环链表,来保证LinkedHashMap的顺序。所以LinkedHashMap实际上HashMap的数据结构+双向循环链表的结构,如图1-1所示。

private transient Entry<K,V> header;  //双向循环链表表头
private final boolean accessOrder;    //true的话按访问顺序排序(类似LRU);false按插入顺序排序;默认是false
void init() {    //初始化一个双向循环链表
    header = new Entry<K,V>(-1, null, null, null);
    header.before = header.after = header;
}

private static class Entry<K,V> extends HashMap.Entry<K,V> {
    // These fields comprise the doubly linked list used for iteration.
    Entry<K,V> before, after;
    ...
}

这里写图片描述图1-1

相关推荐:SpringMVC类型转换、数据绑定详解[附带源码分析]

@Override public Object resolveArgument(MethodParameter methodParameter, ModelAndViewContainer modelAndViewContainer, NativeWebRequest nativeWebRequest, WebDataBinderFactory webDataBinderFactory) throws Exception { Map<String,St

LinkedHashMap基础方法

  • LinkedHashMap的put方法
public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);//在LinkedHashMap中重写了
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);//在LinkedHashMap中重写了
    return null;
}

LinkedHashMap没有对put方法重写,所以LinkedHashMap继承了HashMap的put方法,但是不一样的是LinkedHashMap重写了recordAccess和addEntry这两个函数。下面让我们分析一下这两个函数变得有什么不同。

void recordAccess(HashMap<K,V> m) {    //这个函数的作用就是,如果accessOrder是true的话,那么
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
    if (lm.accessOrder) {     //accessOrder默认是false
        lm.modCount++;
        remove();
        addBefore(lm.header);
    }
}
void addEntry(int hash, K key, V value, int bucketIndex) {
    createEntry(hash, key, value, bucketIndex);
    // Remove eldest entry if instructed, else grow capacity if appropriate
    Entry<K,V> eldest = header.after;
    if (removeEldestEntry(eldest)) {
        removeEntryForKey(eldest.key);
    } else {
        if (size >= threshold)
            resize(2 * table.length);
    }
}

总结:LinkedHashMap的put操作,不仅包含了HashMap的put操作,而且还需要维护插入的顺序,也就是不管accessOrder是ture还是false,插入一个数据都是在双向循环链表的表尾插入数据。

  • LinkedHashMap的get方法
public V get(Object key) {
    Entry<K,V> e = (Entry<K,V>)getEntry(key);
    if (e == null)
        return null;
    e.recordAccess(this);   //get方法中也用到了这个方法,上面有代码
    return e.value;
}

get方法很简单,和HashMap查找方式基本一样,但是有一点需要注意的是,如果accessOrder是ture,也就是上面所说的,那么它就会按照访问的顺序排序(类似LRU,只不过是不淘汰),也就是按照访问的顺序维护这个循环双向链表,也就是如果accessOrder是true,我需要把访问的这个key移到双向循环链表的表尾。

原文

史上最详细的LinkedHashMap详解–源码分析 ps.本文所有源码都是基于jdk1.6 LinkedHashMap数据结构 由下面代码可知,LinkedHashMap继承自HashMap。所以它保留了HashMap的数据结构,但是与之不同

------分隔线----------------------------