今天给大家介绍下八股文中的两个重要成员，LinkedHashMap和TreeMap。
这两者都实现了Map接口，也经常会在面试中被拿来与HashMap比较。
到底它们能使用哪些魔法呢，接下来，就让我们开启探秘之旅。
前言
首先我们来看一下HashMap，这玩意儿可是个八股的高频考点，你要是讲不出个1 2 3 4 5来，面试官可是会不高兴的。
当初有写过一篇《HashMap在多线程下数据丢失问题》文章，大概讲了一下HashMap的线程安全问题。其中也涉及到了一些初始化，负载因子，解决哈希冲突的方法等。并且解释了个魔法版的在多线程情况下也能数据不丢失的情况（说是不丢，但其实也有问题。具体感兴趣的朋友可以直接百度搜索下文章看看，并没有放到公众号中）。
此处我就大概的描述下。
HashMap的知识点，大致有以下这么多点：
- HashMap是线程不安全的
- HashMap无序
- 底层数据结构在1.8之后为数组+链表+红黑树
- 链表和红黑树的转换
- 1.8之后链表由头插法变为尾插
- 扩容机制
- 负载因子以及初始化时的特别操作
- 容量的取值的特别操作
- Hash算法的优雅之处
- 计算哈希槽的优雅之处
- 其他解决哈希冲突的方法
- .............
基本上问的内容都不会脱离上面列的知识点了吧，当然也可能是我眼界问题，如果有缺漏的也希望广大朋友们指出。
由于并不是本篇的重点，所以只列出可能有的知识点，感兴趣的小伙伴可以再细致的了解下。
LinkedHashMap
这东西继承于HashMap，所以LinkedHashMap大部分的特性和HashMap是一致的。
至于为什么说是大部分特性呢？这是因为LinkedHashMap本身其实是HashMap + 链表的数据结构，所以它是有序的。
而且它有两种顺序选择。1：按元素插入顺序，2：按元素访问顺序。是通过内部的域（accessOrder）来控制的，可以在构造时指定，为true表示按元素访问顺序。
朋友们，如果单纯说按元素访问顺序排序你会想到什么？这不妥妥的实现LRU算法的逻辑吗？再想想我们之前的LRU算法是怎么实现的，内部数据接口就是链表+数组呀。
所以是的，用LinkedHashMap也是可以实现LRU算法的。不过也并不能直接用，需要做些改造，接下来我们就一起来看看吧。
public class LRUCache<K,V> extends LinkedHashMap<K,V> {
private int maxCapacity;
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > maxCapacity;
}
public void setMaxCapacity(int maxCapacity) {
this.maxCapacity = maxCapacity;
}
}
怎么样，是不是看着很简单。内部的逻辑都由JDK帮我们实现好了。
咱们主要实现removeEldestEntry方法，这个方法是在LinkedHashMap有调用到，在每次put时调用removeEldestEntry方法判断是否需要移除最旧未访问到的元素。详细代码如下：
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
可以看到相比于我们自己基于链表+数组的实现方式，简洁很多，而且通常情况下也更不容易出错。因此活用JDK自己的实现是一种很好的工作方式，也能更有效率。当然，该了解的原理咱们也还是得了解的。
TreeMap
这玩意儿吧，业务中好像是挺少用到的。但实际上，它使用场景非常广泛，比如大名鼎鼎的一致性哈希算法，就可以使用TreeMap来实现。具体如何，请听我细细道来。
TreeMap底层数据结构是红黑树，是一种自平衡二叉排序树（但是又非严格的平衡），更倾向于局部的平衡，通常通过左旋或者右旋来维持自身的平衡。具体我就不详说了（主要是还挺复杂的，真的要详细的话可以单独水开一章）。
一致性哈希算法又是啥呢，这东西，八股也经常考。这是在分布式领域里非常重要的一个算法，用于解决多节点情况下的负载算法。
主要思路是将多个节点组成一个圆，当有流量访问时计算对应的hash值，然后找出大于该hash值的最近的一个节点，将该流量分配。
Redis集群和RocketMq内部就有使用这种算法来做负载均衡。如此当有一个节点失效或者插入一个新节点时，也只会有部分数据需要迁移或者直接失效而已。
测试方法如下：
public class TreeMapMain {
public static void main(String[] args) {
TreeMap<Integer, String> nodeMap = new TreeMap<>();
nodeMap.put(RandomUtils.nextInt(), "node1");
nodeMap.put(RandomUtils.nextInt(), "node2");
nodeMap.put(RandomUtils.nextInt(), "node3");
System.out.println(nodeMap);
for (int i = 0; i < 10; i++) {
int hashCode = RandomUtils.nextInt();
System.out.println(hashCode);
SortedMap<Integer, String> tailMap = nodeMap.tailMap(hashCode);
Integer matchNodeKey = !tailMap.isEmpty() ? tailMap.firstKey() : nodeMap.firstKey();
System.out.println(nodeMap.get(matchNodeKey));
}
}
}
主要就是SortedMap<Integer, String> tailMap = nodeMap.tailMap(hashCode);这一段，tailMap方法语义是返回大于等于key的子树。再通过firstKey找到最小的一个节点，如此就完成了一致性哈希算法。所以理念上虽然会感觉复杂，但是基于JDK我们还是可以很简单的实现。
有朋友或许就会问了，如果哈希分布不合理，3个节点并不是均等分布的怎么办呢？就比如一共100个数，node1是0-50，node2是51-90，node3是91-100。如此的分发，流量完全不对等，会出现部分节点负载过高，部分节点又很闲置。
这个问题问得很好，不过也别担心，业界也已经有很合理的解法了，那就是虚拟节点。将多个虚拟节点映射成1个真实的节点，当访问虚拟节点时其实就是访问真实节点了。如此节点分得越细，就越不容易出现负载不均的问题了。
图例和代码就不详细展示了，免得像水字数，就当我是提供了个思路给广大的小伙伴，让小伙伴自己思考一下图解与详细代码的实现吧。
最后
今天的分享到这里就结束了，写的没有特别详细，整体更像是提供了一个思路，也留了部分的坑留待后续填上。
今天我们主要是列举了一些HashMap的知识点，以及LinkedHashMap的内部存储结构和可以用到的场景，另外就是讲解了一下一致性哈希算法以及通过TreeMap如何简单的实现它。
希望大家能有收获，我们下期再见～
标签：HashMap,JDK,优雅,nodeMap,算法,哈希,节点,LinkedHashMap From： https://www.cnblogs.com/aischen/p/16950239.html