HashMap总结

HashMap实现了Map接口，Map中的数据是以(Key,Value)的形式存储的，在查找的时候，能够通过哈希函数将Key映射到哈希表中的一个索引位置，从而实现快速访问。Key不能重复，但是Value可以重复。

HashMap的键和值都可以为null，如果键为null，则映射到哈希表的第一个元素。

HashMap有一个初始容量和负载因子，初始容量是哈希表的初始大小，默认是16，负载因子是哈希表在扩容之前，存储的键值对数量和哈希表大小的比例，默认是0.75。

put方法内部的执行流程

在put元素的时候，背后调用了putVal方法，会先判断定位到的数组位置有没有元素。如果没有元素，则直接插入。如果有元素，会先判断Key是否相同，如果相同就直接覆盖；如果不同，就判断当前节点是否是一个树节点，如果是就调用putTreeVal将元素添加进去，如果不是就遍历链表插入（插入的是链表尾部）。

那么是如何判断key是否相同的呢？

简单来说，是先获取key对象的hashCode值，然后用hash方法将其低位和高位进行异或操作，得到最终的hash值，然后将hash值去模，映射到实际的存储位置上。对于hashCode的高位和低位，分布是比较均匀的，如果简单进行相加或与操作，容易出现哈希冲突，而异或操作可以避免这个问题。

HashMap的底层存储

HashMap的底层是用数组实现的，当需要存储元素的时候，不断put元素进去，达到一定容量后会扩容，一是能存储的元素更多了，二是因为位置多了，查询效率也会更快，之前可能多个元素会通过拉链法放在同一个索引上，查询的时候还需要遍历链表，时间复杂度O(n)，如果位置多了，一个元素占一个索引，查找的时间复杂度就是O(1)。

扩容机制

数组是无法自动进行扩容的，HashMap的resize()方法会声明一个更大容量的数组，将之前旧的小容量数组中的元素复制过去，并且重新计算hash值，计算hash值是为了将元素分布得更均匀，减少hash碰撞，这个计算hash值的过程是比较耗时的。