HashMap特点：

1. 存储方式为键值对，键不能重复，键和值都可以为null
2. 底层数据结构使用数组+链表、红黑树
3. 默认容量16，负载因子0.75，当元素数量>当前容量x0.75（threshold）时，自动扩容，容量x2

插入逻辑：

1. 第一次插入x的时候初始化map，指定大小，则默认容量16，负载因子0.75，指定大小K，则容量为大于k的最小2的整数次方（k=7,容量为8，k=10，容量为16）

2. 计算k的hash值，计算数组的坐标index

   1. hash值计算方式：调用key的hashcode方法，拿到32位int值，然后将高16位和低16位进行^操作
   2. index值计算方式：hash值和map容量-1做&操作，即hash&（length-1）
   image

1，hashmap的hash函数怎么设计的，为什么这样设计？

​ 调用key的hashcode方法，拿到32位int值，然后将高16位和低16位进行^操作。

​ 这样设计的目的：降低hash碰撞。至于为什么不直接使用key的hashcode，是因为计算index值时，需要做hash&（length-1）操作，如果只使用key的hashcode，那么受map的容量影响只能使用到hashcode的最低几位，将hashcode高16位和低16位进行^操作就能尽可能的保存高位和低位信息，减低hash碰撞

2，hashmap的容量为什么是2的整数次方？

​ 1，尽可能减少移动已经散列好的元素位置

​ 2，散列的更加均匀保证数组内每个位置都可能会用到

​ 因为计算index位置时要做hash&（length-1）操作，而length-1用二进制标示低位全是1，和hash值做&的时候，就会保留hash值的最低几位。

​ 例如：hash=5，扩容前后，计算的index都是5

image

5&31

​ hash分别为1、2，length-1=14时，最低位不管是0还是1，计算出的index的最低位都是0，即数组内部分位置永远也不可能存储数据

image

2&14

LinkedHashMap保持插入顺序的hashMap，每个节点有两个指针指向前后的节点。

TreeMap基于红黑树的自动排序key-value存储结构，key值不重复。