版本：JDK1.8
针对put方法展开
0、两者底层数据结构
数组+链表+红黑树(JDK1.8新增)
0.1、数组
特点：查改快，增删慢。
查改快：通过数组下标定位
增删慢：增删会引起元素的移动

0.2、链表
特点：增删快，查改慢。
增删快：节点之间的链接断开，进行元素的增删，之后在链接上即可
查改慢：需要从链表头开始查。最大时间复杂度：T(m) = O(n);常数时间

0.3、红黑树
特点：接近于于平衡的二叉树。
相对于链表降低时间复杂度，T(n) = O(logn);对数时间,由于计算机使用二进制的记数系统，对数常常以2为底

引入红黑树的原因
1、解决发生哈希碰撞后，链表过长而导致索引效率的问题
2、利用红黑树增删改查快速的特点
3、时间复杂度有O(n)降为O(logn)

0.4、扩展
算法复杂度
算法复杂度分为时间复杂度和空间复杂度
    时间复杂度是指执行这个算法所需要的计算工作量；
    空间复杂度是指执行这个算法所需要的内存空间

1、两者整体区别
HashMap是线程不安全的，ConcurrentHashMap是线程安全的
HashMap的key和value可以为null，ConcurrentHashMap的key和value不可以为null

2、数组初始化
2.1、HashMap(线程不安全)
if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
 
//DEFAULT_INITIAL_CAPACITY = 1 << 4;
//DEFAULT_LOAD_FACTOR = 0.75f;
newCap = DEFAULT_INITIAL_CAPACITY;		
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

默认数组初始化长度：16
加载因子：0.75f
默认扩容阀值：12
2.2、ConcurrentHashMap(线程安全)
 if ((sc = sizeCtl) < 0)
     Thread.yield();
 else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
     int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
     Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
 }

默认数组初始化长度：16
加载因子：0.75f
默认扩容阀值：12
线程安全体现
对数组初始化使用了CAS无锁化的方式保证了线程安全
CAS：Compare And Swap：比较并交换

数组初始化比较了内存中Node数组长度的值和当前线程中Node数组长度的值，默认都是0。
CAS操作将内存中数组的长度改为了-1，之后其他线程进来就会让出CPU执行权
然后当前线程就进行数组初始化操作

3、put操作和get操作
3.1、put操作之前
3.1.1、对key进行哈希散列计算
HashMap
hash(key)；
=================
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
=================
if ((p = tab[i = (n - 1) & hash]) == null)

ConcurrentHashMap
int hash = spread(key.hashCode());
===================
static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;
}
===================
f = tabAt(tab, i = (n - 1) & hash)

哈希散列计算描述
进行哈希散列计算主要是为了确定元素的索引
为了保证数组的空间能得到充分的利用，需要考虑分散性、均匀性
两者底层hash算法会将key的hashCode值与数组的长度换算成32位二进制形式做位与运算

有一个前提和两个关键点
一个提前：
	数组长度必须是2的次幂数
两个关键
	1、得到一个整型数：key.hashCode()
    	该整型数很关键，关系到数组索引的分散性、均匀性，所以该整型数的最终运算结果要尽可能的不一样
    	
	2、控制这个整型数在0~length-1之间：key.hashCode()%length
    	将%运算换成&运算，key.hashCode()%length = key.hashCode()&(length - 1)
    	用位与运算替代取模的运算，位与效率更高
    	整型数最终会转化为32位二进制数形式的&（length-1）最终会得到一个索引index，确定Node节点存放的位置，10进制表示的范围 0~(length - 1)
    	索引index是由整型数和(length - 1)两个操作数决定的，所以最终还是取决于hash函数的结果

索引index还是要尽可能保证一样
   在同一个数组中，length-1是固定的，所以索引index结果最终还是取决于整型数处理的最终结果，准确来说取决整型数的32位二进制数最后几位，因为高位不参与运算
   即使整型数不同，但是二进制数形式表示的时候低位可能相同，参与运算结果还是有可能一样，因为只是低位参与运算
   所以要保证最后几位不一样即可，因此用高16位和低16位进行异或(^)运算，重复的可能性减少，这样就更加保证了index不一样

3.2、HashMap(线程不安全)
put元素操作
索引处是否有值
没有值：直接put
有值：
	key相同：直接替换，返回旧值
	key不同：形成链表或红黑树
		链表：遍历链表，判断插入后链表长度是否达到8，JDK1.8之前是头插法
			没有达到，尾插法。
			达到，转为红黑树处理，判断哈希表中的容量(数组长度)是否达到最小树形化容量阈值64
				当哈希表中的容量 > 该值时，才允许树形化链表 （即 将链表 转换成红黑树）
				没有达到，进行数组扩容
				达到，转红黑树
		红黑树：直接put

get元素操作
public V get(Object key) {
    Node<K,V> e;
    //先通过hash(key)找到hash值，然后调用getNode(hash,key)找到节点
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //通过(n - 1) & hash找到数组对应位置上的第一个node
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //如果这个node刚好key值相同，直接返回
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        //如果不相同就再往下找
        if ((e = first.next) != null) {
            //如果是treeNode，就遍历红黑树找到对应node，最终会通过find方法
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            //如果是链表，遍历链表找到对应node
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    //没有找到返回null
    return null;
}

3.2、ConcurrentHashMap(线程安全)
put元素操作
索引处是否有值
没有值：直接put(CAS无锁化机制保证线程安全)
有值：使用同步代码块保证线程安全，将链表头或者红黑树根节点元素作为锁
	key相同：直接替换，返回旧值
	key不同：形成链表或红黑树
		链表：遍历链表，判断插入后链表长度是否达到8（不在此同步锁），JDK1.8之前是头插法
			没有达到，尾插法。
			达到，转为红黑树处理(另一同步锁)，判断哈希表中的容量(数组长度)是否达到最小树形化容量阈值64
				当哈希表中的容量 > 该值时，才允许树形化链表 （即 将链表 转换成红黑树）
				没有达到，进行数组扩容
				达到，转红黑树
		红黑树：直接put

get元素操作
public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    //先通过hash(key)找到hash值
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        //如果这个node刚好key值相同，直接返回
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        //如果不相同就再往下找
        else if (eh < 0)
            //如果是treeNode，通过find方法中遍历红黑树找到对应node
            return (p = e.find(h, key)) != null ? p.val : null;
        //如果是链表，遍历链表找到对应node
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    //没有找到返回null
    return null;
}

4、扩容
4.1、前置条件
每次put元素都会有判断，在每次put如果数组索引位置被使用都会有++操作，初始值是0，在数组初始化时会有一个扩容阀值：数组长度X加载因子

4.2、扩容条件
1、数组table被使用的容量超过扩容阀值
2、红黑树扩容：哈希表中的容量小于最小树形化容量阈值64(引起链表过长的根本原因是数组过短)

4.3、怎么扩容
长度和扩容阀值左移1位,变为原来容量的双倍

4.4、扩容与元素迁移
4.4.1、HashMap(线程不安全)
扩容说明：resize()方法

前置：判断扩容前哈希表是否为空，不为空则开始遍历数组
条件：数组索引处有元素
元素迁移
	会重新计算hash值，得到新数组的index
	1、没有链表或红黑树
		直接搬运
	2、有链表节点
		遍历搬运
	3、有红黑树节点
		树形拆分搬运

4.4.2、ConcurrentHashMap(线程安全)
扩容说明：
在put元素的时候会进行头节点的hash值判断，如果等于MOVEN(也就是-1)，就让当前线程帮助扩容(没有加锁，因为还需要其他线程帮助迁移元素，但是其他线程要能监测到当前线程正在扩容)，在扩容的时候，会将这个hash值置为-1，相当于让其他线程监听到当前线程正在扩容，就去帮助当前线程进行扩容，会暂停线程put元素操作，等扩容完以后才能再put元素到新数组

addCount()判断是否需要扩容
transfer()方法
	在此方法中，每个线程会领取任务
	stride = MIN_TRANSFER_STRIDE;//最小16，
	//如果数组长度只有16，一个线程即可，多个的话下一个线程进来会领取自己对应的任务

搬运元素和HashMap一样，只是是用来同步代码块

前置：判断扩容前哈希表是否为空，不为空则开始遍历数组
条件：数组索引处有元素
元素迁移（同步代码块）
	会重新计算hash值，得到新数组的index
	1、没有链表或红黑树
		直接搬运
	2、有链表节点
		遍历搬运
	3、有红黑树节点
		树形拆分搬运

5、问题
1、为什么要对key进行hash计算？
为了保证数组的空间能得到充分的利用，需要考虑分散性、均匀性

2、为什么数组初始化的长度要是2的指数次幂？
因为底层hash算法仍然要换算成二进制运算:hash%length=hash&(length-1)
如果不是2的次幂，就不等价hash%length!=hash&(length-1)
提升效率

即使传入非2的指数次幂的容量，在数组初始化时，也会将这个容量长度转换成最接近这个容量的2的n次方的数

3、加载因子为什么是0.75f？
如果设置为1，最大化利用空间，但是没办法达到理想状态,会导致链表过长或者红黑树时间复杂度增加
如果设置为0.5，查询效率高，节省时间，但是太浪费空间
空间利用率与时间复杂度上去择中，所以选择0.75

4、ConcurrentHashMap在put元素的时候有值情况下为什么不使用CAS无锁化机制保证线程安全?
因为有可能put很频繁，用CAS每次都要和内存中的作比较，非常不好。使用同步代码块，也就是数组上一个元素有一把锁，锁粒度变小，性能提高。

5、链表长度为什么阀值是8？
泊松分布算法