[数据结构与算法]HashMap底层原理理解

1、底层结构

HashMap底层结构在jdk1.7之前和1.8之后会有一些变化。

1. jdk1.7以前hashmap底层结构采用数组+链表
2. jdk1.8之后hashmap底层结构采用数组+链表+红黑树

原理

hashmap是一个关联数组、哈希表，它是线程不安全的，允许key为null,value为null。遍历时无序。
hashmap在put一个值的时候把key values 封装成一个entry,
1、首先会通过调用一个hash(key)方法得到一个hashcode值，
2、然后通过这个hashcode值和数组的长度lengh-1进行&与运算得到一个数组的下标index。
3、然后查看数组对应的下标是否有值，没有直接放入。如果有就和检查要插入的值是否和原本的值一样，不一样的话把entry放入到对应下标的数组中的链表中，采用头插法。

在jdk1.8之后，如果链表中的个数大于等于8并且数组的长度大于64，就会把数组的链表转化为红黑树。此时采用尾插法，若链表的 个数小于等于6个，又会把红黑树改为链表。

扩容

HashMap 扩容的数量都是2的n次方

未更新完。。。。。