江苏龙网

  1. 主页 > 生活百科 > >

图解LinkedHashMap原理( 二 )

LinkedHashMa


图解LinkedHashMap原理

文章插图
 
image.png
因为调用了get("name1")导致了name1对应的Entry移动到了最后，这里只要知道LinkedHashMap有插入顺序和访问顺序两种就可以，后面会详细讲原理 。
还记得，上一篇HashMap解析中提到，在HashMap的构造函数中，调用了init方法，而在HashMap中init方法是空实现，但LinkedHashMap重写了该方法，所以在LinkedHashMap的构造方法里，调用了自身的init方法，init的重写实现如下：
/** * Called by superclass constructors and pseudoconstructors (clone, * readObject) before any entries are inserted into the map. Initializes * the chain. */ @Override void init() { // 创建了一个hash=-1，key、value、next都为null的Entry header = new Entry<>(-1, null, null, null); // 让创建的Entry的before和after都指向自身，注意after不是之前提到的next // 其实就是创建了一个只有头部节点的双向链表 header.before = header.after = header; }这好像跟我们上一篇HashMap提到的Entry有些不一样，HashMap中静态内部类Entry是这样定义的：
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash;没有before和after属性啊！原来，LinkedHashMap有自己的静态内部类Entry，它继承了HashMap.Entry，定义如下:
/** * LinkedHashMap entry. */ 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; Entry(int hash, K key, V value, HashMap.Entry<K,V> next) { super(hash, key, value, next); }所以LinkedHashMap构造函数，主要就是调用HashMap构造函数初始化了一个Entry[] table，然后调用自身的init初始化了一个只有头结点的双向链表 。完成了如下操作：
图解LinkedHashMap原理

文章插图
 
LinkedHashMap构造函数.png
2.5 put方法
LinkedHashMap没有重写put方法，所以还是调用HashMap得到put方法，如下：
public V put(K key, V value) { // 对key为null的处理 if (key == null) return putForNullKey(value); // 计算hash int hash = hash(key); // 得到在table中的index int i = indexFor(hash, table.length); // 遍历table[index]，是否key已经存在，存在则替换，并返回旧值 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 = https://www.isolves.com/it/cxkf/bk/2019-08-30/e.value; e.value = value; e.recordAccess(this); return oldValue; } }modCount++; // 如果key之前在table中不存在，则调用addEntry，LinkedHashMap重写了该方法 addEntry(hash, key, value, i); return null; }我们看看LinkedHashMap的addEntry方法：
void addEntry(int hash, K key, V value, int bucketIndex) { // 调用父类的addEntry，增加一个Entry到HashMap中 super.addEntry(hash, key, value, bucketIndex); // removeEldestEntry方法默认返回false，不用考虑 Entry<K,V> eldest = header.after; if (removeEldestEntry(eldest)) { removeEntryForKey(eldest.key); } }这里调用了父类HashMap的addEntry方法，如下：
void addEntry(int hash, K key, V value, int bucketIndex) { // 扩容相关 if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } // LinkedHashMap进行了重写 createEntry(hash, key, value, bucketIndex); }前面是扩容相关的代码，在上一篇HashMap解析中已经讲过了 。这里主要看createEntry方法，LinkedHashMap进行了重写 。
void createEntry(int hash, K key, V value, int bucketIndex) { HashMap.Entry<K,V> old = table[bucketIndex]; // e就是新创建了Entry，会加入到table[bucketIndex]的表头 Entry<K,V> e = new Entry<>(hash, key, value, old); table[bucketIndex] = e; // 把新创建的Entry，加入到双向链表中 e.addBefore(header); size++; }我们来看看LinkedHashMap.Entry的addBefore方法：
private void addBefore(Entry<K,V> existingEntry) { after = existingEntry; before = existingEntry.before; before.after = this; after.before = this; }从这里就可以看出，当put元素时，不但要把它加入到HashMap中去，还要加入到双向链表中，所以可以看出LinkedHashMap就是HashMap+双向链表，下面用图来表示逐步往LinkedHashMap中添加数据的过程，红色部分是双向链表，黑色部分是HashMap结构，header是一个Entry类型的双向链表表头，本身不存储数据 。
首先是只加入一个元素Entry1，假设index为0：
图解LinkedHashMap原理

文章插图
 
LinkedHashMap结构一个元素.png


推荐阅读


上一篇：Linux系统CPU负载和CPU使用率

下一篇：go语言中关于字符串使用的总结