原文出处：Java8 系列之重新认识 HashMap

摘要

HashMap 是 Java 程序员使用频率最高的用于映射 (键值对) 处理的数据类型。随着 JDK（Java Developmet Kit）版本的更新，JDK1.8 对 HashMap 底层的实现进行了优化，例如引入红黑树的数据结构和扩容的优化等。本文结合 JDK1.7 和 JDK1.8 的区别，深入探讨 HashMap 的结构实现和功能原理。

 

简介

Java 为数据结构中的映射定义了一个接口 java.util.Map，此接口主要有四个常用的实现类，分别是 HashMap、Hashtable、LinkedHashMap 和 TreeMap，类继承关系如下图所示：

通过观测测试结果可知，JDK1.8 的性能要高于 JDK1.7 15% 以上，在某些 size 的区域上，甚至高于 100%。由于 Hash 算法较均匀，JDK1.8 引入的红黑树效果不明显，下面我们看看 Hash 不均匀的的情况。

Hash 极不均匀的情况

假设我们又一个非常差的 Key，它们所有的实例都返回相同的 hashCode 值。这是使用 HashMap 最坏的情况。代码修改如下：

class Key implements Comparable {

    //...

    @Override
    public int hashCode() {
        return 1;
    }
}

仍然执行 main 方法，得出的结果如下表所示：

从表中结果中可知，随着 size 的变大，JDK1.7 的花费时间是增长的趋势，而 JDK1.8 是明显的降低趋势，并且呈现对数增长稳定。当一个链表太长的时候，HashMap 会动态的将它替换成一个红黑树，这话的话会将时间复杂度从 O(n) 降为 O(logn)。hash 算法均匀和不均匀所花费的时间明显也不相同，这两种情况的相对比较，可以说明一个好的 hash 算法的重要性。

      测试环境：处理器为 2.2 GHz Intel Core i7，内存为 16 GB 1600 MHz DDR3，SSD 硬盘，使用默认的 JVM 参数，运行在 64 位的 OS X 10.10.1 上。

小结

(1) 扩容是一个特别耗性能的操作，所以当程序员在使用 HashMap 的时候，估算 map 的大小，初始化的时候给一个大致的数值，避免 map 进行频繁的扩容。

(2) 负载因子是可以修改的，也可以大于 1，但是建议不要轻易修改，除非情况非常特殊。

(3) HashMap 是线程不安全的，不要在并发的环境中同时操作 HashMap，建议使用 ConcurrentHashMap。

(4) JDK1.8 引入红黑树大程度优化了 HashMap 的性能。

(5) 还没升级 JDK1.8 的，现在开始升级吧。HashMap 的性能提升仅仅是 JDK1.8 的冰山一角。

参考

1. JDK1.7&JDK1.8 源码。
2. CSDN 博客频道，HashMap 多线程死循环问题，2014。
3. 红黑联盟，Java 类集框架之 HashMap(JDK1.8) 源码剖析，2015。
4. CSDN 博客频道， 教你初步了解红黑树，2010。
5. Java Code Geeks，HashMap performance improvements in Java 8，2014。
6. Importnew，危险！在 HashMap 中将可变对象用作 Key，2014。
7. CSDN 博客频道，为什么一般 hashtable 的桶数会取一个素数，2013。