首页 > 代码库 > HashMap实现原理

HashMap实现原理

HashMap的数据结构是数组+单向链表,数组里面存储就是链表的Head节点,链表节点存储的是我们put进去的key/value。

技术分享

 

如果要实现HashMap,主要有三个重要的功能点:

1.初始化,也就是HashMap的构造方法

在初始化的时候要给数组的大小一个默认值,也就是常说的桶数量,当然这个值是可以指定的,缺省是通过HashMap的属性来确定的

static final int DEFAULT_INITIAL_CAPACITY = 16;

对于HashMap中桶数量的值必须是2的N次幂,而且这个是HashMap强制规定的。这样做的原因就是因为计算机进行2次幂的运算是非常高效的,仅通过位移操作就可以完成2的N次幂的运算。

 

2.put(K key, V Value)方法

通过key来计算一个hash值,这个值就是数组的index,get(index)来获取链表的Head节点,如果没有Head节点,就把当前key/value创建一个节点作为Head节点;通过更新或者插入新节点来将数据存储起来。

 

如果数据量很大,造成链表很长,对数据的读取有很大的性能影响,因此我们可以扩大数组的大小,也就是增加桶的数量。增加桶数量后要将原来的复制新的结构里面,这个过程就是我们常说的rehash过程,很耗性能,这也是没办法的事,牺牲写性能来换取都性能。

我们常说HashMap是非线程安全的,就是在多线程中使用HashMap,rehash会造成链表死循环,导致不可用。

 

那么就有两个问题

A.什么时候扩容

HashMap默认初始容量16,加载因子0.75,也就是说最多能放16*0.75=12个元素,当put第13个时,HashMap将发生rehash,rehash的一系列处理比较影响性能,所以当我们需要向HashMap存放较多元素时,最好在初始化的时候指定合适的初始容量和加载因子,否则HashMap默认只能存12个元素,将会发生多次rehash操作。

 

B.怎么扩容,或者说扩容的步长是多少

HashMap在扩容时,新数组的容量将是原来的2倍。

 

3.get(Object key)方法

通过key来计算一个hash值,这个值就是数组的index,get(index)来获取链表的Head节点。利用Head节点遍历这个链表,根据比较key的hash值以及key的数值是否相等(注意要用equals方法),从而找出相应的value,没有则返回null。

 

HashMap实现原理