千锋教育Java入门全套视频教程(java核心技术，适合java零基础，Java

HashMap （JDK1.7：一维数组+单向链表，头插法 JDK1.8：一维数组+单向链表+红黑树，尾插法）

默认长度为16，长度必须是2的幂 最大容量1<<30(十亿多)

默认负载因子0.75

添加put过程

获取key的hash值 -- hashCode()

通过hash值计算在数组中的下标

判断下标上是否有元素存在

没有 -- 创建entry对象，存入数组中

有 -- 判断多个key是否相同 -- (hash)&&(== || equals)

相同 -- 替换原value值

不同 -- 添加元素(JDK1.7头插法 ， JDK1.8尾插法)

HashMap内部类Entry(单向链表)

key value hash next

Hash回环解决

如果出现了Hash回环，不应该怪HashMap，因为HashMap明确表示该类不是一个线程安全的类，多线程下应使用ConcurrentHashMap

使用线程安全的ConcurrentHashMap

多线程下使用HashMap可能出现的情况

一个线程不断添加元素，导致HashMap扩容

一个线程不断遍历元素（第一个线程在扩容期间发生了引用地址回环），当前线程遍历时就会出现脏数据

默认的负载因子为什么是0.75？

取得了时间与空间的平衡

负载因子过大，利用了空间，浪费了时间

负载因子过小，利用了时间，浪费了空间

减少Hash碰撞的方法？

重写equals和hashCode方法，equals底层为== 不重写就无法判断是否相同

为什么长度会是2的幂？(重要)

获取元素在数组的下标是 元素的hash值&数组长度-1

如果数组的长度不是2的幂，-1就会导致二进制中的某几位都是0，和元素的hash值做&运算，二进制上的某几位就永远是0，最终导致下标分布不均匀，浪费空间

HashMap什么时候扩容？

如果映射关系个数大于等于阈值 并且 当前下标上的元素不为null，就扩容

JDK1.7HashMap与JDK1.8HashMap的区别？

JDK1.7HashMap

数据结构：一维数组+单向链表

计算hash值：位运算

单项链表插值法：头插法

JDK1.8HashMap

数据结构

一维数组+单向链表--链表长度>8&&数组长度>64 -->一维数组+红黑树（目的：提高查询效率）

一维数组+红黑树--红黑树节点<6 --> 一维数组+单向链表

计算hash值：高16位^低16位（计算更加散列的hash值）

单项链表插值法：尾插法