深入分析HashMap

Author Avatar
stormjie 10月 28, 2018
  • 在其它设备中阅读本文章

HashMap大家都会用,说起特点可能也会说出个一二三,但是凭这点想拿offer是远远不能够的,今天我就详细说说这个常用的集合类。

一、HashMap概述

HashMap是一个散列表,它存储的内容是键值对(key-value)映射。

HashMap继承于AbstractMap,实现了Map、Cloneable、java.io.Serializable接口。

HashMap的实现不是同步的,这意味着它不是线程安全的。如果想要线程安全的HashMap,可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。(看过Java并发编程的同学应该很熟悉)

Map map = Collections.synchronizedMap(new HashMap());

它的key、value都可以为null。此外,HashMap中的映射不是有序的。

主要关注点在下表格:

关 注 点 结 论
HashMap是否允许null key和value都允许为null
HashMap是否允许重复数据 key重复会覆盖、value允许重复
HashMap是否有序 无序,特别说明这个无序指的是遍历HashMap的时候,得到的元素的顺序基本不可能是put的顺序
HashMap是否线程安全 非线程安全

二、HashMap的数据结构

先贴一个HashMap定义的成员变量:

//HashMap是基于hash表来实现Map接口的,HashMap维护了下面几个变量:

    //HashMap默认的初始化大小为16
    static final int DEFAULT_INITIAL_CAPACITY = 16;

    //HashMap包含键值对的最大容量为2^30,HashMap的容量一定要是2的整数次幂
    static final int MAXIMUM_CAPACITY = 1 << 30;

    //默认的加载因子为0.75
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    //装载键值对的内部容器Entry数组,长度一定得是2的幂
    transient Entry[] table;

    //HashMap中包含的键值对的个数
    transient int size;

    //HashMap的极限 当键值对的个数达到threshold时,数组table要扩容的
    int threshold;

    //加载因子
    final float loadFactor;

    //HashMap结构上被改变的次数,结构上的改变包括:键值对的大小的改变,修改HashMap的内部结构(比较进行了rehash操作),此属性用来保持fail-fast
    transient volatile int modCount;

HashMap实际上是一个“链表的数组”的数据结构,每个元素存放链表头结点的数组,即数组和链表的结合体。 (在数据结构中,一般称之为“散列表”)

如上图所示,这就是HashMap底层的数据结构。可以发现,HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元,每一个Entry包含一个key-value键值对。

下面我们看一下Entry的实现,Entry<K,V>是HashMap的一个静态内部类

/**
*Entry是HashMap里面承载键值对数据的数据结构,实现了Map接口里面的Entry接口,除了方法recordAccess(HashMap<K,V> m),recordRemoval(HashMap<K,V> m)外,其他方法均为final方法,表示即使是子类也不能覆写这些方法。
*/
static class Entry<K,V> implements Map.Entry<K,V> {
    //键值,被final修饰,表明一旦赋值,不可修改
    final K key;
    //value值
    V value;
    //下一个键值对的引用
    Entry<K,V> next;
    //当前键值对中键值的hash值
    final int hash;

    //构造方法
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
          next = n;
        key = k;
        hash = h;
    }

    public final K getKey() {
        return key;
    }

    public final V getValue() {
        return value;
    }

    //设置value值,返回原来的value值
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    //比较键值对是否equals相等,只有键、值都相等的情况下,才equals相等
    public final boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry e = (Map.Entry)o;
        Object k1 = getKey();
        Object k2 = e.getKey();
        //若k1 == k2(k1,k2引用同一个对象),或者k1.equals(k2)为true时,进而判断value值是否相等
        if (k1 == k2 || (k1 != null && k1.equals(k2))) {
        Object v1 = getValue();
        Object v2 = e.getValue();
        //若v1 == v2(v1,v2引用同一个对象),或者v1.equals(v2)为true时,此时才能说当前的键值对和指定的的对象equals相等
        if (v1 == v2 || (v1 != null && v1.equals(v2)))
            return true;
        }
        //其他均为false
         return false;
    }

    public final int hashCode() {
        return (key==null ? 0 : key.hashCode()) ^
         (value==null ? 0 : value.hashCode());
    }

    public final String toString() {
        return getKey() + "=" + getValue();
    }

    //此方法只有在key已存在的时候调用m.put(key,value)方法时,才会被调用,即覆盖原来key所对应的value值时被调用
    void recordAccess(HashMap<K,V> m) {}
    //此方法在当前键值对被remove时调用
    void recordRemoval(HashMap<K,V> m) {}
}

三、容量(capacity)和负载因子(loadFactor)

简单的说,capacity就是Entry数组的大小,loadFactor就是Entry数组填满程度的最大比例。当Entry数组中的键值对数目(而不是已占用的位置数)大于capacity*loadFactor(即threshold)时就需要扩容,调整Entry数组的大小为当前的2倍。同时,初始化容量的大小也是2的次幂(大于等于设定容量的最小次幂),则Entry数组的大小在扩容前后都将是2的次幂(非常重要,HashMap访问的性能最高,且resize时能带来极大便利)。

默认的capacity为16,loadFactor为0.75,但如果需要优化的话,要考量具体的使用场景。

  • 如果对迭代性能要求高,不要把capacity设置过大,也不要把loadFactor设置过小,否则会导致Entry数组中的空位置过多,浪费性能。

  • 如果对随机访问的性能要求很高的话,不要把loadFactor设置的过大,否则会导致访问时频繁碰撞,时间复杂度向O(n)退化。

  • 如果数据增长很快的话,或数据规模可预知,可以在创建HashMap时主动设置capacity。

四、HashMap的存取实现

HashMap在get和put计算下标时,先对hashCode进行hash操作,然后再通过hash值进一步计算下标,所以我们先看看这个hash方法是如何实现的以及下标的计算过程。

1.hash的实现和定位

作为API的设计者,不能假定用户实现了良好的hashCode方法,所以通常会对hashCode再计算一次hash,以下是hash方法源码:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

前面已经说过,在get和put计算下标时,先对hashCode进行hash操作,然后再通过hash值进一步计算下标,如下图所示:

回顾hash方法的源码可知,hash方法大概的作用就是:高16bit不变,低16bit和高16bit做了一个异或。(两者相等为0,不等为1)

经过hash方法得到的hash值还要通过indexFor方法进一步处理来获取实际的存储位置,以下是indexFor方法源码:

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

因为目前的table长度n为2的次幂,所以计算下标的时候,取模%运算等价于按位与&运算,但是&比%具有更高的效率。

另外,前面说了初始化容量的大小是2的次幂,Entry数组的大小在扩容前后都将是2的次幂,下面说明理由。

看下图,左边两组是数组长度为16(2的4次方),右边两组是数组长度为15。两组的hash值均为8和9,但是很明显,当右边和1110(15二进制-1)按位与的时候,产生了相同的结果,也就是说它们会定位到数组中的同一个位置上去,这就产生了碰撞,8和9会被放到同一个链表上,那么查询的时候就需要遍历这个链表,得到8或者9,这样就降低了查询的效率。同时,我们也可以发现,当数组长度为15的时候,hash值会与14(1110)进行按位与,那么最后一位永远是0,而0001,0011,0101,1001,1011,0111,1101这几个位置永远都不能存放元素了,空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率!

所以说,当数组长度为2的n次幂的时候,不同的key算得得index相同的几率较小,那么数据在数组上分布就比较均匀,也就是说碰撞的几率小,相对的,查询的时候就不用遍历某个位置上的链表,这样查询效率也就较高了。

2.put的实现

把hash方法以及下标计算方法讲完,这部分就简单许多,以下是HashMap的put方法实现:

/**
*将指定的键key,值value放到HashMap中
*/
public V put(K key, V value) {
    //首先判断键key是否为null,若为null,则调用putForNullKey(V v)方法完成put
    if (key == null)
        return putForNullKey(value);
    //程序走到这,说明key不为null了,先调用hash(int)方法,计算key.hashCode的hash值
    int hash = hash(key.hashCode());
    //再调用indexFor(int,int)方法求出此hash值对应在table数组的哪个下标i上 (bucket桶)
    int i = indexFor(hash, table.length);
    //遍历bucket桶上面的链表元素,找出HashMap中是否有相同的key存在,若存在,则替换其value值,返回原来的value值
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        //若元素e.hash值和上面计算的hash值相等,并且(e.key == 入参key,或者入参key equals 相等 e.key),则说明HashMap中存在了和入参相同的key了,执行替换操作
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            //在执行替换操作的时候,调用Entry对象的recordAccess(HashMap<K,V> m)方法,这个上面说过了
            e.recordAccess(this);
            return oldValue;
        }
    }
    //程序走到这,说明原来HashMap中不存在key,则直接将键值对插入即可,由于插入元素,修改了HashMap的结构,因此将modeCount+1
    modCount++;
    //调用addEntry(int,K,V,int)方法进行键值对的插入
    addEntry(hash, key, value, i);
    //由于原来HashMap中不存在key,则不存在替换value值问题,因此返回null
    return null;
}

当key为null时,HashMap是这样进行数据插入的:

//先看看HashMap中原先是否有key为null的键值对存在,若存在,则替换原来的value值;若不存在,则将key为null的键值对插入到Entry数组的第一个位置table[0]
private V putForNullKey(V value) {
    //获取Entry数组的第一个元素:table[0],然后通过e.next进行链表的遍历,若遍历过程中有元素e.key为null,则替换该元素的值
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        //说明原来之前HashMap中就已经存在key问null的键值对了,现在又插入了一个key为null的新元素,则替换掉原来的key为null的value值
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            //在执行替换操作的时候,调用Entry对象的recordAccess(HashMap<K,V> m)方法,这个上面说过了
            e.recordAccess(this);
            return oldValue;
        }
    }
    //程序走到这,说明HashMap中原来没有key为null的键值对,需要直接插入元素,由于插入元素,修改了HashMap的结构,因此将modeCount+1
    modCount++;
    //调用addEntry(int,K,V,int)方法进行键值对的插入,这里将入参hash设置为0,K为null,插入的位置index也为0,说明key为null的元素插入在bucket[0]第一个桶上
    addEntry(0, null, value, 0);
    return null;
}

通过上述源码我们可以清楚知到,HashMap 中可以保存key为null的键值对,且该键值对是唯一的。若再次向其中添加键为null的键值对,将覆盖其原值。此外,如果HashMap中存在键为null的键值对,那么一定在第一个桶中。

下面我们看一看实际进行数据添加的操作addEntry方法:

/**
*将指定的key,value,hash,bucketIndex 插入键值对,若此时size大于极限threshold,则将Entry数组table扩容到原来容量的两倍
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
    //取出原来bucketIndex处的键值对e
    Entry<K,V> e = table[bucketIndex];
    //创建一个新的键值对,使用给定的hash、key、value,并将新键值对的next属性指向e,最后将新键值对放在bucketIndex处
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    //将size+1,若此时size 大于极限threshold,则将Entry数组table扩容到原来容量的两倍
    if (size++ >= threshold)
        //调用resize(int)方法,进行数组的扩容
        resize(2 * table.length);
}

这就是HashMap基本存键值对的操作,其实在JDK1.8版本中,对数据结构做了进一步的优化,引入了红黑树,实际并非这么简单,下图是完整操作:

  1. 判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容;
  2. 根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向6,如果table[i]不为空,转向3;
  3. 判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向4,这里的相同指的是hashCode以及equals;
  4. 判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向5;
  5. 遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;
  6. 插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。
3.get的实现
//获取指定key所对应的value值
public V get(Object key) {
    //若key==null,则直接调用getForNullKey()方法
    if (key == null)
        return getForNullKey();
    //到这说明key != null,先获取key的hash值
    int hash = hash(key.hashCode());
    //在indexFor(int hash,int length)获取key落在Entry数组的哪个bucket桶上,获取该bucket桶上的元素e,进而遍历e的链表,找相对应的key,若找到则返回key所对应的value值,找不到则返回null
    for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) {
        Object k;
        //若元素e.hash == 上面计算的hash值,并且(e.key 和入参key是同一个对象的引用,或者e.key和入参key equals相等),
        //则认为入参key和当前遍历的元素e的key是同一个,返回e的value值
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    //上面遍历了一遍也没有找到,则返回null
    return null;
}

//获取key为null的value值,由上面putForNullKey方法可知,key为null的键值对,被放在了Entry数组table的第一个bucket桶(table[0])
private V getForNullKey() {
    //获取Entry数组table的第一个元素e,从e开始往下遍历,若找到元素e.key 为null的,则直接返回该元素e.value值
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        //找到元素e.key 为null的,则直接返回该元素e.value值
        if (e.key == null)
            return e.value;
    }
    //从table[0]开始,遍历链表一遍,没有找到key为null的,则返回null
    return null;
}

从上面可以看出HashMap中判断key是否相等的条件是hash值相等且equals,提起这个我要引申下,正因为如此,重写equals时也要同时覆盖hashcode,具体可以看这些帖子HashMap中判断两个key是否为同一个key详解HashMap中key是否相等的判断HashMap实现原理及源码分析中第四点

五、HashMap的resize(扩容操作)

当HashMap中的元素越来越多的时候,hash冲突的几率也就越来越高,因为数组的长度是固定的。所以为了提高查询的效率,就要对HashMap的数组进行扩容,数组扩容这个操作也会出现在ArrayList中,这是一个常用的操作,而在HashMap数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是resize

那么HashMap什么时候进行扩容呢?前面讲put操作里有提到,当HashMap中的元素个数超过数组大小*loadFactor时,就会进行数组扩容,loadFactor的默认值为0.75,这是一个折中的取值。也就是说,默认情况下,数组大小为16,那么当HashMap中元素个数超过16*0.75=12(这个值就是代码中的threshold值,也叫做临界值)的时候,就把数组的大小扩展为 2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。

/**
*将HashMap中Entry数组table的容量扩容至新容量newCapacity,数组的扩容不但涉及到数组元素的复制,还要将原数组中的元素rehash到新的数组中,很耗时;如果能预估到放入HashMap中元素的大小,最好使用new HashMap(size)方式创建足够容量的HashMap,避免不必要的数组扩容(rehash操作),提高效率
*/
void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    //如果原数组的大小已经为允许的最大值MAXIMUM_CAPACITY了,则不能进行扩容了,这里仅仅将极限threshold设置为Integer.MAX_VALUE,然后返回
    if (oldCapacity == MAXIMUM_CAPACITY) {
        //将极限threshold设置为Integer.MAX_VALUE
        threshold = Integer.MAX_VALUE;
        return;
    }
    //程序走到这,说明可以进行扩容,先创建容量为newCapacity的新Entry数组newTable
    Entry[] newTable = new Entry[newCapacity];
    //调用tranfer(Entry[] newTable)方法,进行数组元素的移动和rehashing
    transfer(newTable);
    //将新数组newTable赋值给table
    table = newTable;
    //计算极限threshold的最新值
    threshold = (int)(newCapacity * loadFactor);
}

//将原Entry数组table中的所有键值对迁移到新Entry数组newTable上
void transfer(Entry[] newTable) {
    //原数组赋值给src
    Entry[] src = table;
    //新数组长度为newCapacity
    int newCapacity = newTable.length;
    //遍历原数组
    for (int j = 0; j < src.length; j++) {
        //获取原数组中的元素(键值对),赋值给e
        Entry<K,V> e = src[j];
        //若元素e不为null
        if (e != null) {
            //释放旧Entry数组的对象引用(for循环后,旧的Entry数组不再引用任何对象)
            src[j] = null;
            //遍历元素e所对应的bucket桶内的所有元素
            do {
                //获取下一个元素next
                Entry<K,V> next = e.next;
                //重新计算键值对e在新数组newTable中的bucketIndex位置(即rehash操作)
                int i = indexFor(e.hash, newCapacity);
                //标记[1]
                e.next = newTable[i];
                //将当前元素e放入新数组的i位置
                newTable[i] = e;
                //访问下一个Entry链上的元素
                e = next;
            } while (e != null);
        }
    }
}

关于rehash操作,可以看看这篇帖子的第六点Java HashMap工作原理及实现,讲得很形象,助我理解了很多,感谢作者。

六、总结

理解完HashMap我认为需要通过一些面试题来加深印象补缺补漏,来了HashMap面试常问问题HashMap常问面试题整理,这两篇还是挺好的。


其实写这篇HashMap小总结花了我不少时间,源码分析还是比较累的吧。。接下来我可能不能保持一周两更的频率了,学校事多,最近也想做做项目练手,主要还是自己懒吧,有点吃力,不够努力。

参考博文:

Java 8系列之重新认识HashMap

Java 集合系列10之 HashMap详细介绍(源码解析)和使用示例

深入Java集合学习系列:HashMap的实现原理

HashMap 源码解析

Java HashMap工作原理及实现