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 keySet()	返回此映射中包含的键的 Set 视图
Collection values()	返回此映射中包含的值的 Collection 视图
Set

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

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

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

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