HashMap源码要点整理

之前说过了ArrayList,这篇说说java.util.HashMap。

0. 先看下支持实现的几个属性

除了modCount,还有

  • transient Entry<K,V>[] table;
  • transient int size;
  • int threshold;
  • final float loadFactor;

size和ArrayList一样,是map中实际存入数据的多少,而非数组table的长度。threshold是map需要扩容的限值,loadFactor则是当前hash存储结构的装载因子。table是实现hash存储的主要结构,是一个Entry数组。简单看下(HashMap的)Entry结构

  • final K key;
  • V value;
  • Entry<K,V> next;
  • int hash;

其中key和value就不多说了。next是hash发生冲突时,同在一个slot下的entry链表的指向下一个node的指针。hash则是根据key计算出来的散列值。

1. 最基本的操作put()和get()

HashMap对这两个操作的查找过程实际上是一样的。put的key如果已存在,实际是更新value值。

首先,对于key为null的情况,直接映射到table[0],再通过冲突链表找到key确实是null的Entry。

对于其他大部分情况,查找entry的方式是一致的,以put()源码为例。

    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

先对key对象做散列计算,这个版本不同具体计算方法有可能不同。再根据此散列值结合table数组的长度做与运算,取得次entry在表中的位置。后面的循环则是为了解决冲突所做的链表查找。

这个过程需要注意有两点。第一个是entry的hash值是根据key对象的hashCode()计算得出,第二个则是下面寻找entry的对比,用的是&&条件,意思是只要e.hash==hash不满足,则不认为这个entry是要找到的entry。

其中的e.recordAccess()实际上是为继承HashMap的LinkedHashMap维护访问顺序维护列表收集数据,HashMap类本身实现为空。

对于put()方法,如果没有找到key对应的entry,则添加entry。

2. 添加新的Entry对象和扩容

添加新的Entry实际上是addEntry()中调用的createEntry()方法调用的,实现也很简单,就是传给(HashMap的)Entry构造方法四个参数值,并放入table数组指定位置。需要注意的是,如果原Index处的slot已经有entry数据,即发生冲突,则新Entry放在前面,把之前的列表接在新entry的后面。

更需要注意的是HashMap的扩容。在addEntry()方法的开始处,就要进行判断,size值是不是已经等于甚至超过threshold阈值了,如果已达到,则必须扩容处理并全面重新映射。

对于容量,HashMap都是采用2的整数次幂,默认初始容量16,装载因子0.75,即无参构造HashMap对象时,首次最多放12个元素。

扩容时也是一样,都是double扩容,new一个原容量2倍的新Entry数组newTable。更重要的是,此后的Entry数据迁移工作,每个节点要重新做hash映射。这个过程是要把所有entry节点都过一遍。最后,修改threshold阈值。

和用ArrayList需要强调的一样,对于HashMap对象,扩容也是一件成本很高的事情,所以最好在使用前明确容量需求,避免扩容和重新映射。

对于装载因子也要考虑,装载因子太小,过度浪费无用空间,如果装载因子太大,则发生hash冲突的可能性大大增加,冲突发生的情况就是链表查找元素,效率会大大降低。

3. HashSet的实现

HashSet实际上是基于HashMap的keySet实现。而keySet实际上又是对HashSet进行封装后的一个“窗口”而已。

4. LinkedHashMap的实现

java.util.LinkedHashMap类是HashMap的一个子类,即继承于它。

对于LinkedHashMap本身,只是增加了两个属性:(LinkedHashMap的)Entry链表头节点对象和accessOrder的布尔值。前者为HashMap维护了一个顺序相关的节点链表,而后者则根据初始化参数确定是维护插入顺序还是访问顺序。

对于LinkedHashMap的Entry节点类,也是继承于HashMap.Entry,增加了before和after引用,维协助维护双向链表。

至于HashMap的其它细节,其实在初步了解了其结构后,都很容易想明白,就不赘述了。HashMap因为查找效率高,通常是Map的默认选择,也是《Thinking in Java》书中提到的“没有特殊需求之必选”。而使用好HashMap,需要注意的主要是扩容重映射的成本和元素对象(key)的hashCode()的意义以及散列冲突带来的影响。

此条目发表在 Java, Java语言, 开发, 计算机技术 分类目录,贴了 , , , 标签。将固定链接加入收藏夹。

发表评论

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

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>