一、HashMap的宏观实现
1、HashMap数据结构:
HashMap采用 数组 + 链表 的方式来实现数据的存储。为什么使用这种方式呢？链表什么时候产生呢？
首先HashMap主要还是用数组来存储元素的。它通过key的hash来计算元素应该放在数组中的哪个位置。如果有两个key的hash都一样，该怎么处理呢？这时候会去判断这两个key是否相等，如果相等，那就直接用新的value覆盖旧的value；如果这两个key不相等，那么就连接在第一个key的后面，用头插法形成链表(JDK1.8开始用尾插法)。由此链表就诞生了。
JDK1.8开始，又对HashMap进行了优化。我们知道链表读取数据不方便，所以为了避免链表太长，又加入了红黑树结构。当链表长度达到阈值时，就会将链表转成红黑树。
所以宏观的来说，JDK1.8开始，HashMap是由(数组 + 链表 + 红黑树)实现的。首先是用hash去判断元素应该放到数组中的哪个位置，如果该位置已有元素，就判断这两个元素的key是否相同，相同就覆盖，不同就生成链表，接在后面。当链表达到一定长度时，就转成红黑树。同时数组的元素个数达到一定值时，就会进行扩容。扩容之后再将数据转移到新的数组。
二、HashMap实现细节
1、用什么存储元素？
根据上面的宏观描述，可以知道，我们需要一个Node类，里面有四个属性，分别是 key、value、hash、next。其中next是Node类型，表示下一个节点，用于生成链表。同时需要一个Node[ ] 数组，用来存储每个节点。如下代码所示：
// 这是源码中的节点内部类。 static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; ... } // 源码中的节点数组 transient Node<K,V>[] table;
2、数组如何初始化？
从上面我们可以看到，这个数组并没有初始化，那么当我们put元素的时候，这个数组是如何初始化的呢？
通过源码可以发现，put方法里面调用了一个putVal方法，在putVal方法中，首先判断数组长度是不是没有初始化，如果是，就调用resize方法进行初始化。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; ... }
接下来看看resize方法是怎么初始化数组的。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
这个是数组初始化默认的大小。
... Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; ... return newTab;
在这个方法中，其他的先不用看，就看这几行代码，其中newCap的值就是与上面数组默认初始化大小值一样，也就是16。也就是说，使用HashMap的时候，首先会初始化一个长度为16的数组，用来存储元素。
3、如何将元素放入数组？
初始化了一个长度为16的数组，那么索引就是 0 ~ 15，当put元素的时候，如何知晓元素是放入哪个位置呢？Node内部类的hash属性就起作用了。首先来看看这个hash属性是怎么来的。
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
在HasnMap中有一个hash方法，该方法返回key的hashCode值的高16与低16位进行异或运算(科普一下：异或运算，将运算数转成二进制，1^1=0，1^0=1，0^0=0 ，0^1=1，也就是说，相等为0，不等为1；与运算，将运算数转成二进制，1&1=1，1&0=0，0&1=0，0&0=0；或运算，将运算数转成二进制，1|1=1，1|0=1，0|1=1，0|0=0)，该值就是hash。为什么要这样计算hash的值，而不直接使用hashCode方法计算的值？hashCode方法返回值是一个32位的二进制数，等下在计算元素索引的时候，这32位并没有都参与运算，这样的话，两个key计算出来的索引一致的概率就更大，所以要让这32位充分利用起来，都参与计算，所以先用hashCode值的高16位与低16位进行异或运算。那么为什么是异或，而不是其他运算呢？从上面括号内的说明可以知道，只有异或运算，得到1和0的概率都是0.5。为了不影响计算结果，所以选择了异或。
有了hash后，如何计算出索引？
... if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); ... }
在putVal方法中，有这样一段代码。索引 i 就是 hash 和 n ( n是数组长度 - 1) 进行与运算得来的。为什么这样算呢？上面说了，数组默认初始化长度为16，二进制就是 10000，减一后结果就是 01111。再用 hash 和 01111 进行与运算，其结果一定是在 0 到 01111 这个范围的，也就是 0 到 15 之间。而数组索引也是 0 到 15，这样便达到了目的。计算出来的结果是 n，那就放入数组索引为 n 的位置。
问题来了，因为数组默认初始化长度是16，是2的n次幂。(length - 1) 就是奇数，最后一位是1。这样就保证了 hash & (length - 1) 的计算结果可能为奇数也可能为偶数，保证了散列的均匀性。
4、如果我们给的初始化大小不是2的n次幂怎么办？
HashMap还有个构造方法，我们可以自己传入一个数组初始化容量。如下：
HashMap<Integer,String> map = new HashMap<>(20);
根据上面的分析，我们知道数组的大小一定得是2的n次幂，才能保证散列均匀分布。如果我传入不是2的n次幂，比如是20，那么如何处理？
通过源码我们可以发现如下的一个方法：
static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }
这个方法的作用就是，如果用户传入的不是2的n次幂，那么就会return一个大于和用户传入的数最接近的2的n次幂的数。比如传入20，那么实际上数组的大小将会是32。
5、数组何时进行扩容？如何扩容？
resize方法不仅是用来初始化的，也是用来扩容的。那么什么时候进行扩容？是数组中的元素满了才扩容的吗？当然不是。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
在源码中有这么一个常量，暂且称作扩容因子。当数组中元素个数达到了数组长度的四分之三的时候，就会进行扩容。上面也说了，数组长度必须是2的n次幂，所以扩容就会扩成两倍。原来长度为16，当数组中有12个元素了，就会进行扩容，扩成32。那么旧数组的数据如何移动到新数组呢？有三种情况：
- 如果是单个元素，那就用 hash & (newLength - 1 )；
- 如果是链表，那么就用看 hash & oldLength 的计算结果是否为0(oldLength表示旧数组的容量)，如果为0，放在原位置，如果不为0，放在 (原来的index + 旧数组容量) 的位置。
- 如果是红黑树，那么将树打散，根据 hash & (newLength - 1 ) 重新分配位置。
所以总结起来就是，要么在原来的位置，要么在原来索引加上原数组容量的位置。
6、什么时候会生成链表？
上面说了HashMap通过计算 hash & (数组长度 - 1 ) 的值来确定元素放入数组中哪个位置。当两个元素计算出来的值一样时，如何处理？那么就会继续通过equals方法方法判断这两个元素的key是否一样，如果一样，那么新的value就会覆盖旧的value；如果不一样，就会生成链表。在jdk 1.7的时候，用头插法生成链表，jdk1.8开始，用尾插法生成链表。
7、为什么要有红黑树？什么时候生成红黑树？
上面说了什么时候生成链表，我们知道链表读取数据很慢，如果链表太长，会导致读取性能不好。所以就出现了红黑树。在源码中，有如下常量：
static final int TREEIFY_THRESHOLD = 8;
也就是说，当链表的长度达到了8，就会将链表转成红黑树，以提高读取效率。还有一个常量：
static final int UNTREEIFY_THRESHOLD = 6;
也就是说，当树中元素个数少于6个时，那就将树变回链表。
红黑树的平均查找长度为log(n)，链表的平均查找长度为 n/2。当元素个数为8时，使用链表平均查找长度为4，而使用红黑树的话平均查找长度为3，所以有必要转成红黑树。当元素个数小于等于6时，用链表平均查找长度是3，速度已经很快了，所以没必要转红黑树。
小结：往HashMap中put元素主要分为以下几个步骤：
- hash(key)，计算key的hash，用key的hashCode值的高16位和低16位进行异或运算；
- 调用resize方法初始化数组，默认初始化大小为 16 ，如果自定义的初始化大小x不是2的n次幂，就会转成比x大的最接近x的2的n次幂；
- hash和数组长度减一的值进行与运算，判断元素在数组中的存储位置，如果这个位置没有其他key，直接存入该位置，如果有其他的key，那么又有三种情况：
--- ：如果key相等，直接替换
--- ：如果key不等，生成链表
--- ：如果链表长度达到 8 了，那就转成红黑树 - 当数组中元素个数达到容量的 0.75 时，调用resize方法将容量扩为当前的两倍。
- 扩容后数据的转移有两种情况：
--- ：如果是单个元素或者是红黑树，根据 hash ^ （newLength - 1）的方式存储；
---： 如果是链表，判断 hash ^ oldLength 的值是否为0，如果是，放在原位置，不为0，放在 (原index + 旧数组容量) 的位置。
三、ConcurrentHashMap
1、为什么要有ConcurrentHashMap？
看了HashMap的源码之后，可以发现HashMap并不是同步的。如果在多线程环境中同时对一个HashMap进行读写操作，肯定是会出问题的。那么如何保证在多线程中的安全问题呢？加锁！没错，最熟悉的就是 synchronized 了。只要在HashMap的每个方法中都加上 synchronized 关键字，就安全了。确实可以，HashTable就是这样做的，所以它被淘汰了，因为这样性能很低。接下来就该ConcurrentHashMap上场表演了。
2、ConcurrentHashMap如何保证线程安全？
说这个问题之前，先回到HashMap的小结中的5个过程，看看5个过程哪几个过程在多线程环境中可能出现线程安全问题。
- hash(key)，这个过程不管多少个线程同时操作，计算出的hash都是一样的，不会有线程安全问题。所以ConcurrentHashMap中这个过程没做处理。
- 初始化数组，这个过程肯定会有问题。比如一个线程要初始化容量为16，另一个线程要初始化容量为32，那么怎么办？ConcurrentHashMap采用了CAS算法来保证线程的安全性。当有线程初始化map了，其他线程就yield，礼让一下。初始化数组的 initTable 方法如下：
private final Node<K,V>[] initTable() { Node<K,V>[] tab; int sc; while ((tab = table) == null || tab.length == 0) { if ((sc = sizeCtl) < 0) Thread.yield(); // lost initialization race; just spin else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { try { if ((tab = table) == null || tab.length == 0) { int n = (sc > 0) ? sc : DEFAULT_CAPACITY; @SuppressWarnings("unchecked") Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; table = tab = nt; sc = n - (n >>> 2); } } finally { sizeCtl = sc; } break; } } return tab; }
关于CAS算法的工作原理，它如何保证线程安全，以后再写个文章详细说明，此处不多说。
- 3、 存放元素，这个过程肯定也会有线程安全问题。
if (tab == null || (n = tab.length) == 0) tab = initTable(); else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // no lock when adding to empty bin }
先看这段代码，首先判断数组是否为空，为空，那么就调用initTable进行初始化。如果不为空，并且要插入的位置没有元素，就执行casTabAt方法。下面来看一个这个方法：
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v) { return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v); }
这个方法也是使用了CAS算法，也就是说，当要插入的位置没有其他key时，也是用CAS保证线程的安全性的。如果要插入的位置有key存在呢，看接下来的代码：
else { synchronized (f) { ...... } }
如果要插入的位置有key了，那么要判断是替换还是生成链表还是生成红黑树，情况比较复杂。所以直接用synchronized代码块。锁对象是当前操作的node节点，缩小了锁的粒度也就是说，其他线程只是不能对当前节点进行操作，但可以对其他节点进行操作。
- 4、扩容和转移数据：这个过程也会有线程安全问题。只能有一个线程进行扩容，当一个线程进行扩容的时候，其他线程也别闲着，其他线程就帮忙将旧数组的数据转移到新数组。扩容的addCount方法也是通过CAS来保证线程安全的。在putVal方法中，好友一个判断条件如下：
else if ((fh = f.hash) == MOVED) // -1 tab = helpTransfer(tab, f);
当那个值等于-1时，那么就调用helpTransfer方法去帮忙进行数据的转移。
小结：ConcurrentHashMap在put元素时主要逻辑如下：
if (tab == null || (n = tab.length) == 0) // 数组为空 tab = initTable(); // 初始化，CAS保证线程安全 else if ((f = tabAt(tab, i = (n - 1) & h)) == null) { // 要插入的位置key为null // casTabAt 方法用CAS保证线程安全 if (casTabAt(tab, i, null, new Node<K,V>(h, key, value, null))) { delta = 1; val = value; break; } } else if ((fh = f.hash) == MOVED) // f.hash == MOVED(-1) tab = helpTransfer(tab, f); // 帮忙转移元素到扩容后的数组，CAS保证安全性 else { // 要插入的位置key不为null synchronized (f) { // 同步代码块保证线程安全 ...... } } if (delta != 0) addCount((long)delta, binCount); // 扩容，CAS保证安全性
