1.1 前言
做过 java 开发的朋友们相信都很熟悉 HashMap 这个类,它是一个基于 hashing 原理用于存储 Key-Value 键值对的集合,其中的每一个键也叫做 Entry
,这些键分别存储在一个数组当中,系统会根据 hash
方法来计算出 Key-Value 的存储位置,可以通过 key 快速存取 value。
HashMap 基于 hashing 原理,当我们将一个键值对(Key-Value) 传入 put
方法时,它将调用这个 key 的 hashcode
方法计算出 key 的 hashcode 值,然后根据这个 hashcode 值来定位其存放数组的位置来存储对象(HashMap 使用链表来解决碰撞问题,当其发生碰撞了,对象将会存储在链表的下一个节点中,在链表的每个节点中存储 Entry
对象,在 JDK 1.8+ 中,当链表的节点个数超过一定值时会转为红黑树来进行存储),当通过 get
方法传入一个 key 来获取其对应的值时,也是先通过 key 的 hashcode
方法来定位其存储在数组的位置,然后通过键对象的 eqauls
方法找到对应的 value 值。接下来让我们看看其内部的一些实现细节。(PS:以下代码分析都是基于 JDK 1.8
)
1.2 为什么容量始终是 2 的整数次幂
因为获取 key 在数组中对应的下标是通过 key 的哈希值与数组的长度减一进行与运算来确定的(tab[(n - 1) & hash]
)。当数组的长度 n 为 2 的整数次幂,这样进行 n - 1 运算后,之前为 1 的位后面全是 1 ,这样就能保证 (n - 1) & hash
后相应位的值既可能是 1 又可能是 0 ,这完全取决于 key 的哈希值,这样就能保证散列的均匀,同时与运算(位运算)效率高。如果数组的长度 n 不是 2 的整数次幂,会造成更多的 hash 冲突。HashMap 提供了如下四个重载的构造方法来满足不同的使用场景:
- 无参构造:
HashMap()
,使用该方法表示全部使用 HashMap 的默认配置参数 - 指定容量初始值构造:
HashMap(int initialCapacity)
,在初始化 HashMap 时指定其容量大小 - 指定容量初始值和扩容因子构造:
HashMap(int initialCapacity, float loadFactor)
,使用自定义初始化容量和扩容因子 - 通过
Map
来构造 HashMap:HashMap(Map<? extends K, ? extends V> m)
,使用默认的扩容因子,其容量大小有传入的Map
大小来决定