HashMap
基本知识点
- hahsMap 负载因为默认为0.75，作用是用于决定什么时候扩容、
- 默认数组大小为16，并且数组大小永远为2的倍数，即使我们实例化时候传入非2的倍数，map内部也会找一个最接近的2的倍数大小替代它使用
- 每次扩容都是2的倍数，因为数组下标是有key的hash和数组长度-1做与运算得到的。对于2的倍数-1的16进制，低位都是1，1&1=0,1&0=0,这样可以保证hash每一位都参与计算，使得更加散列。如果非2的倍数，出现了0，那么0和任何数与都是0，那么有些下标永远计算不到。
- 当数组长度大于64时，且链表长度大于8，那么会转换链表为红黑树，当链表长度小于6时候，会再讲红黑树转为链表。转换只会在put元素时候触发
简介概括原理
- HashMap内部维护了一个Node对象数组，注意的是:实例化hashMap对象时候，并不会给内部维护的数组table初始化，仅仅是在hashMap对象中保存一下传入的默认数组大小和负载因子。数组第一次初始化是在put时候。
- 每次put值的时候，会先对Key进行hash散列运算，并和数组长度-1做与运算，得到其在数组中的下标。
- 首先判断数组是否已经初始化过，如果没初始化过，会调用resize()调整数组长度并进行初始化操作。
- 根据下标找到对应的Node对象，如果对象为Null，那么就实例化一个Node对象，保存key和value。如果对象不为Null，那么判断其对象是否是TreeNode，如果对象类型是TreeNode，那么说明当前存储的红黑树，如果不为TreeNode类型，那么说明存储的是链表式结构。
- 如果是红黑树，那么通过红黑树的排序性质（二叉排序树）来查找节点，如果找不到节点，则根据value大小在红黑树合适的位置来插入Node。插入结束，根据需要来平衡红黑树。
- 如果是链表，那么依次遍历比对key查找节点，查找到后替换值，没找到则在后续插入新对象Node。
- 插入结束后，会判断元素个数和数组长度乘负载因子的大小，从而决定是否扩容
- 获取元素时候，直接查找元素获取对象
- 移除元素时候，先查找到对应元素，然后再移除，移除时候并不会触发resize方法，从而也不会转换链表和红黑树结构。
关于数组扩容，resize方法+tableSizeFor方法
- capcity
HahsMap中实际没有专门定义这个变量，只有一个默认值16，这个变量的含义是指map中数组的长度大小，是我们可以在实例化map时候传入的。我们实例化对象时候传入的数组长度，如果不是2的倍数，那么map中会找到最接近其的2的倍数作为数组长度。这里找到最接近其2的倍数使用的方法就是tableSizeFor。
每次数组如果判断需要扩容时候，那么都会调用resize方法进行处理，这里包括数组的第一次初始化。
- resize方法做的事情
- 将原数组长度乘2算出新的数组长度。
- 根据负载因子和当前数组长度计算出新的数组最大元素限制，保存到map中。
- 生成新的Node数组
- 遍历当前的table，将每个元素都放到新数组中的对应位置中。
- 什么时候会触发扩容调用resize方法呢？
从源码流程中可以看到，在put元素时候，如果元素个数大于数组长度乘以负载因子，那么就会触发扩容
- 什么时候红黑树转为链表呢？
在每次扩容方法resize被调用后，在扩容方法里会判断如果是红黑树，那么会调用其spilt方法判断是否Node个数小于等于6，如果是则转为链表结构。
所以在删除元素时候并不会触发红黑树转为链表
根据key查找下标的方法
- 调用key的hashCode方法，得到hash值
- 取hash的高16位和其低16位做异或得到新的hash值作为key的最终hash值，记为hash1
- 拿hash1和数组长度-1做与，得到数组下标。
- 高16和地16做异或原因
数组长度一般不会特别大，将hash高16和低16做一次异或运算，保证key的hash全部参与数组下标的计算，增加散列度。
- 和数组长度-1做与原因
防止下标越界。
hashMap key可以为Null吗
可以，对于key为null，那么会将数组保存到数组的第一位，即数组下标永远为0
为什么HashMap的默认负载因子是0.75呢？而不是别的呢？
设计者通过各种计算得出的最优扩容。
jdk1.7和jdk1.8 HashMap 的区别
- jdk1.7不存在红黑树，1.8存在红黑树，1.7结构是数组+链表，1.8是数组+链表+红黑树
- 1.7将数据插入到链表头部，1.8插入数据到链表尾部
- 1.7在元素插入前检查扩容，1.8是在插入后检查扩容
为什么HashMap线程不安全
- 对于jdk1.8
我们插入数据时候，如果数组下标当前是null，那么会直接生成一个新的Node对象插入数组，多线程中，这里可能出现同时插入一个新数据，后边数据将前边数据覆盖的情况。
- 对于jdk1.7
1.7链表中插入Node是插入到头部，所以每次扩容后，原链表相当于倒置的插入到了新的数组中。他会从旧数组的链表头部开始遍历，查找其在新数组的下标，然后插入，如果存在A和B，在旧数组中链表位置为A->B,扩容后，他两正好还在同一个数组下标，那么有以下流程。
多线程扩容时候：
- 线程1，扩容时候会循环遍历链表，首先拿出A，赋给临时遍历E，
- 此时线程2已经执行完扩容，数组现状是对应下标为B->A
- 接着线程1继续执行，将E的next指向新数组下标的元素，此时新数组下标的元素已经是B了，所以A->B->A,接着，死循环就开始了。
putMapEntries方法什么用，做什么事
对于我们实例化时候传入的map集合，该方法用于遍历传入的map，将其内部数据依次传入到当前的map中。
