关于java:JDK成长记8HashMap的兄弟姐妹们

30次阅读

共计 8781 个字符，预计需要花费 22 分钟才能阅读完成。

<div class=”output_wrapper” id=”output_wrapper_id” style=”width:fit-content;font-size: 16px; color: rgb(62, 62, 62); line-height: 1.6; word-spacing: 0px; letter-spacing: 0px; font-family: ‘Helvetica Neue’, Helvetica, ‘Hiragino Sans GB’, ‘Microsoft YaHei’, Arial, sans-serif;”><h3 id=”hdddd” style=”width:fit-content;line-height: inherit; margin: 1.5em 0px; font-weight: bold; font-size: 1.3em; margin-bottom: 2em; margin-right: 5px; padding: 8px 15px; letter-spacing: 2px; background-image: linear-gradient(to right bottom, rgb(43,48,70), rgb(43,48,70)); background-color: rgb(63, 81, 181); color: rgb(255, 255, 255); border-left: 10px solid rgb(255,204,0); border-radius: 5px; text-shadow: rgb(102, 102, 102) 1px 1px 1px; box-shadow: rgb(102, 102, 102) 1px 1px 2px;”><span style=”font-size: inherit; color: inherit; line-height: inherit; margin: 0px; padding: 0px;”>LinkedHashMap 的源码底层原理 </span></h3></div>

LinkedHashMap 继承自 HashMap, 然而它的底层减少了一个链表来保护 插入或者拜访程序，使得 LinkedHashMap 变动有程序性。如下图所示：

上图中能够看出，LinkedHashMap 继承了 HashMap，多了两个成员变量，tail 和 head 指针，还应用 Entry 外部类继承了 HashMap 的 Node 外部类，在原有根底上减少了 before 和 after 指针。

默认状况下，是依照插入程序的，也就是 put 的程序。LiknedHashMap 在 put 元素的时候会记录用指针，将数组元素的插入程序记录下来。

通过 重写 HashMap 的 newNode()办法，在 put 办法，插入一个 Entry 后，Entry 的 before 和 last 指针相似链表会连起来，并且LinkedHashMap 的 tail 和 head 指针也会记录下首尾元素。将插入程序用链表记录下来。

至于拜访程序的状况，你能够在一会前面的例子会提到。

<div class=”output_wrapper” id=”output_wrapper_id” style=”width:fit-content;font-size: 16px; color: rgb(62, 62, 62); line-height: 1.6; word-spacing: 0px; letter-spacing: 0px; font-family: ‘Helvetica Neue’, Helvetica, ‘Hiragino Sans GB’, ‘Microsoft YaHei’, Arial, sans-serif;”><h3 id=”hdddd” style=”width:fit-content;line-height: inherit; margin: 1.5em 0px; font-weight: bold; font-size: 1.3em; margin-bottom: 2em; margin-right: 5px; padding: 8px 15px; letter-spacing: 2px; background-image: linear-gradient(to right bottom, rgb(43,48,70), rgb(43,48,70)); background-color: rgb(63, 81, 181); color: rgb(255, 255, 255); border-left: 10px solid rgb(255,204,0); border-radius: 5px; text-shadow: rgb(102, 102, 102) 1px 1px 1px; box-shadow: rgb(102, 102, 102) 1px 1px 2px;”><span style=”font-size: inherit; color: inherit; line-height: inherit; margin: 0px; padding: 0px;”>TreeMap 的源码底层原理 </span></h3></div>

同理 TreeMap 也是一个有序的 Map，底层是通过红黑树来维持程序的，并且 TreeMap 反对自定义排序规定。原理下图所示：

TreeMap 没有继承 HashMap，他本人实现了 put 办法，次要逻辑是生成树 root 节点和一般叶子节点。

刚开始树为空，必定是进入第一步，生成 root 节点，创立一个 Entry 就完结了，这个 Entry 中多了 left 和 partent、right，color 等变量。

创立 TreeMap 的时候能够指定排序规定，默认不指定应用 Key 值默认的 compare 办法, 进行排序生成一棵排序后的二叉树，之后调整为红黑树。

而且它没有数组的构造，它就是一个纯正的红黑树，get 的时候通过遍历红黑树获取元素。

在遍历的时候，TreeMap 通过 EntryIterator 进行从小到大的遍历，实现有序拜访。

<div class=”output_wrapper” id=”output_wrapper_id” style=”width:fit-content;font-size: 16px; color: rgb(62, 62, 62); line-height: 1.6; word-spacing: 0px; letter-spacing: 0px; font-family: ‘Helvetica Neue’, Helvetica, ‘Hiragino Sans GB’, ‘Microsoft YaHei’, Arial, sans-serif;”><h3 id=”hdddd” style=”width:fit-content;line-height: inherit; margin: 1.5em 0px; font-weight: bold; font-size: 1.3em; margin-bottom: 2em; margin-right: 5px; padding: 8px 15px; letter-spacing: 2px; background-image: linear-gradient(to right bottom, rgb(43,48,70), rgb(43,48,70)); background-color: rgb(63, 81, 181); color: rgb(255, 255, 255); border-left: 10px solid rgb(255,204,0); border-radius: 5px; text-shadow: rgb(102, 102, 102) 1px 1px 1px; box-shadow: rgb(102, 102, 102) 1px 1px 2px;”><span style=”font-size: inherit; color: inherit; line-height: inherit; margin: 0px; padding: 0px;”>HashTable、HashSet、LinkedHashSet、TreeSet 底层原理 </span></h3></div>

最初咱们聊一下 HashMap 的其余兄弟姐妹。为什么这么说呢？

因为 HashTable 和 HashMap 外围区别就是应用 synchronized 保障线程平安，这个和 Vector+ArrayList 很像。

因为 HashSet 应用了 HashMap，只不过 add 办法时候的 value 都是 new Object()而已，联合 map 的个性，同一个 key 值只能存在一个，map 在 put 的时候，会 hash 寻址到数组的同一个地位去，而后笼罩原来的值，所以 Set 是去重的。默认是无序的。外围代码如下：

public boolean add(E e) {return map.put(e, PRESENT)==null;
}

因为 LinkedHashSet 继承了 HashSet, 此时 HashSet 通过应用 LinkedHashMap 是能够进行拜访有序的保障。

因为 TreeSet 也同理，默认是依据 key 值的 compare 办法来排序的，能够自定义 Comparator，底层应用了 TreeMap，add 元素时，同样是空的 Object，同样去重，然而 TreeSet 拜访是能够有序。

 public boolean add(E e) {return map.put(e, PRESENT)==null;
   }

它们的源码都极其简略，没什么好钻研的。所以重点是，你懂了之前的 HashMap、LinkedHashMap、TreeMap 才是要害。**

上面咱们来看一些应用这些汇合的场景：

<div class=”output_wrapper” id=”output_wrapper_id” style=”width:fit-content;font-size: 16px; color: rgb(62, 62, 62); line-height: 1.6; word-spacing: 0px; letter-spacing: 0px; font-family: ‘Helvetica Neue’, Helvetica, ‘Hiragino Sans GB’, ‘Microsoft YaHei’, Arial, sans-serif;”><h3 id=”hdddd” style=”width:fit-content;line-height: inherit; margin: 1.5em 0px; font-weight: bold; font-size: 1.3em; margin-bottom: 2em; margin-right: 5px; padding: 8px 15px; letter-spacing: 2px; background-image: linear-gradient(to right bottom, rgb(43,48,70), rgb(43,48,70)); background-color: rgb(63, 81, 181); color: rgb(255, 255, 255); border-left: 10px solid rgb(255,204,0); border-radius: 5px; text-shadow: rgb(102, 102, 102) 1px 1px 1px; box-shadow: rgb(102, 102, 102) 1px 1px 2px;”><span style=”font-size: inherit; color: inherit; line-height: inherit; margin: 0px; padding: 0px;”>LinkedHashMap 利用：Storm 中的 LRUMap</span></h3></div>

之前你应该相熟了 LinkedHashMap 的的插入有序性。调用 put 办法时，通过链表记录插入的程序。然而 LinkedHashMap 还能够反对拜访有序性。依照 get 办法的拜访程序，进行排序。比方：

这个底层和插入有序很像，也是 通过一个变量叫做 accessOrder 和 HashMap 的 put 办法和 get 中重写预留的办法做到的。

每拜访一次元素，会将元素挪动链表的指针，将刚拜访的元素挪动到链表的尾部。

基于这个机制咱们能够实现一个 LRU 的 Map，实现有主动生效 LRU 内存缓存 Map, 这样当元素个数超过缓存容量时，通过 LRU 能够保障最近起码拜访的元素被移除掉。

如果你看过 storm 的源码的话，你会看到有这样一个 LRUMap 实现：

import java.util.LinkedHashMap;
import java.util.Map;


public class LRUMap<A, B> extends LinkedHashMap<A, B> {
    private int maxSize;


    public LRUMap(int maxSize) {super(maxSize + 1, 1.0f, true);
        this.maxSize = maxSize;
    }


    @Override
    protected boolean removeEldestEntry(final Map.Entry<A, B> eldest) {return size() > maxSize;
    }
}

这个办法很奇妙的基于 LinkedHashMap 拜访有序，实现了一个 LRUMap。

首先通过 maxSize 限定缓存 Map 的大小，调用父类构造函数，扩容因子为 1.0f，第三个入参示意 accessOrder=true。重写了 removeEldestEntry。

其次通过 LinkedHashMap, 在 get 办法时候，如果 accessOrder 是 true，会将 get 到的元素，放到链表的尾部。保障 Map 缓存中最新拜访的元素的不会被 LRU 掉。get 办法源码如下：

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

能够看到有一个办法 afterNodeAccess, 通过这个来管制 LinkedList 拜访时，单向链表的程序，从而达到拜访有序。

在 put 办法的时候有一个扩大的入口 afterNodeInsertion 中，HashMap 默认这个办法是空的，什么都不做。然而 LinkedHashMap 实现了这个办法，并且通过 removeEldestEntry+accessOrder 管制，如果拜访有序参数为 true，并且头节点有元素，且 removeEldestEntry 满足，即 size() > maxSize，缓存大小达到下限 maxSize，会进行一次 removeNode 操作，移除链表第一个元素。第一个元素就是最近起码拜访的元素。如下图所示：

<div class=”output_wrapper” id=”output_wrapper_id” style=”width:fit-content;font-size: 16px; color: rgb(62, 62, 62); line-height: 1.6; word-spacing: 0px; letter-spacing: 0px; font-family: ‘Helvetica Neue’, Helvetica, ‘Hiragino Sans GB’, ‘Microsoft YaHei’, Arial, sans-serif;”><h3 id=”hdddd” style=”width:fit-content;line-height: inherit; margin: 1.5em 0px; font-weight: bold; font-size: 1.3em; margin-bottom: 2em; margin-right: 5px; padding: 8px 15px; letter-spacing: 2px; background-image: linear-gradient(to right bottom, rgb(43,48,70), rgb(43,48,70)); background-color: rgb(63, 81, 181); color: rgb(255, 255, 255); border-left: 10px solid rgb(255,204,0); border-radius: 5px; text-shadow: rgb(102, 102, 102) 1px 1px 1px; box-shadow: rgb(102, 102, 102) 1px 1px 2px;”><span style=”font-size: inherit; color: inherit; line-height: inherit; margin: 0px; padding: 0px;”>TreeSet 和 TreeMap 利用：HDFS 中文件租约时长保护 </span></h3></div>

在 HDFS 中 LeaseManager，有一个十分经典契约查看的机制，对所有的契约，依照续约的工夫在 TreeSet 里排序，前面查看的时候，每次就挑最老的那个契约来查看，是否超过 60 分钟。如果超过，就开释契约再查看第二老的那个契约，如果最老的契约都没过期，那就阐明其余的契约必定都没过期。

用这个办法，能够奇妙的防止说，后盾线程每隔肯定工夫，就要把所有的契约都遍历一遍来查看外面的最近一次续约的工夫

如果一个客户端申请契约过后，超过 1 小时，都还没有续约，那么这个契约会被主动开释掉，这是他的一个很重要的机制。

如下图所示：

好了，到这里，《JDK 源码成长记》汇合篇的常识根本就带大家学习完了。当然，你肯定要联合学到的，一直本人看源码剖析思路，之后讲给共事，和他们讨论一下，能力更多的死记硬背。而不是看过文章之后，80% 还给我了。

你能够在评论区回复你遇见的应用这些汇合的场景，欢送你评论。

你也能够搜寻下你们的业务代码，看看应用了哪些汇合类，怎么用的，有没什么隐患？

下一篇我会进行章节总结，也会给大家提供一些常见面试题，让大家检测下学习成绩。置信大家把握了源码原理后，无论是看源码，还是面试，或者利用都能够熟能生巧。

除了明天常识，技能的成长，给大家带来一个金句甜点，完结我明天的分享：保持的三个秘诀之一个性化。

保持的秘诀除了之前提到的视觉化、指标化，最初一个就是个性化。每个人都本人喜爱的事件，你不能保持你不喜爱的事件，还是那个例子，如果你要减肥，比方你就不喜爱吃西蓝花，他尽管是热量低的食物，确实很适宜减脂塑形的时候吃，然而非要你吃，头两天还好，你能忍耐，然而你必定是保持不下来的，你要找到适宜你本人的低热量食物，定制化的调整，不喜爱的事件怎么能保持下来呢？静止也是一样，你就是不喜爱做俯卧撑，就喜爱平板撑持，那就换成你喜爱的，你做不了 Burbee 跳，你就能够做半个等等 …. 而且个性化很重要的一点是比方不喜爱看成长记的时候，感觉费脑子，就看看今日头条，微博，朋友圈处分本人一下，再看一篇成长记，之后再处分本人做些本人喜爱的事件。能够做一些重要的事件，在做一些本人喜爱的事件。适当的个性化调整，也是让你保持后退，慢慢造成习惯的个性化。工夫久了置信你不这么做都会感觉好受的。

所以，当你抉择你能保持而且喜爱的，变成一个好的习惯，还始终揭示本人感觉值，就肯定能保持下来。记住保持的秘诀视觉化、指标化、个性化，你能够试试。

最初，大家能够在浏览完源码后，在茶余饭后的时候问问共事或同学，你也能够分享下，讲给他听听。

欢送大家在评论区留言和我交换。

（申明：JDK 源码成长记基于 JDK 1.8 版本，局部章节会提到旧版本特点）