HashMap详解

HashMap摘要

HashMap应该算是Java程序员使用频率最高的容器类了,它主要用于处理键值映射数据。随着JDK的升级,JDK1.8后对HashMap底层采取了不少优化,例如引入红黑树,改用Node类存放节点等。但HashMap是线程不安全的类,遇到多线程问题时需要改用其他相关线程安全类。

HashMap继承体系

HashMap<K,V>是一个key-value结构,继承自抽象类AbstractMap<K,V>,实现了Map<K,V>以及Cloneable和Serializable接口;Cloneable是一个标记接口,里面没有任何东西,表明类中需要重写clone()方法时必须实现此接口;Serializable也是一个标记接口,表明需要序列化此类对象时必须实现该接口。

类中定义的serialVersionUID是人为定义的一个序列化编号,对于需要序列化的类即实现了Serializable接口的类建议一定加上serialVersionUID的定义,且一定为private static final long类型。下图是HashMap继承图。

HashMap容量

HashMap初始化容量DEFAULT_INITIAL_CAPACITY = 16,默认不写容量时就是16,下列是源码写法。首先,为何初始容量选择16,这个没有太多的解释,经验表明,16应该是大多数开发者最好的选择;其次,为何写成1 << 4,而不是直接写16,这个里面原理就深入了。

当我们在安装了阿里巴巴规范插件的IDEA中定义HashMap时,它会自动提醒我们将容量初始化为2的幂,这样做是为了方便进行位运算,位与运算&比算术运算效率高得多,而位与运算服务于将Key映射到index的算法。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

当我们计算出了Key的Hash值,我们如何将通过Hash值将相应的键均匀分布到HashMap中的位置上呢?HashMap是通过Hash值对容量取模运算的,但由于位于&运算效率大于取模运算,容量取2的幂时使用相应的位与运算和取模运算等价,所以一般使用2的幂作为容量初始值。下列是计算index公式,Length - 1得到的二进制位全是1,与hash位与运算等同于直接取HashCode后几位,具体的取模和位与运算为何等价读者可自行查阅资料。

index = (Length - 1) & hash

若随机取一个数作为初始值,HashMap在底层会直接取到大于等于此值的最小的2的幂。因此,若是准确知道我们需要多少的空间最好自己定义,并定义为2的幂;若不知道具体容量该如何定义,也可以默认不写。

在源码中,我们又看到了下面这行DEFAULT_LOAD_FACTOR = 0.75,装载因子load_factor关乎到扩容机制。我们知道HashMap容量有限,多次插入可能会到满的时候,这时候就要进行扩容了。

resize扩容有两个因素,一是HashMap当前长度capacity,二是负载因子,默认为0.75;当存入的数据大于当前长度乘以负载因子时就要进行扩容。

扩容步骤要分为两步,第一步新建一个容量为之前容量2倍的HashMap数组,第二步进行rehash操作,将原数组所有entry元素重新hash到新的数组。

为何不能直接复制数组而要进行rehash操作呢?这是因为数组容量改变了hash规则也要改变的,hash公式是index = hash & (Length - 1),与不同容量进行位与运算得到index大多数都是不一样的。

static final float DEFAULT_LOAD_FACTOR = 0.75f;

当然,这里的负载因子取0.75也是一个经验值,可以根据自己项目需要自行更改,默认就是0.75,一般不要去修改。

剩下的还有一些关于容量的参数,例如最大容量、转化为红黑树阈值容量(后文会细说为何出现红黑树)、从红黑树转化为链表阈值容量(HashMap具体数据结构后文细说)、最小树形化阈值。

static final int MAXIMUM_CAPACITY = 1 << 30;

static final int TREEIFY_THRESHOLD = 8;

static final int UNTREEIFY_THRESHOLD = 6;

static final int MIN_TREEIFY_CAPACITY = 64;

HashMap数据结构

JDK1.7和JDK1.8发生了一些变化。HashMap主要由数组和链表组成,具体结构如下图所示。在Java7中每个位置叫Entry,Java8中叫Node,每个位置下面还连着链表,当然,Java8后链表超过一定容量(容量为8)就自动转化为红黑树。

以Java8为例,HashMap内部定义了一个Node<K,V>类,就是我们上面说的这些节点,每个Node内部定义了自身的hash值、对应的key、自身的value值、以及对下一个Node的引用,代码如下。HashMap自身定义了一个Node[] table数组,即哈希桶数组。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    HashMap.Node<K, V> next;
}

HashMap中有几个关键字段,用于初始化HashMap默认构造函数。

transient int size;
transient int modCount;
int threshold;            // 所能容纳的key-value对极限
final float loadFactor;  // 负载因子

注意,HashMap中key允许为null,当其为null时,定义hash取0的位置,否则计算相应的hash值,代码如下。

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

HashMap在进行put操作时,先计算出key对应的hash值,根据hash值做位与运算得到对应的index。我们知道,HashMap容量有限,不同的key的hash值会存在碰撞(hash碰撞具体原因查看数据结构中对于Hash的讲解),解决hash碰撞的一个方法就是使用拉链法,具体操作就是将相同hash值的节点形成链表。拉链法形成方式如下图。

其实,put操作较为复杂,具体的实现操作可参照下图。主要有如下步骤:

(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,如果超过,进行扩容。

JDK1.8HashMap中put源码如下。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // (1)tab为空则创建
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (2)计算index,并对null处理
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 节点key存在,直接覆盖value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 判断该链为红黑树
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 链表大于8转换为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // key已经存在覆盖value
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 超过最大容量就扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

注意,在HashMap内部定义了一个modCount值,记录HashMap内部结构变化的次数,而在put方法内部将modCount进行++,原因是一旦对HashMap这类可以Iterator进行遍历的容器来说,当其进行遍历期间若是对这类容器进行了修改(例如put),就会报ConcurrentModificationException。每次迭代时候都会检查expectedmodCount是否和modCount相等,是就返回遍历,否则抛出异常。

而究其原理就是fail-fast(快速失败),它是Java集合的一种机制,若遍历过程中对集合对象内部进行了修改,就是抛出ConcurrentModificationException。

HashMap在形成链表进行插入时,在Java8之前采用头插法,而Java8之后采用尾插法,头插法和尾插法比较如下图,插入顺序为key1-key2-key3。

采用头插法可能是作者认为后来的节点被查找的概率更大,但从Java8之后就改为尾插法了。

究其原因是因为当扩容后,原来顺序为A->B->C的链表,可能变为B->A并且A->B的环形链表,形成Infinite Loop,具体原因可以查看知乎敖丙的HashMap相关文章。

为何Java8之后会出现红黑树呢?由于链表在极端情况下会出现不断堆积的情况,最坏时候会通过O(n)时间复杂度查询链表,而红黑树是相对平衡的二叉树,平均查找时间复杂度是O(logn),因此Java8中链表长度达到8时链表自动转换为红黑树。

HashMap线程安全性问题

HashMap是线程不安全的,它的每个方法都没有涉及到加锁机制,在多线程环境下,很容易造成线程不安全。

可以使用下面三种方式替换为线程安全的类。

Map<String, String> map = new Hashtable<>();

Map<String, String> map = new HashMap<>();
Map<String, String> map1 = Collections.synchronizedMap(map);

Map<String, String> map = new ConcurrentHashMap<>();


end
  • 作者:JJ(联系作者)
  • 发表时间:2021-02-15 13:04
  • 版权声明:自由转载-非商用-非衍生-保持署名(创意共享3.0许可证)
  • 转载声明:如果是转载博主转载的文章,请附上原文链接
  • 公众号转载:请在文末添加作者公众号二维码(公众号二维码见右边,欢迎关注)
  • 评论