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

<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的源码底层原理

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指针也会记录下首尾元素。将插入程序用链表记录下来。

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

TreeMap的源码底层原理

同理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>

HashTable、HashSet、LinkedHashSet、TreeSet底层原理

最初咱们聊一下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才是要害。**

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

LinkedHashMap利用：Storm中的LRUMap

之前你应该相熟了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>

TreeSet和TreeMap利用：HDFS中文件租约时长保护

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

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

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

如下图所示：

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

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

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

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

金句甜点

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

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

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

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

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

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

本文由博客一文多发平台 OpenWrite 公布！