HashMap实现存储原理及性能优化

柔情只为你懂 2021-12-12 11:09 356阅读 0赞

最近工作比较忙，好久不写点东西了.......（其实是比较懒）

这几天在看JAVA性能调优中讲到HashMap性能优化。这篇文章着实对我印象深刻，印象深刻的原因有两个：一是这篇文章耗时较长，看了三天，一天一遍；二是文章里面涉及知识较多，比较难理解。其实在学习一个新技能时，尤其是新框架或者读源码，很难一两遍就搞明白的，需要不断反复学习阅读；正应了那句话---【**书读百遍，其义自见！**】

言归正传....

### 【**HashMap存储原理**】 ###

在说hashMap实现原理前，先说点关于HashMap底层的几个关键词

hashmap容量：指的hashmap的初始容量。当不指定容量时，默认是16

加载因子：默认为0.75

边界值：当hashmap的node个数超过边界值，就会扩容数组。边界值=容量\*加载因子。

存储原理：当new一个hashmap后，就会初始化hashmap大小，如果没有指定大小，默认大小为16，边界值是12；

这里会初始化一个长度为16的Node数组。

node就是hashmap的内部类，每个Node里包含key-value和next等属性（next是指向下一个node的引用地址）

每次put一个key-vlue时，系统会根据key的hashCode（）返回值，再通过hash（）方法计算出hash值，然后通过

（n-1）&hash值得到改node的实际存储地址。这里有一点需要注意，就是计算的内存地址肯定在初始化的数组里面，通俗点说，可以把这内存地址看做初始化数组的下标，计算出的这个下标肯定会在这个数组下标范围内。具体原因比较复杂不用追究。

当put第二个元素时，还是会根据key经过一系列计算获取到数组下标，当下标冲突时（即计算出的下标已经被占用了），也就是哈希冲突，那么会通过链表结构，把该新的元素放到前面下标元素的后面（如果key相同就是覆盖上一个node中的value，只有key不相同时才放后面node），同时上一个元素node中的next会指向新元素的引用，如果在put进来的新元素也发生了哈希冲突，就继续向后方，到达到8个时，就会采用红黑树的结构存储（jdk8开始），因为红黑树的结构比链表查询的快；

当put的元素个数达到初始化数组的边界值12时，就会发生数组扩容，一旦有数组扩容就会比较耗时。所以在预估出map大小的情况下，可以设置一个map初始值，初始值大小=预估值/0.75；需要注意的是，**这个初始大小应该是2的整数次幂。这样可以有效利用存储空间，减少哈希冲突**。

### **【HashMap性能优化技巧】** ###

如果hashmap的存储原理太多不好理解，那么就记住这些优化技巧吧

一是当预估出hashmap大小时，可以设置初始值。初始值遵循下面原则：2的整数次幂；初始值=预估值/0.75

二是当hashmap查询效率要求高时，可以把加载因子设置小点。原因是加载因子小，空间充足，发生哈希冲突的几率小，那么就不会出现链表和红黑树；

三是当hashmap对空间要求比较节省时，就可以把加载因子设置大点。这样node数组空间利用比较充分。因为加载因子大，边界值就大，node数组就会更容易占满，空间利用比较充分；