HashMap是Java开发当中使用得非常多的一种数据结构,因为其可以快速的定位到需要查找到数据,其最快的速度可以达到O(1),最差的时候也可以达到O(n)。本文以Java8中的HashMap做为分析原型,因为不同的JDK版本中的HashMap,可能存在着底层实现上的不一样。
HashMap是通过数组存储所有的数据,每个元素所存放数组的下标,是根据该存储元素的key的Hash值与该数组的长度减去1做与运算,如下所示:
index = (length_of_array - 1) & hash_of_the_key;
因为在单个Hash值对应的元素小于等于8个时,其查询时间最差为O(8),但是当单个Hash值对应的元素大于8个时,再通过Node的单向链表的方式进行查询,速度上就会变得更慢了;这个时候HashMap就会将Node的普通节点转为TreeNode(红黑树)进行存储,这是由于TreeNode占用的空间大小约为常规节点的两倍,但是其查询速度可以得到保证,这个是通过空间换时间了。当TreeNode中包括的元素变得比较少时,为了存储空间的占用,也会转换为Node节点单向链表的方式实现,它们之间可以互相转换的。
Node:
可以看到每个Node中包括了4个属性,分别为:
hash值:当前Node的Hash值
key:当前Node的key
value:当前Node的value
next:表示指向下一个Node的指针,相同hash值的Node,通过next进行遍历查找
TreeNode:
可以看到TreeNode使用的是红黑树(Red Black Tree)的数据结构,红黑树是一种自平衡二叉查找树,在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能,即使在最坏情况运行时间也是非常良好的,并且在实践中是非常高效的,它可以在O(log n)时间内做查找、插入和删除等操作,这里的n 是树中元素的数目。
以下是一张关于HashMap存储结构的示意图:
写入数据(一切皆在注释中)
其方法如下:
Hash值的计算方法:
读取数据(一切皆在注释中)