hashMap，面试看这篇文章就够了

HashMap

它是JAVA中的一个集合框架通过key value的方式存储数据，如果key采用自定义对象的话必须重写Key对象的HashCode和Equals方法。

最大容量为：1<<30 2的30次方

jdk1.8后他的底层是由数组+链表+红黑树组成的（1.7之前只有数组+链表）

存储结构如图所示：

数组大小：

数组默认长度为16。

当通过构造函数指定数组大小时，系统会自动将该值转化为一个>=他的2的N次方的数

原因：为了方便计算索引值hash&（length-1），防止出现数组越界，减少hash冲突，让数据散列的更均匀。

eg：通过构造函数指定数组长度为13，则系统转化为16，length-1为15（1111）可以方便的进行&运算。（为了系统&操作的方便）

存储过程：

通过Key的hash（hash是由hashcode右移16位再异或（两个数不同为1）hashcode计算出来的）&(与，两个都为1时为1)数组长度-1来求出存储元素在数组中的索引

（采用hash的原因，hashMap中存放的元素是有限的，因此数组长度也是有限的，为了让Key的hashCode高几位也参与到&运算当中，可以计算出hash后进行&运算）

若该索引没有元素则直接存放即可，若有元素，则比较hash，若hash相同，

（hash相同equlas不一定相同，hash不同equlas不同）则通过equlas方法来比较key，

若有相同的则覆盖，若没有相同的则使用尾插法来存放到链表当中，当链表长度达到8且散列表中元素个数达到64后进行树转，发生hash冲突则判断是否需要resize扩容。

hashmap的put方法：

一：判断是否是第一次调用put方法然后进行扩容

二：计算出所在位置判断是否存在元素，不存在直接存放

三：此时发生了Hash冲突，判断散列表长度是否达到阈值且发生了Hash冲突，则进行扩容

四：通过hash equals比较是否相同，相同则进行value的覆盖

五：判断是否是红黑树，如果是则插入树中

六：判断是否有链表，若有则依次比较，没有相同元素则尾插法插入

七：判断是否链表达到8，若散列表长度也达到了64则进行转换为红黑树，否则进行扩容

数据转换：

当链表长度达到8（根据泊松分布公式决定）且hashmap的散列表长度达到64时（否则优先扩容）进行数据转化，将链表转为红黑树

当红黑树大小变为6时，回退到链表结构

红黑树所占节点大小约为链表结点的2倍，故一开始是链表结构。

负载因子：

hashmap的默认负载因子（loadFactor）是0.75（泊松公式推导出来的）（决定多会儿扩容）为了让散列更均匀，负载因子越大（扩容越慢），空间利用率越高但发生Hash冲突的概率则越高，负载因子越小，发生Hash冲突的概率就低了，但空间利用率低。（为了扩容机制减少Hash冲突还保证利用率）

扩容机制（resize）：

数组已存储元素达到临界值（数组总长度*0.75）且这次添加数据发生了Hash冲突时才扩容，大小左移一位变为原来的2倍。每次扩容后都要rehash（重新计算Hash值，因为数组长度变了，索引位置也要改变）

自定义对象作为key时必须重写hashcode和equlas吗？

是的，必须重写，自定义对象我们为了让其语义上相等，eg：年龄姓名相同的就认为是一个对象，我们就需要重写equals，equlas相等则hashcode必然相同，所以要重写hashcode（hashcode相同，equlas不一定相同）在put，get时，也需要hashcode来找到索引位置，equlas来比较对象是否相同。