1 HashMap数据结构
目标：
HashMap 概念、数据结构回顾（JDK8和JDK7） & 为什么1.8使用红黑树？
概念：
HashMap 是一个利用散列表（哈希表）原理来存储元素的集合，是根据Key value而直接进行访问的数
据结构
在 JDK1.7 中，HashMap 是由 数组+链表构成的。
在 JDK1.8 中，HashMap 是由 数组+链表+红黑树构成
回顾： 数组、链表（优势和劣势）
数组: 优势：数组是连续的内存，查询快（o1） 劣势：插入删除O(N)
链表: 优势：不是连续的内存，随便插入（前、中间、尾部） 插入O(1) 劣势：查询慢O(N)
思考？
为什么是JDK1.8 是数组+链表+红黑树？
HashMap变化历程
1.7的数据结构：链表变长，效率低了！
1.8的数据结构：
数组+链表+红黑树
链表–红黑（链长度>8、数组长度大于64）
总结：
JDK1.8使用红黑树，其实就是为了提高查询效率
因为，1.7的时候使用的数组+链表，如果链表太长，查询的时间复杂度直接上升到了O(N)
2 HashMap继承体系
目标：梳理map的继承关系
总结
HashMap已经继承了AbstractMap而AbstractMap类实现了Map接口那为什么HashMap还要在实现Map接口呢？
据 java 集合框架的创始人Josh Bloch描述，这样的写法是一个失误。
在java集合框架中，类似这样的写法很多，最开始写java集合框架的时候，他认为这样写，在某些
地方可能是有价值的，直到他意识到错了。显然的，JDK的维护者，后来不认为这个小小的失误值
得去修改，所以就这样存在下来
Cloneable 空接口，表示可以克隆
Serializable 序列化
AbstractMap 提供Map实现接口
3 HashMap源码深度剖析
目标：
通过阅读HashMap（since1.2）源码，我们可以知道以下几个问题在源码是如何解决的
（1）HashMap的底层数据结构是什么？
（2）HashMap中增删改查操作的底部实现原理是什么？
（3）HashMap是如何实现扩容的？
（4）HashMap是如何解决hash冲突的？
（5）HashMap为什么是非线程安全的？
测试代码如下
package com.mmap; import java.util.ArrayList; import java.util.ConcurrentModificationException; import java.util.HashMap; import java.util.List; import java.util.concurrent.ConcurrentHashMap; public class MMapTest { public static void main(String[] args) { HashMap<Integer, String> m = new HashMap<Integer, String>();//尾插 //断点跟踪put m.put(1, "001"); m.put(1, "002"); m.put(17, "003");//使用17可hash冲突（存储位置相同） //断点跟踪get System.out.println(m.get(1));//返回002（数组查找） System.out.println(m.get(17));//返回003（链表查找） //断点跟踪remove m.remove(1); } }
下面源码看到16是默认容量1和17数组长度取余得到的值相同,所以会产生hash冲突
3.1 成员变量与内部类
目标：理解map的成员变量代表的意思
两大部分
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //16，默认容量：左位移4位，即2的4次幂 static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量：即2的30次幂 static final float DEFAULT_LOAD_FACTOR = 0.75f;//负载因子：扩容使用，统计学计算出的最合理的 static final int TREEIFY_THRESHOLD = 8;//链表转红黑树阈值 static final int UNTREEIFY_THRESHOLD = 6;//当链表的值小<6, 红黑树转链表 ..略 transient Node<K,V>[] table;//HashMap中的数组,中间状态数据;不参与序列化(重点) transient Set<Map.Entry<K,V>> entrySet;//用来存放缓存,中间状态数据; transient int size;//size为HashMap中K-V的实时数量（重点）,中间状态数据; transient int modCount;//用来记录HashMap的修改次数 int threshold;//扩容临界点；(capacity * loadFactor)（重点） final float loadFactor;//负载因子 DEFAULT_LOAD_FACTOR = 0.75f赋值
1 << 4 表示1左移四位 ，推理公式
简单记忆：
如果 1 << 4 、1 << 5、1 << 20
等于
2^4、2^5、2^20
左移其实就是 X（对应1）乘以2的N次方
注意，前导（第一位）为1 不适用
下面会详细讲
静态内部类（1.8前是Entry）
static class Node<K,V> implements Map.Entry<K,V> {//数组（哈希桶）：1.8前是Entry final int hash;//扰动后的hash final K key;//map的key V value;//map的value Node<K,V> next;//下个节点 Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next;//链表下一个 ....略 transient Node<K,V>[] table;//HashMap中的数组,不参与序列化(重点) transient int size;//size为HashMap中K-V的实时数量（重点） transient int modCount;//用来记录HashMap的修改次数 int threshold;//扩容临界点；(capacity * loadFactor)（重点） final float loadFactor;//负载因子 DEFAULT_LOAD_FACTOR = 0.75f赋值 ....略
总结：
1、上面的成员变量大体有个印象，后面源码分析我们会用到
2、位运算计算比较麻烦，可以按照上面的快速记忆计算
3.2 HashMap构造器
目标：学习下面的三个构造器，它们都干了哪些事情？
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // 负载因子DEFAULT_LOAD_FACTOR =0.75f }
public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } 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); }
总结：
可以发现上面是三个构造器都么有在内存上创建对象，只是针对容量和负载因子做了大量的判断和赋值
3.3 HashMap插入方法
目标：图解+代码+断点分析put源码
插入流程如下
插入主方法
当我们调用put方法添加元素时，实际是调用了其内部的putVal方法，第一个参数需要对key求hash值，
为了减少hash碰撞
public V put(K key, V value) { return putVal(hash(key), key, value, false, true);//调用Map的putVal方法 }
生成hash，干扰（扰动）函数
为了防止一些实现比较差的 hashCode() 方法，减少碰撞，尽可能使元素更散列地存储
static final int hash(Object key) {//干扰（扰动）函数；通过key计算hash值，仅仅是 hash值，不是存储位置 int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//hash后对右 16（空位补0）后进行异或，key为null，表示HashMap是支持Key为空的， }
核心逻辑
在resize时会丢数据,线程不安全的,1.7叫做transfer函数功能相同
HashMap
1.在JDK1.7中，当并发执⾏扩容操作时会造成环形链和数据丢失的情况。
2.在JDK1.8中，在并发执⾏put操作时会发⽣数据覆盖就是丢数据的情况。
这是jdk1.8中HashMap中put操作的主函数， 注意代码，如果没有hash碰撞则会直接插入元素。如果线程A和线程B同时进行put操作，刚好这两条不同的数据hash值一样，并且该位置数据为null，所以这线程A、B都会进入这行代码中。假设一种情况，线程A进入后还未进行数据插入时挂起，而线程B正常执行，从而正常插入数据，然后线程A获取CPU时间片，此时线程A不用再进行hash判断了，问题出现：线程A会把线程B插入的数据给覆盖，发生线程不安全。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {//onlyIfAbsent：true不更改现有值；evict：false表 示table为创建状态 Node<K,V>[] tab; Node<K,V> p; int n, i;//临时变量 if ((tab = table) == null || (n = tab.length) == 0)//数组是否null或者==0， 第1次put为空 n = (tab = resize()).length;//初始化数组(or扩容)！！！！！！！！！！！！！ if ((p = tab[i = (n - 1) & hash]) == null)//寻址：(n - 1) & hash重要，16-1 按位与hash，为null表示没有值 tab[i] = newNode(hash, key, value, null);//等空，直接插入 else { Node<K,V> e; K k;//1、key（hash）相等 2、hash冲突 （链表） 3、红黑树 if (p.hash == hash &&//如果与第一个元素(数组中的结点)的hash值相等，key相等 ((k = p.key) == key || (key != null && key.equals(k)))) e = p;//将第一个元素赋值给e，用e来记录；跳到646Line 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) {//p.next为空表明处于链表的尾部，1、生成 链表 2、已经是链表 p.next = newNode(hash, key, value, null);// 直接创建 if (binCount >= TREEIFY_THRESHOLD - 1) //链表长度如果>8转红 黑树（or 扩容），-1是因为binCount从0开始 treeifyBin(tab, hash);//树化；还需要判断是否大于64，否则扩 容 break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))//对链表节点中数据进行覆盖判断 break;// 如果key相同,break跳出for循环,执行后面的逻辑 p = e; } } if (e != null) { // key已经存在 V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value;// 用新的value值去覆盖老的value值 afterNodeAccess(e); return oldValue;// 返回覆盖前的value值，put的返回值 } } ++modCount;//用来记录HashMap的修改次数 if (++size > threshold)//map数量是否大于容量 resize();//如果size大于threshold,就需要进行扩容 afterNodeInsertion(evict); return null; }
重点（寻址计算）：
计算存放到数组的位置，如果为null表示没值，有值，表示hash冲突(or key相等)
if ((p = tab[i = (n - 1) & hash]) == null)
寻址公式：
(n - 1) & hash
(16-1) & 1122
0000 0000 1111B
0100 0110 0010B
0010B 开始按位与（都是1则为1，反之0）
思考，为什么不用模运算？（面试常问的问题）
与运算：(n - 1) & hash
模运算：15%2
都可以得到0-15之内的值
为什么不用mod（模运算）进行寻址?
package com.cmap; public class CMod { public static void main(String[] args) { bit(); mod(); } public static void bit() { int num = 10000 * 10; int a = 1; long start = System.currentTimeMillis(); for (int i = num; i > 0; i++) { a &= i; // a = a&i; } long end = System.currentTimeMillis(); System.out.println("BIT耗时>>" + (end - start)); } public static void mod() { int num = 10000 * 10; int a = 1; long start = System.currentTimeMillis(); for (int i = num; i > 0; i++) { a %= i; // a = a%i; } long end = System.currentTimeMillis(); System.out.println("MOD耗时>>" + (end - start)); } }
输出
结论：
mod运算是与运算的20倍，效率太低下
总之，一切为了性能
那么，&运算为什么这么高？操作的是二进制
