HashMap的扩容机制

简介

HashMap是单纯的kv键值对结构，可以接受null键和null值，速度比较快，非线程安全。

HashMap的数据结构

HashMap实际上是一个“链表的数组”的数据结构，每个元素存放链表头节点的数组，即数组和链表的结合体。

hashmap

Entry就是数组中的元素，每个Map.Entry其实就是一个key-value对，它持有指向下一个元素的引用，这就构成了链表。

工作原理

  • put

当我们往HashMap中put元素的时候，先根据key的hashCode重新计算hash值，根据hash值得到这个元素在数组中的位置（即下标），如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组的该位置上。

HashMap基于hashing原理，使用put()方法存储，当将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，然后找到bucket位置来存储值对象。

当获取对象时，同上找到对应的bucket，通过键对象的equals()方法找到正确的键值对，然后返回值对象。

  • resize(rehash)

当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，这是一个常用的操作，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

那么HashMap什么时候进行扩容呢？当HashMap中的元素个数超过数组大小 loadFactor 时，就会进行数组扩容，loadFactor 的默认值为 0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过 16 * 0.75 = 12 的时候，就要把数组的大小扩展为 2 * 16 = 32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经与之HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。