HashMap底层结构、扩容机制实战探索

作者专注于Java、架构、Linux、小程序、爬虫、自动化等技术。 工作期间含泪整理出一些资料，微信搜索【javaUp】，回复 【java】【黑客】【爬虫】【小程序】【面试】等关键字免费获取资料。技术交流、项目合作可私聊。 微信：shuhao-99999 

1.存储结构

从结构上，HashMap是由 数组+链表+红黑树（JDK1.8增加了红黑树部分） 实现的。

下图中，每一个黑色原点代表一个键值对（Node，实现了Map.Entry）,table的默认长度是16；

JDK1.8引入了红黑树，链表长度大于8时转化为红黑树，极大地优化了HashMap的性能

2.获取hash数组索引位置

实质上有3步：取key的hashcode值，高位运算、取模运算

取模运算是JDK7里面的，JDK8没有这个运算方法：

h & (length - 1)

3.hash碰撞

有时候，如果2个key定位到了相同的位置，表示发生了hash碰撞

4.扩容机制（如何减少hash碰撞的概率）

想要减少hash碰撞，就要在键值对达到一定数量的时候，进行hash运算和扩容；

threshold是HashMap所能容纳的最大键值对（Node）数量，计算方式：

threshold = length * （1+loadFactor）

其中，

length是table的默认长度，值为16；

loadFactor是负载因子，默认值为0.75；

也就是说，初始化一个HashMap的时候，HashMap的极限值threshold的默认长度是16 * 1.75 = 12。从下图也可以看出来确实是12！

如上图所示，当前键值对已经达到极限值12，再向map中添加一个键值对之后，就要扩容了。

扩容后的length是原来length的2倍！

5. 设置HashMap的初始大小和负载因子

HashMap有一个构造方法可以设置初始大小和负载因子：HashMap(int initialCapacity, float loadFactor)

当然，也有一个构造方法HashMap(int initialCapacity)，只设置初始大小，实际上也是调用了上面的构造方法：

扩容是一个非常消耗性能的操作，所以如果我们已经预知 hashmap 中元素的个数，那么预设元素的个数能够有效的提高hashmap 的性能。比如说，我们有 1000 个元素 new HashMap(1000), 但是理论上来讲 new HashMap(1024) 更合适，不过上面 annegu 已经说过，即使是 1000，hashmap 也自动会将其设置为 1024。 但是 new HashMap(1024) 还不是更合适的，因为0.75*1000 < 1000, 也就是说为了让 0.75 * length > 1000（length是table的长度）， 我们必须这样 new HashMap(2048) 才最合适，既考虑了 & 的问题，也避免了 resize的问题。

6.一般用什么作为HashMap的key?

一般用Integer、String这种不可变类当HashMap当key，而且String最为常用。选择Integer，String这种不可变的类型，像对String的一切操作都是新建一个String对象，对新的对象进行拼接分割等，这些类已经很规范的覆写了hashCode()以及equals()方法。作为不可变类天生是线程安全的

7.HashSet底层是基于HashMap实现的

查看HashSet的源码可以知道，无论是构造方法，还是add、remove、size等方法，都是基于HashMap来实现的！把元素当做HashMap的key来存储，这是一个非常精巧的构思！

8.链表转换为红黑树，和树转换为链表的条件 

1.链表转红黑树，两个条件，必须同时满足两个条件才能进行转换

条件1：单个链表长度大于等于8

条件2：hashMap的总长度大于64个、且树化的节点位置不能为空

2.红黑树转链表，两个条件，必须同时满足两个条件才能进行转换

条件1：树内节点数小于等于6

条件2：根节点为空，根节点的左右子树为空，根节点的左子树的左子树为空