大师网-带你快速走向大师之路 解决你在学习过程中的疑惑,带你快速进入大师之门。节省时间,提升效率

用好HashMap,只需看这里!

Map是映射表的实现,是关联数组,维护着键与值的关联关系,因此可以根据键找到对应的值。


Java中有几种不同的Map实现,体现了各自不同的优势,或者是注重查找性能的HashMap、或者注重线程安全的ConcurrentHashMap,亦或Key有序排列的TreeMap等等。

而本节要讲的正是HashMap,是基于散列表的实现,插入和查询“键值对”操作具有近似O(1)的时间复杂度,并提供了通过调整容量负载因子的手段来优化Map的性能。

HashMap的实现是数组+链表,很是简单,本文就不够多赘述,而是侧重从工程实践出发,陈述些HashMap使用的注意点或容易忽视且容易想当然的出错点。

null的处理

编程中,最长见的异常,就有NPE(NullPointerException ),那么HashMap是如何处理key或者value为null的情况呢?

1. Key为null

在HashMap中 ,Key是用来定位数组索引的,若Key为Null,则索引为0,也就是说键值对会放到数组的第一个桶位,若被占据,则链表链接,插入的逻辑和非null一模一样。

2. value为null

插入其实就是寻找位置的过程,此过程value不起任何作用。但是如果使用putIfAbsent()(JDK1.8之后)方法,就有需要注意的地方了。如果仅从字面上理解,可能会认为,如果通过key查找不到相等的元素,就插入新元素,反之,则不插入。其实不然,此方法解读应该是:元素不存在则作为新元素插入,当元素存在但是value==null时,也替换value值。

    if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
    }

定位算法

HashMap中数组下标的计算并不是通过hash%length,而是(length - 1) & hash(两个数与计算,最终的结果肯定小于或者等于最小的那个值,最后肯定不越界)。这种方式明细不直观,不符合常规思维,难道是这种方式有更优的性能吗?

不妨用JMH微机准测试下:

 static int length = 32;
    @Benchmark
    public void wellHelloThere() {
        int i = RandomUtils.nextInt() % length;
    }
    @Benchmark
    public void wellHelloThere1() {
        int i = RandomUtils.nextInt() & (length - 1);
    }
    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                .include(JMHTest.class.getSimpleName())
                .forks(1)
                .mode(Mode.Throughput)
                .warmupIterations(2)
                .measurementIterations(2)
                .build();
        new Runner(opt).run();
    }

我的机器上执行,吞吐量ops几乎相等,这几乎可以排除性能的原因,那到底有何用意?下面详细分析。

数组扩容

HashMap有两个重要的属性,容量和负载因子。容量为数组的长度,而负载因子是一个衡量什么时候数组扩容的指标,默认值为0.75。

数组容量负载因子计算出的扩容阈值Threshold是最终的度量,当Map中元素数量大于Threshold时,此时HashMap需要实例化新数组(容量为原来2倍)然后把老Map的元素放到新的Map中,可以肯定,这个过程是整个HashMap中最耗时的,涉及所有元素的位置调整。

元素转移最简单的思路可能就是将所有的元素重新调用put方法,这会重新hash计算,定位桶位,遍历链表,有严重的性能问题,那么实际的操作又是怎样的呢?

扩容实现

HashMap底层数组长度始终是2的次方,不管你初始化设置数组容量为多少,例如:赋值为7,实际则是8,赋值为17,则为32。

下图展示扩容重新下标计算:


所有,只需要把原数组每个节点的链表按照高位是否为1进行拆分为2个链表,高位为1的链接到新的位置,也就是(原位置+原数组长度),为0的链接到新数组中原来的位置。

从而得出结论,(length - 1) & hash的算法选择是为了降低扩容时的性能损耗考虑的。

初始容量和负载因子对性能的影响

初始容量

当HashMap元素数量达到阈值,rehashing就会发生,频繁的发生会造成很大的开销。选择合适的初始容量将会很大程度上减少rehashing的发生,会改善HashMap的写入性能。

凡是有两面性,如果容量很大,且元素很少时,迭代操作将会产生额外的开销,所以当需要经常的进行迭代操作,就需要节点分布适当的紧促了,也就是说初始容量不能过大。

负载因子

过大的负载因子会减少空间的使用,但会造成查询(包括get和put)的耗时增加,默认值0.75是考虑了空间成本和时间成本后的一种折中方案,是一权衡。如果过小,也会造成迭代操作的消耗增加。

线程是否安全

HashMap是非线程安全的,多线程访问时如果有一个线程是写操作,则需要进行外部同步操作,否则其他线程将观察到对象内部的不一致状态,或者写入操作根本就不能被其他线程看见。

在多线程环境下,应该使用同步的Map,最好使用ConcurrentHashMap,而不是包装 Collections.synchronizedMap(new HashMap(...))以及Hashtable。

fail-fast

如同其他的非并发容器一样,HashMap的遍历也是快速失败机制,当iterator被创建后,任何对于底层数据结构的改变(put,remove)都可能会导致 ConcurrentModificationException异常的产生,由于没有使用同步,所有异常并不是一定会产生,这只是提供一种定位bug的参考。

与Hashtable区别

Hashtable是线程安全的,而HashMap并不是,在单线程环境下HashMap性能更优,毕竟锁是有开销的。

Hashtable不允许key或者value为null,HashMap则可以。

以上大概就是实际使用中需要了解,也需要注意的点了,为了代码的健壮,理解原理还是必要的。