LinkedHashMap详解 |
您所在的位置：网站首页 › linkedhashmap底层原理图解 › LinkedHashMap详解 |
LinkedHashMap详解
|
一、概念及概述
LinkedHashMap 继承自 HashMap，在 HashMap 基础上，通过维护一条双向链表，解决了 HashMap 不能随时保持遍历顺序和插入顺序一致的问题。在一些场景下，该特性很有用，比如缓存。在实现上，LinkedHashMap 很多方法直接继承自 HashMap，仅为维护双向链表覆写了部分方法。 当我们希望有顺序地去存储key-value时，就需要使用LinkedHashMap了 二、工作原理 1、数据结构示意图：
注意：JDK1.8中引入了红黑树，如下 上图中，淡蓝色的箭头表示前驱引用，红色箭头表示后继引用。每当有新键值对节点插入，新节点最终会接在 tail 引用指向的节点后面。而 tail 引用则会移动到新的节点上，这样一个双向链表就建立起来了。 2、put()方法的执行流程 a、首先是只加入一个元素Entry1，假设index为0：
b、当再加入一个元素Entry2，假设index为15
c、当再加入一个元素Entry3, 假设index也是0：
以上就是LinkedHashMap中put的过程了，总体来看，跟HashMap的put类似 当put元素时，不但要把它加入到HashMap中去，还要加入到双向链表中，所以可以看出LinkedHashMap就是HashMap+双向链表，下面用图来表示逐步往LinkedHashMap中添加数据的过程，红色部分是双向链表，黑色部分是HashMap结构，header是一个Entry类型的双向链表表头，本身不存储数据。 3、get()的执行流程 LinkedHashMap有对get方法进行了重写，如下： public V get(Object key) { // 调用genEntry得到Entry Entry e = (Entry)getEntry(key); if (e == null) return null; // 如果LinkedHashMap是访问顺序的，则get时，也需要重新排序 e.recordAccess(this); return e.value; }先是调用了getEntry方法，通过key得到Entry，而LinkedHashMap并没有重写getEntry方法，所以调用的是HashMap的getEntry方法：首先通过key算出hash值，然后根据hash值算出在table中存储的index，然后遍历table[index]的单向链表去对比key，如果找到了就返回Entry。（单向链表和双向链表的遍历区别？） 后面调用了LinkedHashMap.Entry的recordAccess方法，上面分析过put过程中这个方法，其实就是在访问顺序的LinkedHashMap进行了get操作以后，重新排序，把get的Entry移动到双向链表的表尾。 三、构造函数解析
LinkedHashMap提供了多个构造方法，我们先看空参的构造方法。 public LinkedHashMap() { // 调用HashMap的构造方法，其实就是初始化Entry[] table super(); // 这里是指是否基于访问排序，默认为false accessOrder = false; }首先使用super调用了父类HashMap的构造方法，其实就是根据初始容量、负载因子去初始化Entry[] table accessOrder可以设置排序，分为两种：插入顺序和访问顺序 这里accessOrder设置为false，表示按插入顺序存储，这也是默认值，即LinkedHashMap中存储的顺序是按照调用put方法插入的顺序进行排序的。LinkedHashMap也提供了可以设置accessOrder的构造方法，我们来看看这种模式下，它的顺序有什么特点？ Map linkedHashMap = new LinkedHashMap(16, 0.75f, true); linkedHashMap.put("name1", "josan1"); linkedHashMap.put("name2", "josan2"); linkedHashMap.put("name3", "josan3"); System.out.println("开始时顺序："); Set set = linkedHashMap.entrySet(); Iterator iterator = set.iterator(); while(iterator.hasNext()) { Entry entry = iterator.next(); String key = (String) entry.getKey(); String value = (String) entry.getValue(); System.out.println("key:" + key + ",value:" + value); } System.out.println("通过get方法，导致key为name1对应的Entry到表尾"); linkedHashMap.get("name1"); Set set2 = linkedHashMap.entrySet(); Iterator iterator2 = set2.iterator(); while(iterator2.hasNext()) { Entry entry = iterator2.next(); String key = (String) entry.getKey(); String value = (String) entry.getValue(); System.out.println("key:" + key + ",value:" + value); } }
关于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 implements Map.Entry { final K key; V value; Entry next; int hash;没有before和after属性啊！原来，LinkedHashMap有自己的静态内部类Entry，它继承了HashMap.Entry，定义如下: /** * LinkedHashMap entry. */ private static class Entry extends HashMap.Entry { // These fields comprise the doubly linked list used for iteration. Entry before, after; Entry(int hash, K key, V value, HashMap.Entry next) { super(hash, key, value, next); }所以LinkedHashMap构造函数，主要就是调用HashMap构造函数初始化了一个Entry[] table，然后调用自身的init初始化了一个只有头结点的双向链表。完成了如下操作：
四、遍历方式 我们先来看看HashMap使用遍历方式取数据的过程：
很明显，这样取出来的Entry顺序肯定跟插入顺序不同了，既然LinkedHashMap是有序的，那么它是怎么实现的呢？ 再来看看LinkedHashMap取遍历方式获取数据的方式：
这里其实遍历的是双向链表，所以不会存在HashMap中需要寻找下一条单向链表的情况，从头结点Entry header的下一个节点开始，只要把当前返回的Entry的after作为下一个应该返回的节点即可。直到到达双向链表的尾部时，after为双向链表的表头节点Entry header，这时候hasNext就会返回false，表示没有下一个元素了。 五、关于扩容 在HashMap的put方法中，如果发现前元素个数超过了扩容阀值时，会调用resize方法，如下： void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; boolean oldAltHashing = useAltHashing; useAltHashing |= sun.misc.VM.isBooted() && (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); boolean rehash = oldAltHashing ^ useAltHashing; // 把旧table的数据迁移到新table transfer(newTable, rehash); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }LinkedHashMap重写了transfer方法，数据的迁移，它的实现如下： void transfer(HashMap.Entry[] newTable, boolean rehash) { // 扩容后的容量是之前的2倍 int newCapacity = newTable.length; // 遍历双向链表，把所有双向链表中的Entry，重新就算hash，并加入到新的table中 for (Entry 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; } }可以看出，LinkedHashMap扩容时，数据的再散列和HashMap是不一样的。 HashMap是先遍历旧table，再遍历旧table中每个元素的单向链表，取得Entry以后，重新计算hash值，然后存放到新table的对应位置。 LinkedHashMap是遍历的双向链表，取得每一个Entry，然后重新计算hash值，然后存放到新table的对应位置。 从遍历的效率来说，遍历双向链表的效率要高于遍历table，因为遍历双向链表是N次（N为元素个数）；而遍历table是N+table的空余个数（N为元素个数）。 |
【本文地址】
今日新闻 |
推荐新闻 |