共计 1604 个字符，预计需要花费 5 分钟才能阅读完成。
HashMap 是 java 中十分罕用的容器，以前只是停留在应用阶段，对于它的底层设计更是只知其一; 不知其二，看到源码才晓得它奇妙的设计和工作原理。在理解底层原理之前，倡议先学习相干的数据结构几种常见数据结构，能够帮忙你更好的理解 HashMap。
数据结构
HashMap 的数据结构是 数组 + 链表 ，默认初始大小是16，默认负载因子是0.75，当理论容量大小（容量大小是蕴含每一个 node 的大小，不是非空数组的大小）超过定义的容量 Capacity 乘以负载因子的值后，HashMap 会进行一次resize 扩容操作，创立一个 2 倍大小的新数组，同时 rehash 所有的数据（之所以须要 rehash，而不是间接复制之前的数组地位，是因为 hash 算法中须要应用到数组长度，扩容后数组的长度变动了）
HashMap 初始大小是 16，设置成 2 的幂，便于进行位运算，另外，在手动设置 HashMap 大小的时候，也尽量设置成 2 的幂数
链表进化和进化机制：hashmap 中的链表长度在大于 8 的时候会进化成 红黑树结构，小于 6 的时候又会进化成链表。那么，为什么是 8 和 6 呢? 那是因为在屡次的试验中发现，产生 8 次 hash 碰撞的概率十分十分小，设置成 8 能够在小概率事件产生后，转换数据结构，优化后续查问性能，进化阈值设置成 6 是为了防止设置成 8 或者 7 的时候，因为 hash 碰撞在 8 左近来回的切换数据结构.
Hash 算法
每一个 key 会通过一次 hash 运算（先获取 key 的 hashcode，将 hashcode 无符号右移 16 位 [hashcode >>> 16]，对右移后的值和 hashcode 进行异或运算（二进制里雷同得 0，不同得 1））[hash = hashcode ^ hashcode >>> 16]，失去 key 的 hash 值，至于数组的 index 值，须要将 hash 值和数组长度减一后的值进行与运算（同时为 1 后果为 1，否则为 0）[(length – 1) & hash] 失去。
hashmap 产生 hash 碰撞的数组会应用尾插法（jdk7 是头插法）插入一个 node，node 中蕴含 key，hash 值，value 以及下一个 node 的指针 next
tips：<< 左移，左边补 0 >> 右移，右边初始位为正补 0，为负补 1 >>> 无符号右移，初始位补 0 对于二进制来说，初始位 0 为正，1 为负
线程平安
HashMap 的线程不平安，jdk7 和 jdk8 的起因不同
在 jdk7 中，应用的是头插法，会有两种状况的线程不平安问题
（1）在某一个数组的索引的地位，A 线程要插入一对 key-value，指针 next 指向第一个 Entry，这个时候 B 线程也要插入一对 key-value，因为 A 线程的赋值还未实现，所以 Entry 的 next 也指向第一个 Entry，并胜利增加。随后线程 A 开始进行赋值操作，这个时候就会发现，在线程 A 执行完之后，线程 B 所增加的数据被笼罩了
（2）有一个链表有两个相邻的 Entry，Entry1 和 Entry2，Entry1 的 next 指针指向 Entry2，当线程 A 在执行 resize 操作的时候，Entry1 还没有胜利执行完搁置到新数组并更新 next 的操作的时候，切换到 B 线程，B 线程操作实现了整个 HashMap 的 resize，此时扩容后的 HashMap，因为头插法的存在，Entry2 的 next 指针指向 Entry1，同时切换到线程 A，线程 A 继续执行 Entry1 搁置到新数组中的操作，Entry1 的 next 指针指向 Entry2，又因为 Entry2 的 next 指针是指向 Entry1 的，所以会陷入死循环，线程 A 无奈跳出 resize 这步在 jdk8 中，因为尾插法的存在，不会呈现死循环的状况，然而会呈现数据笼罩的问题。假如线程 A 和线程 B 同时在 put 值，它们的 key 的 hash 值通过计算后失去的 index 索引值雷同，此时线程 A 挂起，线程 B 进行了更新操作，之后线程 A 持续进行更新操作，会笼罩后面线程 B 的更新，线程 B put 的数据就隐没了
