承接上篇《Java深入研究Collection汇合框架》文章中的HashMap、ConcurrentHashMap源码剖析,在Java中罕用的四个实现Map接口的类，别离是HashMap、TreeMap、LinkedHashMap以及继承自Dictionary抽象类的Hashtable，上面简略概述下各实现类的特点 :
HashMap
依据键的hashcode存储数据，容许null键/值(null键只容许一条，value能够有多条null)，非synchronized、元素无序，程序也可能随时扭转，底层基于链表+红黑树实现【JDK1.8】
TreeMap
实现SortedMap接口，能够依据键排序，默认按键值升序排序，也能够指定排序的比拟器，在应用时key必须实现Comparable接口，TreeMap在Iterator遍历是排过序的
LinkedHashMap
属于HashMap的一个子类，保留了记录的插入程序，在用Iterator遍历LinkedHashMap时，先失去的记录必定是先插入的，也能够在结构时带参数，依照拜访秩序排序
Hashtable
罕用性能跟HashMap相似，不反对null键/值,synchronized线程平安，Hashtable默认的初始大小为11，之后每次裁减，容量变为原来的2n+1.HashMap默认的初始化大小为16.之后每次裁减，容量变为原来的2倍，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁
HashMap重要的常量定义
DEFAULT_INITIAL_CAPACITY =16 默认容量MAXIMUM_CAPACITY =1 << 30 最大容量DEFAULT_LOAD_FACTOR = 0.75f 默认负载因子TREEIFY_THRESHOLD=8 链表转换红黑树的阀值UNTREEIFY_THRESHOLD=6 红黑树转换链表的阀值MIN_TREEIFY_CAPACITY=64 桶中bin最小hash容量，如果大于这个值会进行resize扩容操作，此值至多是TREEIFY_THRESHOLD的4倍HashMap构造函数
首先看初始化容量、负载因子的有参函数源码
public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }惯例的边界判断、赋值操作，通过tableSizeFor办法计算初始容量
HashMap put办法源码剖析
办法调用 public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } 传入key的hash计算 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } 理论调用办法 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //部分node节点tab Node<K,V>[] tab; Node<K,V> p; int n, i; //将初始化的table赋值给tab并判null，如果为空则进行tab初始化 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //依据hash计算tab[i]地位，判断如果为空则调用newNode()存储新的node<K,V>中 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; //依据hash值和equals判断key，如果key雷同就把老的node赋值给变量e if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //key不同，判断是否时红黑树，如果是则调用putTreeVal()放在树中 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { //循环链表 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { //没有下一个元素，则把以后元素传入newNode()作为下一个元素 p.next = newNode(hash, key, value, null); //链表长度超过阈值TREEIFY_THRESHOLD=8 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash);//转换成红黑树 break; } //判断key雷同则赋值替换 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //判断value是否替换 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold)//判断扩容阈值 resize();//扩容办法 afterNodeInsertion(evict); return null; }resize实现
当put时，如果bucke占用水平曾经超过了DEFAULT_LOAD_FACTOR参数初始比例，就把bucket裁减为2倍，之后从新计算index，再把节点放到新的bucket中，源代码阐明如下Initializes or doubles table size. If null, allocates in accord with initial capacity target held in field threshold. Otherwise, because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table
实现办法在【JDK1.7】和【JDK1.8】中有差别(1.8引入红黑树)，感兴趣能够钻研JDK源码对reszie()的实现
HashMap get办法源码剖析
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } //hash值同put操作 final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //判断tab节点是否为空，依据hash算出下标 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { //在第一个node中查找 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; //如果有下一个元素 if ((e = first.next) != null) { //如果是树，调用getTreeNode()在红黑树中查找 if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { //循环链表 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }HashMap put、get办法思路总结
put办法大抵思路
- 依据键值key做hash计算，失去插入数组下标，如果tab[i]为null，间接newNode插入新节点
- 如果tab[i]不为null，判断tab[i]首个元素和key是否雷同，雷同就把老元素赋值给局部变量
- 如果比拟的key不同，判断是否为TreeNode(红黑树),如果是，调用putTreeVal()插入树中
- 如果不是TreeNode,对链表做遍历，链表长度超过阈值TREEIFY_THRESHOLD=8转换成红黑树
get办法大抵思路
- 判断tab节点是否为空，依据hash算出下标
- 在第一个node节点中查找，如果有间接return first
- 如果没有，判断是否有下一个元素，如果有判断是否为TreeNode,如果是则在树中查找
- 如果不是，循环链表查找
equals()和hashCode()的作用
通过对key的hashCode()进行hashing，并计算下标( n-1 & hash)，从而取得buckets的地位。如果比拟的key雷同，则利用key.equals()办法去链表或树中去查找对应的节点
<br/>
ConcurrentHashMap实现原理
ConcurrentHashMap在Java 8中勾销了Segment分段锁的数据结构，采纳数组+链表+红黑树的数据结构，而对于锁的粒度，调整为对每个数组元素加锁(Node节点)，简化定位节点的hash算法，这样带来的弊病是hash碰撞会增大，因而在链表节点数量大于8时，会将链表转化为红黑树进行存储。这样一来，查问的工夫复杂度就会由原先的O(n)变为O(logN)
对于CAS算法
CAS的全称叫"Compare And Swap"，也就是比拟并替换，应用时次要波及到三个操作数，内存值V、预期值A、新值B，如果在执行时发现内存值V与预期值A相匹配，那么他会将内存值V更新为新值B，相同处理器就不会执行任何操作
外围属性
//用于table[]的初始化和扩容操作，-1示意正在初始化，-N示意有N个线程正在扩容，非正数时，示意初始化table[]的大小，曾经初始化则示意扩容阈值，默认为table[]容量的0.75倍 private transient volatile int sizeCtl; //示意默认的并发级别，也就是table[]的默认大小 private static finalint DEFAULT_CONCURRENCY_LEVEL = 16; //默认的负载因子 private static final float LOAD_FACTOR = 0.75f; //链表转红黑树的阀值 static final int TREEIFY_THRESHOLD = 8; //红黑树转链表的阀值， static final int UNTREEIFY_THRESHOLD = 6; //哈希表的最小树形化容量 static final int MIN_TREEIFY_CAPACITY = 64;构造函数
public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) { if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0) throw new IllegalArgumentException(); if (initialCapacity < concurrencyLevel) // Use at least as many bins initialCapacity = concurrencyLevel; // as estimated threads long size = (long)(1.0 + (long)initialCapacity / loadFactor); int cap = (size >= (long)MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : tableSizeFor((int)size); this.sizeCtl = cap; //次要是初始化map容量size、concurrencyLevel并发级别 }put操作
//惯例put入口 public V put(K key, V value) { return putVal(key, value, false); } final V putVal(K key, V value, boolean onlyIfAbsent) { //不容许空键空值 if (key == null || value == null) throw new NullPointerException(); int hash = spread(key.hashCode());//计算key hash int binCount = 0; for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; if (tab == null || (n = tab.length) == 0) tab = initTable();//惯例初始化tab[] //依据hash值与运算确认下标并将节点赋值给f，而后判null else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { //如果为空，采纳CAS算法将新值插入Node节点 if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // no lock when adding to empty bin } //hash值==-1，阐明正在扩容 else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f);//扩容后返回最新tab[] else { V oldVal = null; synchronized (f) {//获取数组同步锁， if (tabAt(tab, i) == f) { if (fh >= 0) {//hash大于0，阐明是链表 binCount = 1; for (Node<K,V> e = f;; ++binCount) {//链表遍历 K ek; if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break;//key雷同，进行value替换，退出循环 } Node<K,V> pred = e; if ((e = e.next) == null) { //创立新的节点插入链表尾部 pred.next = new Node<K,V>(hash, key, value, null); break; } } } else if (f instanceof TreeBin) {//如果是红黑树 Node<K,V> p; binCount = 2; //// 调用红黑树的插值办法插入新节点 if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } else if (f instanceof ReservationNode)//空节点，占位符 throw new IllegalStateException("Recursive update"); } } if (binCount != 0) { //链表转换红黑树阈值判断 if (binCount >= TREEIFY_THRESHOLD) //与HashMap类中转换红黑树有区别，当hash表长度小于MIN_TREEIFY_CAPACITY属性值时尝试扩容操作，相同进行树形化 treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } } addCount(1L, binCount); return null; }ConcurrentHashMap的put()操作大抵流程
- 初始化map容量size、concurrencyLevel并发级别
- 对键、值非null判断，计算hash值，判断table[]是否创立，没有就初始化
- 如果table[i]为null，采纳CAS算法将新值插入Node节点
- 如果不为null,判断hash值是否为-1，如果是则调用helpTransfer()扩容
- 如果hash值不为-1，就在链表尾部或者和红黑树中插入节点
- 最初对链表转红黑树阈值做判断，当hash表长度小于MIN_TREEIFY_CAPACITY属性值时尝试扩容操作，相同进行树形化
get操作
public V get(Object key) { Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek; int h = spread(key.hashCode());//计算key hash //判断table[]是否为null,依据下标确认table[i]节点并做非null束缚 if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) { //比拟头部元素是否雷同，雷同则间接返回该键对应的值 if ((eh = e.hash) == h) { if ((ek = e.key) == key || (ek != null && key.equals(ek))) return e.val; } //如果头结点的 hash 小于 0，阐明正在扩容，或者该地位是红黑树 else if (eh < 0) //e.find可比照查看ForwardingNode类的find()、TreeBin类的find()源码 return (p = e.find(h, key)) != null ? p.val : null; //遍历链表 while ((e = e.next) != null) { if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) return e.val; } } return null; }ConcurrentHashMap的get()操作大抵流程(不加锁)
- 计算key的hash值，判断table[]是否为null，同时依据下标判断table[i]是否为null
- 如果table[i]则比拟链表头部元素是否雷同，如果是间接返回该键地位所对应的值
- 如果hash不雷同，判断是否是红黑树或是正在扩容操作，如果是则在树中查找
- 如果不是红黑树或是正在扩容操作，则遍历链表查找
Java8对ConcurrentHashMap实现改良
- 不采纳segment而采纳node，锁住node来实现减小锁粒度，退出红黑树机制
- 换回Synchronized关键字，替换ReentrantLock分段锁
- 设计了MOVED状态，容许多线程进行帮忙扩容操作
- 应用CAS操作来确保node的一些操作的原子性，这种形式代替了锁
- 采纳sizeCtl的不同值来代表不同含意，起到了管制的作用