严格来说,Map 并非集合,而是一个键值对的映射。但是 Map 却可以从某些角度被当作集合。Map 当中,最常用的就是 HashMap ,其余几种实现基本都和 HashMap 有关系或者原理一致。
注:本文基于 jdk_1.8.0_144
HashMap 的内部元素是由一个数组存放,数组类型为 HashMap.Node ,是一个链表。其中,元素所有数组的位置,由 Key 的 hashcode 决定。当然,数组长度有限,hash 值也会有碰撞,如果产生 hash 碰撞,则存于同一个数组下标中,并添加至链表。也就是说,HashMap 的内部实现是,数组 + 链表。另外,自 JDK1.8 ,对于同一个数组下标位置,如果链表长度过长,会将链表的二叉树转成红黑树(平衡二叉树)。即:
数组 + 链表 + 红黑树
主要成员变量如下:
- // 默认初始容量16
- static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
- // 最大容量
- static final int MAXIMUM_CAPACITY = 1 << 30;
- // 默认负载因子0.75
- static final float DEFAULT_LOAD_FACTOR = 0.75f;
- // 链表转成红黑树的长度临界值
- static final int TREEIFY_THRESHOLD = 8;
- // 红黑树转成链表的长度临界值
- static final int UNTREEIFY_THRESHOLD = 6;
- // 转化红黑树的最小数组长度,数组长度太小不会转化红黑树的
- static final int MIN_TREEIFY_CAPACITY = 64;
- // 存放链表的数组
- transient Node < K,
- V > [] table;
- // 键值对数量
- transient int size;
- // 修改次数
- transient int modCount;
- // 扩容阀值 capacity * load factor
- int threshold;
- // 负载因子,初始化未赋值则使用 DEFAULT_LOAD_FACTOR
- final float loadFactor;
其中,Node 的结构如下,是一个带有 hash 值及键值对的链表:
- static class Node<K,V> implements Map.Entry<K,V> {
- final int hash;
- final K key;
- V value;
- Node<K,V> next;
- }
当链表转化成红黑对的时候,结构如下,LinkedHashMap.Entry 是上面 Node 的子类:
- static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
- TreeNode<K,V> parent; // red-black tree links
- TreeNode<K,V> left;
- TreeNode<K,V> right;
- TreeNode<K,V> prev; // needed to unlink next upon deletion
- boolean red;
- }
默认构造器会在初始化的时候,指定加载因子为默认加载因子 0.75,容量为 0。
- public HashMap() {
- this.loadFactor = DEFAULT_LOAD_FACTOR;
- }
当然,一般我们建议在初始化的时候,能根据情况指定初始容量。
- public HashMap(int initialCapacity) {
- this(initialCapacity, DEFAULT_LOAD_FACTOR);
- }
- public HashMap(int initialCapacity, float loadFactor) {
- if (initialCapacity < 0)
- throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
- if (initialCapacity > MAXIMUM_CAPACITY)
- initialCapacity = MAXIMUM_CAPACITY;
- if (loadFactor <= 0 || Float.isNaN(loadFactor))
- throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
- this.loadFactor = loadFactor;
- this.threshold = tableSizeFor(initialCapacity);
- }
可以看出,如果指定了初始容量,会进行容量的重计算,保证初始容量是 2 的 N 次方。
- static final int tableSizeFor(int cap) {
- int n = cap - 1;
- n |= n >>> 1;
- n |= n >>> 2;
- n |= n >>> 4;
- n |= n >>> 8;
- n |= n >>> 16;
- return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY: n + 1;
- }
那么这个算法是怎么保证得到的是 2 的 N 次方的呢?
- 01xxxxxx | 001xxxxx = 011xxxxx
,直至得到
- 011xxxxx | 00011xxx = 01111xxx
- 01111111
HashMap 在进行 put 和 get 操作时,是把键值对放至 table 数组的特定下标位。
其中索引位置是这样计算出来的:
- int n = table.length
- int index = (n - 1) & hash
其中,hash 是将 key 通过下面的方法算出来的。
- static final int hash(Object key) {
- int h;
- return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
- }
那么问题来了,hash 值为什么要这样算?索引计算到底表示什么意义?
通过上面我们知道,HashMap 的数组容量大小始终是 2 的 N 次方。n 表示的数组的长度,所以 n - 1 得到的二进制,后面的值一定是连续的 1 ,在与 hash 做与运算之后,得到的实际是 hash 对 n 的取余。
如,某数对 16 取余:
0100 1110 1101 0011
0000 0000 0000 1111
——————————
0000 0000 0000 0011
所以,
。当然,这是有前提的,n 必须为 2 的 N 次方。
- (n - 1) & hash == hash % n
我们明明可以直接用 key.hashCode() ,为什么还要做个异或操作呢?
由于 HashMap 的 Key 的 hashCode() 方法是不确定的,所以,某些自定义类型的 Key ,有可能会得到一些尾数具有重复性的 hashcode 。这时候,将 hashcode 的高 16 位与低 16 位进行异或,就会减少 hash 碰撞。
借用一张来自美团的图,put 流程如下:
还是对照下源码来对照理解吧。
- public V put(K key, V value) {
- return putVal(hash(key), key, value, false, true);
- }
- /**
- * put 方法具体调用
- *
- * @param key 计算出来的 hash 值
- * @param key key
- * @param value value
- * @param onlyIfAbsent 如果true,则不替换原来的值
- * @param evict LinkedHashMap 才用到.
- * @return 返回 null 或者替换前的值
- */
- final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
- Node < K,
- V > [] tab;
- Node < K,
- V > p;
- int n,
- i;
- // table 为空或者长度为0,进行扩容操作
- if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;
- // 如果当前索引位没有值,则添加新链表
- if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);
- // 如果当前索引有值了,说明hash碰撞了
- else {
- Node < K,
- V > e;
- K k;
- // p 是该索引位置的链表的第一个节点
- // hash 值相等,key 又相等,说明是同一个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);
- // 不是红黑树,key 之前又不存在
- else {
- for (int binCount = 0;; ++binCount) {
- // p.next == null 说明是最后一个节点了
- if ((e = p.next) == null) {
- p.next = newNode(hash, key, value, null);
- // 链表长度大于8,转化成红黑树操作
- // 如果tab.length 达不到 MIN_TREEIFY_CAPACITY,是不会转化的
- // -1 是因为上面已经排除了首节点了
- if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash);
- break;
- }
- // 在非首节点中已存在,则替换value
- if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break;
- p = e;
- }
- }
- // e 是上面操作,得到的key存在的那个节点,不为null则说明存在,已存在则替换value
- if (e != null) { // existing mapping for key
- V oldValue = e.value;
- if (!onlyIfAbsent || oldValue == null) e.value = value;
- afterNodeAccess(e);
- return oldValue;
- }
- }++modCount;
- //增加size,并判断是否要扩容,size 大于扩容阀值,则要扩容
- if (++size > threshold) resize();
- //这个方法在LinkedHashMap中有实现
- afterNodeInsertion(evict);
- return null;
- }
注:红黑树本文不讨论是怎么实现的,头大。
- public V get(Object key) {
- Node<K,V> e;
- return (e = getNode(hash(key), key)) == null ? null : e.value;
- }
- /**
- * get 方法具体调用
- *
- * @param hash key 的 hash 值
- * @param key key
- * @return null 或者 key 所在的节点
- */
- final Node<K,V> getNode(int hash, Object key) {
- Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
- // 数组有值且指定下标位有值,这样才有可能存在,否则就返回null
- if ((tab = table) != null && (n = tab.length) > 0 &&
- (first = tab[(n - 1) & hash]) != null) {
- // 首节点key就对了
- if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
- return first;
- if ((e = first.next) != null) {
- // 如果是红黑树,则从红黑对查找
- if (first instanceof TreeNode)
- return ((TreeNode<K,V>)first).getTreeNode(hash, key);
- // 遍历链表所有节点查找
- do {
- if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
- return e;
- } while ((e = e.next) != null);
- }
- }
- return null;
- }
这里面有个不大不小的坑,如果 key 的设计和使用不当,会引起不必要的 bug:在查找数据的时候,是直接去指定下标进行查找的,如果当前索引查找不到,则返回结果为 null 。
看起来好像没毛病,那么下面这种情况呢?
- // hashcode 有问题的类
- public class User {
- private String username;
- private Integer age;
- @Override public int hashCode() {
- return age;
- }
- }
- // 测试 key 的 hash 会变
- public class Test {
- public static void main(String[] args) {
- Map < User,
- String > testMap = new HashMap < User,
- String > ();
- User user = new User();
- user.setUsername("Tom");
- user.setAge(18);
- testMap.put(user, user.getUsername() + " is a good child");
- System.out.println("exists : " + testMap.get(user));
- user.setAge(22);
- System.out.println("exists : " + testMap.get(user));
- }
- }
输出结果很明显,同一个 key ,后来查找不到了:
exists : Tom is a good child
exists : null
- final Node < K,
- V > [] resize() {
- // 旧数据的备份
- Node < K,
- V > [] oldTab = table;
- int oldCap = (oldTab == null) ? 0 : oldTab.length;
- int oldThr = threshold;
- int newCap,
- newThr = 0;
- // 新数组长度与扩阀值的计算
- if (oldCap > 0) {
- // 数组长度不得大于定义的最大值
- if (oldCap >= MAXIMUM_CAPACITY) {
- threshold = Integer.MAX_VALUE;
- return oldTab;
- }
- // 扩容2倍
- else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold
- } else if (oldThr > 0) // initial capacity was placed in threshold
- newCap = oldThr;
- else { // zero initial threshold signifies using defaults
- newCap = DEFAULT_INITIAL_CAPACITY;
- // 扩容阀值是 数组长度 * 负载因子
- newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
- }
- if (newThr == 0) {
- // 扩容阀值是 数组长度 * 负载因子
- float ft = (float) newCap * loadFactor;
- newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft: Integer.MAX_VALUE);
- }
- // 至此计算出了新的扩容阀值和新数组长度
- threshold = newThr;
- //索引重排部分
- @SuppressWarnings({
- "rawtypes",
- "unchecked"
- }) Node < K,
- V > [] newTab = (Node < K, V > []) new Node[newCap];
- table = newTab;
- if (oldTab != null) {
- // 遍历数组
- for (int j = 0; j < oldCap; ++j) {
- Node < K,
- V > e;
- if ((e = oldTab[j]) != null) {
- // 释放旧引用
- oldTab[j] = null;
- // 链表只有一个节点,直接找到索引位置
- if (e.next == null) newTab[e.hash & (newCap - 1)] = e;
- // 红黑树的特殊处理,不讨论
- else if (e instanceof TreeNode)((TreeNode < K, V > ) e).split(this, newTab, j, oldCap);
- // 链表有多个节点
- else { // preserve order
- Node < K,
- V > loHead = null,
- loTail = null;
- Node < K,
- V > hiHead = null,
- hiTail = null;
- Node < K,
- V > next;
- // 遍历链表的所有节点
- do {
- next = e.next;
- // if 和 else 将原一个链表拆分为两个链表,此处是精髓,下面详解
- if ((e.hash & oldCap) == 0) {
- if (loTail == null) loHead = e;
- else loTail.next = e;
- loTail = e;
- } else {
- if (hiTail == null) hiHead = e;
- else hiTail.next = e;
- hiTail = e;
- }
- } while (( e = next ) != null);
- // 一个链表保持原来的索引位置
- if (loTail != null) {
- loTail.next = null;
- newTab[j] = loHead;
- }
- // 一个链表放到 j + oldCap 位置
- if (hiTail != null) {
- hiTail.next = null;
- newTab[j + oldCap] = hiHead;
- }
- }
- }
- }
- }
- return newTab;
- }
前文说的下面几点很重要:
对于链表只有一个节点的情况,直接查找索引位置重定位就可以了;而如果链表有多个节点的话,难道所有的节点都重新计算一下索引位置吗?并不是这样的,按照源码可以看出是这样子的:
,重组一个新链表 A
- (e.hash & oldCap) == 0
,再组一个新链表 B
- (e.hash & oldCap) != 0
那么问题来了,为什么一个链表要拆成两个?为什么索引位置只有这两个位置,而不需要全部重新计算?通过上面说的几点可以解答:( n 指扩容前数组大小)
时,说明原来的 hash 的低 N 位上的二进制数字是 0 ,所以索引位置不变;同理,
- (e.hash & oldCap) == 0
,说明原来的 hash 的低 N 位上的数字是 1 ,新索引位置要加 oldCap 了
- (e.hash & oldCap) != 0
HashMap 是个非线程安全的类,所以,在多线程情况下,应尽量避免直接使用 HashMap ,换成 ConcurrentHashMap 或者
。为什么说 HashMap 非线程安全呢?
- Collections.synchronizedMap(hashmap)
参考 : 疫苗:JAVA HASHMAP 的死循环
其实,这个问题在 JDK1.8 已经被修复了 。死循环的原因是 resize() 时链表的倒序引起的,但是在 JDK1.8 中,插入元素并会再插入链表头部了,resize() 时也不会倒排了。
举个例子,在上述的 put 操作 部分,有一行源码如下:
- tab[i] = newNode(hash, key, value, null);
比如,两个线程同时走到这里,分别执行此行代码,就会有一个线程的数据丢了。
关于 modCount ,之前的一篇文章中有提过,参考这里: modCount 是干什么的
在 Map 中也有同样的机制,在进行某些操作的时候,会检查 modCount 。如果 modCount 与预期不一样,就会抛
。
- ConcurrentModificationException
所以,如果同时有两个线程操作同一个 HashMap ,一个线程在遍历,一个线程在 put 。这个时候就有可能导致 modCount 校验不通过,从而引起异常。这显然不是我们想要的结果,不符合我们的预期。
- 数组 + 链表 + 红黑树
- Collections.synchronizedMap
来源: https://juejin.im/entry/5a387bca5188251fbd33bd79