Java中HashMap等的实现要点浅析

时间:2021-05-24 22:19:22

  @南柯梦博客中的系列文章对Jdk中常用容器类ArrayList、LinkedList、HashMap、HashSet等的实现原理以代码注释的方式给予了说明(详见http://www.cnblogs.com/dongying/p/4022795.html#3045118等文章),而我在这里用另一种方式对其实现要点作一说明。

一、ArrayList和LinkedList的实现

  ArrayList和LinkList的实现原理比较简单,在关于Java的面试中经常被要求立即写出这两种容器类的简单实现。正如其名称所显示的,利用Java对泛型的支持在内部分别使用数组和双向链表存储元素,当容量不足时进行扩容,因而这两种容器类的适用场景基本对应于数组和链表的适用场景。

二、HashMap的实现之hash值

  HashMap的实现使用了内部类Entry,实际上存储在HashMap中的键值对就是使用Entry类型的数组来存储的,而Entry同时还是个单向无头链表,其用next属性指向下一个元素。存储键值对时首先得到key的hash值,并计算其在Entry数组中的存储位置,如方法indexFor所示:

static int indexFor(int h, int length) {
return h & (length-1);
}

即将hash值和Entry数组做按位与运算得到其应存储的位置索引。接下来的处理就是其中的精华了。如果该位置处是空的,则把代表键值对的Entry对象放入;否则位置处存在Entry链表,遍历该链表,如果有Entry节点的key值和待插入的Entry对象相等,则用新的value值替换旧值并返回旧值;如果没有相等的key值则把新的Entry对象放到链表头处。

三、相同hash值时键值对的存储结构

  总结一下,实际上这是不同key的hash值相同时的冲突处理方法。根据hash值的原理,相同元素其hash值必定相同,不同元素其hash值不一定相同。反过来讲,hash值相同的元素其值不一定相同,但hash值不同的元素其值一定不同。因此不同元素根据hash值以及indexFor()方法取得的索引值很可能是相同的,故需要在索引位置处用链表存储所有元素以供进一步甄别。由此可以推断出,HashMap的get()方法只能保证近似的O(1)时间复杂度。HashMap中的loadFactor属性也正是因为这个原因才存在的。进一步查看源码发现,Jdk8中HashMap的实现已有所变化,相同hash值的键值对是用链表和红黑树来共同实现的,具体使用哪种结构由冲突的key值个数决定。这样查找的时间复杂度得到了进一步优化,但同时增加了存储的时间,因为要涉及链表和红黑树的转换以及红黑树的再平衡等。

三、HashMap应用之HashSet

  而对于HashSet可以看做HashMap的一种特殊的使用,即对HashMap中所有的key值都存储相同的外部不可见的对象。