Map&Set

  说到Map，大家都知道它是双列集合的根接口，用来保存键值对数据。但很多时候人们对于它实现类的效率和使用限制都是通过别人的总结记住的，所以今天就从数据结构的角度和大家一起分析它的几个常用实现类：HashMap、HashTable、ConcurrentHashMap、LinkedHashMap和TreeMap。
  在分析源码之前我们先来看看一些常用的API，毕竟会用是第一要务。

方法	解释
V put(K key, V value)	返回当前key对应的更新前的value
V get(Object key)	返回指定键所映射的值或null
V remove(Object key)	如果存在一个键的映射关系，则将其从此映射中移除
int size()	返回此映射中的键-值映射关系数
Set<K> keySet()	返回此映射中包含的键的 Set 视图
Collection<V> values()	返回此映射中包含的值的 Collection 视图
Set<Map.Entry<K,V>> entrySet()	返回此映射中包含的映射关系的 Set 视图。

  其中Entry是键值对对象。它的常用方法如下。

方法	解释
K getKey()	获得当前entey的key
V getValue()	获得当前entry的value

  正如我们刚才分析的那样，我们学Map的时候一般都是先学Map，然后再学Entry，所以我们会有一种感觉就是Entry是Map中抽取出来的数据。但事实却恰恰相反，Map中的数据其实是一个Node数组（Node实现了Entry）。JDK8第396行：transient Node<K,V>[] table;。再看API中：Set<Map.Entry<K,V>> entrySet()，我们就又知道，Entry是Map一个内部接口！
  我们先分析第一个，也是最最常用的HashMap。HashMap是依靠哈希表构建的Map，说详细点就是应该存放的位置是由Entry数组的key值由Hash函数计算出来的。而提到Hash表我们一般都会想到三条：装载因子、哈希函数、冲突解决方案。
  首先第一条，装载因子。HashMap默认的装载因子是0.75，所以当Map容量超过75%时，会将最大容量增加一倍。

DEFAULT_LOAD_FACTOR 增加容量和阈值

  第二点就是哈希函数，它的哈希值是用key自己的哈希值（设为h）异或上h无符号右移16位产生的结果。例如：0000 0111 0000 1101 1110 1010 0100 1110 ₍₂₎，右移16位得到：0000 0000 0000 0000 0000 0111 0000 1101 ₍₂₎，再和自己异或得到：0000 0111 0000 1101 1110 1101 0100 0011 ₍₂₎。
  从下图我们也能看出来为什么HashMap的键值可以为空，因为他不是直接使用key的哈希值，做了一个三元运算。
  那么key对象的哈希值怎么计算呢？这个其实源码就看不出来，因为Object中的hashCode()是一个native方法。后来的类如果覆盖后我们更无从得知。

HashMap中key的哈希值 Object哈希值

  第三点是冲突解决方案。哈希表冲突解决方案分为两种：开散列法和闭散列法。我们得看看put调用的putVal()函数，这个才是真正起到插入功能的函数（只截了部分图。而且由于集合之间的继承、实现体系超级复杂，只挑了我们直接的那部分使用的讲解）。第5行能发现，如果通过哈希值计算出来的位置没有被使用，则直接插入。否则，它会判断key是否相等（第9行），相等即保存，在26行进行value的替换。否则会做循环（第14行），能一直next空，则在尾部插入新数据，若循环时遇到相同key值的情况，保存，等到26行进行value的替换。看到这里我们也就很明白，这是开散列的方法。但在JDK8中，哈希表已经不再是数组+链表的组合了，看11行和17行，这两行是对应的。当插入的是这个分支的第九个时会给这个链表转化成红黑树。这样做是为了减小平均查找时间。

putVal()（由于太长，把源码取出来稍微改了排版）

  看到这里还有一个问题，就是装载因子的计算时的分子是按照Node数组被使用的个数来计算，还是整个HashMap的size来计算？答案是整个HashMap的size。上图中完整实现了各种情况的entry插入，可以分成两类，一类是key重复的情况，上图第31行直接返回老的value。第二类是key不重复的情况，分析之后可以发现，无论是插入Node数组还是开散列后的链表都会走下图的662行，即size会加1。

++size（和上图紧密衔接）

  到这里HashMap的简单分析就结束了，对于HashTable，一般码农培训班的视频里都会指出，它与HashMap唯一的不同就是它是线程安全的类，事实上也确实如此。但HashTable是JDK 1.1里的集合，它还继承了已经被弃用的Dictionary类。在JDK 1.2里，为了融入现在的集合体系，它才实现了Map接口。现在已经不推荐使用HashTable，如果需要用到，对并发没有要求的情况下使用HashMap，对并发有要求的情况下使用ConcurrentHashMap。（原话：If a thread-safe implementation is not needed, it is recommended to use HashMap in place of Hashtable. If a thread-safe highly-concurrent implementation is desired, then it is recommended to use java.util.concurrent.ConcurrentHashMap in place of Hashtable.）
  第三个就是ConcurrentHashMap，ConcurrentHashMap直接实现的是ConcurrentMap接口，而ConcurrentMap继承了Map。翻下源码你会发现，这个类光内部类就有53个，可以说是超级复杂了。它的结构和参数与HashMap一样，也是数组+链表+红黑树的结构。不过它已经不再支持key为null了。

不支持key为空

  在JDK1.7中ConcurrentHashMap实现并发安全性是对Segment进行分段加锁。每个Map是多个Segment，每一个Segment就是一个小的HashMap。图解如下：

static final class Segment<K,V> extends ReentrantLock implements Serializable {
        transient volatile HashEntry<K,V>[] table;
        transient int count;
    }

JDK1.7结构

  而在JDK1.8中已经不再使用Segment来完成分段锁，而是直接对Node数组进行操作。第1016行，如果数组为空或者长度为0则初始化数组。第1018行，如果查询到的数组中元素为null，把null和新Node互换，即插入进去。第1023行是为了转移数据做准备，本文不分析。我们先看第1027行，f 是Node数组中的元素，也就是一个链表或红黑树分支的头，对这个节点进行加锁来控制并发问题。在默认的情况下，最高可同时支持16个线程进行访问。
  这里需要提一下的是ConcurrentHashMap的哈希值计算和HashMap不同，它采用了更复杂的方法使数据能更均匀的插入。

JDK1.8加锁 ConcurrentHashMap哈希值

  看到这里，ConcurrentHashMap的四个要点：装载因子、哈希函数、冲突解决方案和并发控制的分析其实都已经结束了。但还得一提个问题，就是数组的链表分支节点个数大于8的时候一定会转换成红黑树吗？这里就和HashMap不同，它不一定转换成红黑树。当数组本身的长度大于等于64时才转换为红黑树。

调用treeifyBin 转换条件

  第四个是LinkedHashMap。它继承了HashMap，自然也是线程不安全的集合。它和HashMap的区别是它是按照key值有序的（迭代顺序和加入顺序一致）。翻阅源码可以发现，LinkedHashMap并没有重写put()和putVal()方法，它实现有序是通过重写newNode()方法和增加一个Entry类继承HashMap.Node类实现的。同时在LinkedHashMap多了两个属性：ransient LinkedHashMap.Entry<K,V> head;和transient LinkedHashMap.Entry<K,V> tail;

head & tail 重写newNode() 继承HashMap.Node

  真正实现双向链表的是newNode()中的linkNodeLast()方法。

实现双向链表

  HashMap和LinkedHashMap都是通过同一个putVal()方法进行的插入。我们刚才分析的时候还有一句重要的代码没有分析。afterNodeAccess(e);。在解释这句代码之前，先看个例子。如果第三个参数为true，结果为图一，为false结果为图二。

三个参数的构造函数 图一
图二

  也就是数第三个参数为true时，对链表put已存在的key时会把此entry移至Map的尾部。这个参数被JDK叫做accessOrder。当他为真时afterNodeAccess()的功能会被唤醒把被操作的节点移至尾部。除了put()还有get()中也调用了这个方法。这个算法被叫做LUR（Least Recently Used），核心思想是如果数据最近被访问过，那么将来被访问的几率也更高，就给它放在最前面（注意：最后面是最前面，因为最后面是最近一次插入的）。它可以实现小型的缓存机制。

afterNodeAccess()

  LinkedHashMap结束后，就剩下最后一个TreeMap了。TreeMap是按key生成的一颗红黑树，可以说是很难了。这里不深入分析，只讨论一下如何使用。
  它是按key的自然顺序进行排列的。如果是自定义的数据类型，需要传入一个比较器，比较器是实现自定义顺序的关键。

TreeMap例子

  到这里，常用的5个实现类就结束了，单个实现类的更深入分析以后会发。而Set其实就很简单了。其中由于HashTable不建议使用，自然不再分析。HashSet的底层维护的是一个HashMap，TreeSet的底层维护的是一个TreeMap，LinkedHashSet底层维护的是一个LinkedHashMap。

HashSet TreeSet LinkedHashSet_1（Ctrl+super进入LinkedHashSet_2） LinkedHashSet_2

  但是JDK8中没有把ConcurrentHashMap的keys抽取成Set（其他版本小码农不清楚）。不过Collections.newSetFromMap(Map<E, Boolean> map)可以由Map构建Set。例子如下。

newSetFromMap的小例子

  Map和Set的解析到这就结束了，面试之前小码农还会再分析一次源码的，带时候会更详细的和大家一起分析。