分类
uncategorized

Java7 HashMap分析

Java7 HashMap原理分析,以及由此引发的思考。

Java HashMap是一个简单的数据结构,Java中很多其他种类的Hash结构包括HashSet、HashTable、ConcurrentHashMap等都是基于它的。同时Hash是一种很通用的数据结构,在不同场景下Hash的策略不一样,通过Java中的HashMap我们理解基本Hash的实现方式,希望能对我们在工作中不同场景下对Hash结构的使用与理解有所帮助。

Java HashMap是一种数据结构,那么我们先从数据结构的角度来看它。HashMap内部基础数据结构由数组与链表组成,如下图,图中每个元素代表一个键值对,数组结构中每个键值对的键的Hash值都不同,相反链表结构中每个键值对的键的Hash值都相同,也就是说HashMap采用链表的方式处理冲突,知道了基础数据结构,那么构建在之上的操作就很好理解了。

在深入介绍HashMap之前我们先来看一下HashMap内部的一些重要的逻辑变量,这些变量与我们之后介绍HashMap的工作机制紧密相关。

  • size:HashMap中存贮的键值对的个数
  • capacity:数组数据结构的长度
  • loadfactor:默认值为0.75,用于计算threshold,与HashMap Rehash紧密相关
  • threshold:threshold=capacity*loadfactor,当size>=threshold时再次put需要
  • ReshashmodCount:HashMap的映射关系修改的次数

接下来我们看put操作,put操作分三种情况,第一种情况是需要被put的键值对在HashMap中不存在(键值对中的键不存在于HashMap中),并且通过Hash操作计算出来的index,没有发生冲突(数组结构中index位置是空的),此时只需要把它放到数组结构对应索引的位置就好;第二种情况是需要被put的键值对在HashMap中不存在,但是通过Hash操作计算出来的index发生了冲突,此时需要把它放到链表结构中,HashMap中是放到链表结构的头部;第三种情况是键值对已经存在于HashMap中,此时只要替换值就ok了。值得注意的是当执行put操作的时候如果发现size>=threshold,则HashMap首先会Rehash,之后再执行put操作,Rehash操作留待后文再讲。

get操作比较简单,首先计算hash值,Java中每个对象都有的hashCode方法就会在hash方法中被调用,其次通过hash值计算出键在数组结构中所对应的index,如果index位置为空则返回空,否则遍历链表结构,如果键相等就返回次键的值,如果遍历结束都没有找相等的键就返回空。由此可见如果冲突过多的话,get操作的时间会变的很长,极端情况数组结构只有一个节点,那么HashMap则完全退化成链表结构,查询的时间复杂度不在是O(1)而是O(N)。如果我们在创建HashMap的时候将loadfactor参数设置的很大,当数组中元素过多,就会导致冲突过多,从而导致查询缓慢。

接下来再看遍历操作,我们首先来看遍历的逻辑,对于数组结构从左至右,对于链表结构则由上至下。文章开头图片中的HashMap的遍历顺序为:E1->E2->E3->E4->E5>E6->E7->E8->E11->E10。HashMap的遍历操作通过java.util.Iterator接口实现。主要遍历逻辑在java.util.HashMap.HashIterator抽象类中,当我们遍历HashMap的时候会调用HashIterator的nextEntry方法。HashIterator代码如下:

private abstract class HashIterator<E> implements Iterator<E> {
        Entry<K,V> next;      // next entry to return
        int expectedModCount;   // For fast-fail
        int index;         // current slot
        Entry<K,V> current;    // current entry
        HashIterator() {
            expectedModCount = modCount;
            if (size > 0) { // advance to first entry
                Entry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
        }
        public final boolean hasNext() {
            return next != null;
        }
        final Entry<K,V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            Entry<K,V> e = next;
            if (e == null)
                throw new NoSuchElementException();

            if ((next = e.next) == null) {
                Entry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
            current = e;
            return e;
        }
        public void remove() {
            if (current == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            Object k = current.key;
            current = null;
            HashMap.this.removeEntryForKey(k);
            expectedModCount = modCount;
        }
    }

上述代码中大家有没有看到一个熟悉的异常呢,对了就是ConcurrentModificationException,我们来看看它是怎么产生的。首先我们明确一点HashIterator是HashMap的内部类,它能访问HashMap的字段比如modCount。首先新建HashIterator实例的时候设置expectedModCount = modCount,所以正常情况下进行遍历的时候nextEntry方法中的对expectedModCount与modCount相等的判断都是ok的。我们想象这样一个场景,在遍历的同时,如果另外一个线程也持有对该HashMap的引用,并且调用了put、remove或clear方法,改变了HashMap的键值映射结构,此时使modCount++,遍历线程中的下一次对nextEntry方法的调用就会抛出ConcurrentModificationException。

我们想一想HashMap为什么要进行这样的设置呢。在遍历HashMap的过程中,HashMap的内容发生了改变,如果此时遍历继续进行,那么遍历出来的结果可能就不是我们一开始想要的内容了。这种尽早发现问题可能存在的情况并且中断操作抛出异常的做法,我们称之为fail-fast原则

其实还有另外一种比较典型的ConcurrentModificationException的场景。就是在我们遍历HashMap的时候,通过hashMap的put、remove、clear方法来改变HashMap的映射关系。

对于前文提到的改变HashMap的映射关系,指的是操作过后HashMap的元素的个数发生了改变,这样的操作包括put、remove、clear。但是put方法如果被put的键值对已经存在于HashMap中,则不会改变HashMap的映射关系,从而不会导致modCount++,进而不会引起ConcurrentModificationException。

通过HashMap能得到一个keySet与一个values,他们的数据类型分别是HashSet与Collection。那么大家有没有想过他们内部到底是怎么实现的呢,是不是分配了内存空间,拷贝对应的数据新的空间呢。其实不是这样的,通过HashMap的到的keySet与values都是构建在HashMap基础数据结构之上的,并没有重新分内存空间,也就是说三个数据结构是同相同的内存空间,相同的数据结构以及相同的数据。基于此HashMap、HashMap衍生的keySet、HashMap衍生的values中的任意一个对自身的修改操作都对其它两个有影响。另外keySet与values不支持put操作,并且他们的remove与clear操作也必须通过Iterator才能完成。它们三个的遍历操作都是基于HashIterator的,所以keySet与values也同样存在ConcurrentModificationException的问题。

最后我们来看HashMap的Rehash操作。当我们创建一个HashMap的时候可以传入initCapaity参数,HashMap会将initCapaity赋值给threshold,这里是HashMap设计上逻辑不合理的地方,按照一贯逻辑threshold应该为initCapaity*loadfactor,当然它这种设计使得用户更容易理解。其实在HashMap第一次分配内存的时候依然会对initCapaity做出调整,新的值为第一个大于initCapaity的2的N次方的整数值。更当我们向HashMap中添加数据的时候,如果发现size>=thredshold则进行Rehash,HashMap采用2倍扩容的策略,即新的数组元素个数为之前的两倍,当然总个数不能超过Integer.MAX_VALUE因为size为一个整形值。分配好空间之后,在用户线程中直接迁移数据,此时会阻塞用户线程,迁移好之后引用切换,使用新分配的数组。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注