HashMap是一个用来存储Key-Value键值对的集合，每一个键值对叫做Entry，这些键值对分散存储在一个数组中，每个数组空间都存储一个链表结构，每一个链表节点都是一个Node对象，里面包含了key、value、next、hash

HashMap数组每一个元素的初始值都是Null

Put方法的实现原理：

1).执行putVal方法，判断table(哈希表的链接数组，对应桶的下标，桶，bucket，指数组中的元素)是否为空或者null，如果为空，就执行resize()进行扩容

2).根据key值计算hash值得到数组下标i，如果数组下标位置没有其他节点，即table[i]==null，直接新建节点添加，转向6，如果存在其他节点，转向3

3).判断table[i]的首个元素是否与key相同，如果相同直接覆盖value，否则转向4

4).判断table[i]是否是红黑树，如果是红黑树，直接在树中插入键值对，否则转向5

5).遍历table[i]，判断链表长度是否大于8，如果大于8就将链表转为红黑树，在红黑树中进行插入操作，否则进行链表的插入操作，遍历过程中如果发现key已经存在则直接覆盖value即可

6).插入成功后，判断实际存在的键值对数量size，是否超过了最大容量threshold，如果超过进行扩容

Get方法的实现原理：

首先计算key的hash值，然后计算出key的数组下标，获得数组元素的位置，如果产生碰撞，使用key.equals()方法查找对应的节点

如何确定hash值 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h »> 16); }

从源码可以看出，hash函数中有一个变量h，h是key的hashCode值，将h和h无符号右移16位后的值做异或操作，得到最终的hash值

如何寻找数组下标：

hash值&(数组长度-1)，即hash值与数组长度-1做与运算

为什么高低位要进行异或操作

如果不进行异或操作，得到的hash值只保留了低位的特性，和数组长度-1进行与操作时，如果数组容量小，容易产生碰撞，进行高低位异或得到的hash值会均匀分布，减少碰撞概率

为什么数组大小是2的幂次方

寻找数组下标时是hash值&(数组长度-1)

数组长度-1是为了让得到的下标结果在数组范围内，不越界

数组大小是2的幂次方，减一后二进制表示都是1，可以合理分配数组的位置，如果不是2的幂次方，二进制表示后肯定有0，例如1101，这样得到的数组下标只能由1，2，4位决定，导致数组下标分布不均匀，大大减小了数组下标的利用率

为什么负载因子是0.75

如果负载因子是0.5，会有一半的数组空间被浪费，随着数组的增大，浪费的越多

如果负载因子是1，数组扩容是为了减少hash碰撞，如果是1，就需要每个数组下标都有值才会进行扩容，如果有一个数组下标迟迟没有值，很有可能其他数组下标的链表已经很长了，已经经历过很多次的碰撞，大大影响性能

为什么使用红黑树不使用平衡二叉树

平衡二叉树追求绝对平衡，条件比较苛刻，左右两个子树的高度差的绝对值不超过1，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知

红黑树放弃了追求绝对完全平衡，追求大致平衡，保证每次只需要三次旋转就能达到平衡，实现起来比较简单

如何扩容：

每次扩容都是两倍，因为默认数组长度是16，负载因子是0.75，所以当数组大小变为12时开始扩容，扩容的时候会新建一个数组，原数组会被垃圾回收器回收，将原数组每个节点的hash值和原数组长度进行与操作，结果等于0代表该节点位置不变，否则该节点的位置是原来位置+扩容大小

如何将HashMap变为线程安全的

使用Collections.synchronizedMap(map)方法

最后修改于 2020-03-22