# 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的性能。