JDK成长记8：HashMap的兄弟姐妹们

时间：2023-04-01 22:28:21 Java

LinkedHashMap的源码底层原理

LinkedHashMap的源码底层原理LinkedHashMap继承自HashMap，只是在其底层增加了一个链表来维护插入或访问顺序，使得LinkedHashMap顺序变化，如下图所示：从中可以看出上图中，LinkedHashMap继承了HashMap，多了两个成员变量，tail和head指针，同样使用Entry内部类继承了HashMap的Node内部类，并在原来的基础上增加了before和after指针。默认是按照插入的顺序，也就是put的顺序。LinkedHashMap在放元素的时候会记录指针，记录数组元素的插入顺序。通过重写HashMap的newNode()方法，在put方法中插入一个Entry后，Entry的before和last指针会像链表一样连接起来，LinkedHashMap的tail和head指针也会记录first和last元素。用链表记录插入顺序。至于访问顺序，你可以在后面的例子中提到。

TreeMap的源码层原理/h3>

TreeMap的源代码底层原理同理TreeMap也是一个有序的Map，底层通过红黑树维护顺序，TreeMap支持自定义排序规则。普通叶节点。树一开始是空的，所以肯定是第一步，生成一个根节点，创建一个Entry，就结束了。这个Entry中有left、partent、right、color等变量。创建TreeMap时，您可以指定排序规则。默认不指定使用默认Key值的compare方法，排序后生成排序后的二叉树，然后调整为红黑树。而且它没有数组结构，是纯红黑树，获取的时候通过遍历红黑树获取元素。TreeMap在遍历时使用EntryIterator从小到大遍历，实现有序访问。

HashTable、HashSet、LinkedHashSet、TreeSet底层原理

HashTable、HashSet、LinkedHashSet、TreeSet的底层原理最后说说为什么其他HashMap的师兄师姐这么说？因为HashTable和HashMap最核心的区别就是使用synchronized来保证线程安全，这点和Vector+ArrayList很相似。因为HashSet使用了HashMap，但是add方法里面的值都是newObject()。结合map的特点，同一个key只能有一个keyvalue。当放置地图时，它将散列地址数组中的相同键。该位置被移除，然后原始值被覆盖，因此该Set被删除了。默认是无序的。核心代码如下：publicbooleanadd(Ee){returnmap.put(e,PRESENT)==null;}由于LinkedHashSet继承了HashSet，此时HashSet可以通过使用LinkedHashMap来保证有序访问。TreeSet也是一样，默认是按照key-value的compare方式排序的。您可以自定义比较器。底层使用TreeMap。添加元素时，也是一个空的Object，去重了，但是TreeSet的访问是可以有序的。publicbooleanadd(Ee){returnmap.put(e,PRESENT)==null;}他们的源代码极其简单，没有什么可研究的。所以重点是，你理解前面的HashMap，LinkedHashMap，TreeMap是关键。**让我们看看使用这些集合的一些场景：

LinkedHashMap应用：LRUMapinStorm</div>LinkedHashMap应用：在Storm中使用LRUMap之前，大家应该熟悉LinkedHashMap的插入顺序。在调用put方法时，通过链表记录插入顺序。但是LinkedHashMap也可以支持访问排序。按照get方法的访问顺序排序。比如：这个底层很像插入顺序，也是通过一个叫accessOrder的变量和HashMap的put方法以及get中重写reservation的方法来实现的。每访问一个元素，该元素就会被移动到链表的指针，而刚刚访问的元素又被移动到链表的尾部。基于这种机制，我们可以实现一个LRUMap，实现一个自动失效的LRU内存缓存Map，这样当元素数量超过缓存容量时，LRU可以保证最近最少访问的元素被移除。如果你看过storm的源码，你会看到有这么一个LRUMap实现：importjava.util.LinkedHashMap;importjava.util.Map;publicclassLRUMapextendsLinkedHashMap{私有intmaxSize;publicLRUMap(intmaxSize){super(maxSize+1,1.0f,true);this.maxSize=maxSize;}@OverrideprotectedbooleanremoveEldestEntry(finalMap.Entryelderest){returnsize()>maxSize;}}这个方法巧妙的基于LinkedHashMap的访问顺序，实现了一个LRUMap。首先通过maxSize限制缓存Map的大小，调用父类构造函数，扩展因子为1.0f，第三个入参表示accessOrder=true。覆盖removeEldestEntry。其次，通过LinkedHashMap，在get方法中，如果accessOrder为true，则get元素会被放到链表的末尾。确保Map缓存中最近访问的元素不会被LRU丢弃。get方法源码如下：publicVget(Objectkey){Nodee;如果((e=getNode(hash(key),key))==null)返回null；if(accessOrder)afterNodeAccess(e);returne.value;}可以看到有一个方法afterNodeAccess，通过它来控制LinkedList访问时单向链表的顺序，从而实现有序访问。在put方法中，有一个扩展入口afterNodeInsertion。HashMap默认此方法为空，不执行任何操作。但是LinkedHashMap实现了这个方法，它是由removeEldestEntry+accessOrder控制的。如果访问顺序参数为真，且头节点有元素，且满足removeEldestEntry，即size()>maxSize，且缓存大小达到上限maxSize，则执行removeNode操作，移除第一个元素链表的。第一个元素是最近最少访问的元素。如下图所示：

TreeSet和TreeMap应用：HDFS中文软件租约时间维护