Java容器_HashMap源码分析(6)

数据结构

Java 8 之后,HashMap 由数组、链表、红黑树实现

HashMap数据结构
HashMap数据结构

添加一个键值对,首先是计算 key 对应的 hash 值,即确定其在数组中插入的位置,若发生哈希碰撞,则通过链地址法将冲突位置的元素保存在链表中,若冲突元素个数大于了 8,则改为红黑树保存,但如果数组长度小于 64 则不会建树,而是通过扩容来解决哈希冲突,见 treeifyBin 方法

HashMap 数组的初始容量是一个重要的性能指标,若插入的数据超过了数组当前的扩容临界值,则会通过 rehash 操作扩容到原来的两倍,所以初始容量不能设置得太小,防止频繁扩容,但也不能设置得过大,导致占用太多空间且遍历费时,默认取的是 16

加载因子则是另一个重要的性能指标,其决定了数组扩容的临界值,默认取的是 0.75,加载因子越大,数组被填得越满,空间利用率越高,但冲突几率变大,为了减小冲突,所以需要对数组进行扩容,把所有元素 rehash 后再保存到扩容后的数组中,所以扩容操作非常耗时,在源码中有以下注释

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
/*
 * Ideally, under random hashCodes, the frequency of
 * nodes in bins follows a Poisson distribution
 * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
 * parameter of about 0.5 on average for the default resizing
 * threshold of 0.75, although with a large variance because of
 * resizing granularity. Ignoring variance, the expected
 * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
 * factorial(k)). The first values are:
 * 0:    0.60653066
 * 1:    0.30326533
 * 2:    0.07581633
 * 3:    0.01263606
 * 4:    0.00157952
 * 5:    0.00015795
 * 6:    0.00001316
 * 7:    0.00000094
 * 8:    0.00000006
 * more: less than 1 in ten million
 */

HashMap 的 hash 方法使用了 hashCode,在理想情况下,同一哈希值出现冲突的次数遵循泊松分布,可以看到,将加载因子设置为 0.75 ,同一哈希值出现 8 次冲突的概率已经非常小了,这也是为什么设计为只有当链表长度大于 8 时才转换为红黑树

hash 方法

直接使用了 hashCode 方法返回的哈希值

1
2
3
4
5
static final int hash(Object key) {
  int h;
  //意外收获,key可以为null, 且存储在桶数组的0索引处
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

HashMap 对于非 null 的 key,首先获取其 hashCode 方法返回的 32 位 int 哈希值,即对应 40 多亿的映射空间,但不能直接构建一个这么长的数组,需要先进行取模运算,即 hash % n ,为了提高效率,HashMap 使用的是位运算操作 hash & (n - 1)

对一个十进制数取余 $2^n$,可以将其对应的二进制数右移 n 位,移出的 n 位即为余数,例如, 14 % 8 = 6,14 的二进制数为 1110,8 等于 $2^3$ ,所以将 1110 右移 3 位,移出的 110 对应的十进制即为余数 6,而 8 - 1 的 二进制为 0111,刚好为 n 位的低位掩码,若跟其做按位与操作,即可以将高于 n 的位全部置零,而低 n 位保留,即 14 & (8 - 1) 对应 1110 & 0111 得 110 余数 7

所以取余 $2^n$ ,可以转换为与 $2^n-1$ 进行按位与运算,结果即为余数

1
2
3
            hash = 1111 1111 1111 1111 1010 1111 1010 1100
         len - 1 = 0000 0000 0000 0000 0000 0000 0000 1111
hash & (len - 1) = 0000 0000 0000 0000 0000 0000 0000 1100 = 12

这也是为什么要将 HashMap 的桶数组长度 len 设为 $2^n$ ,默认 len 为 16,即使指定了非 $2^n$ 大小的容量,HashMap 也会将容量设置为离指定容量最近的 $2^n$ 大小,在构造方法中可以看到相关的算法

但若直接让 hashCode 和 len - 1 进行按位与操作,hash 的高位信息是丢失的,所以需要对 hash 值做扰动处理,让高低位都能参与到计算,防止出现哈希值的高位变化很大而低位变化很小,取余后发生碰撞的情况,hash 方法对 hashCode 做的扰动操作是将高 16 位和低 16 位进行异或

1
2
3
4
 h = key.hashCode() = 1111 1111 1111 1111 0101 0000 0101 0011
                  h = 1111 1111 1111 1111 0101 0000 0101 0011
           h >>> 16 = 0000 0000 0000 0000 1111 1111 1111 1111
hash = h ^ (h>>>16) = 1111 1111 1111 1111 1010 1111 1010 1100

对 hash 方法的返回值做取模操作在增删查等方法中都能见到,都是进行的 hash & (n - 1) 操作,n 为数组的长度,hash 为 hash 方法返回的哈希值,例如 get 方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
//返回指定的key的value,若value为null,则返回null
public V get(Object key) {
  Node<K,V> e;
  //hash(Object key)方法返回key对应的哈希值
  return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
	//...(n - 1) & hash...
  //省略其他的代码...
}

属性和构造方法

静态属性

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
//数组默认初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认16
//数组最大容量, 若指定的初始容量超过该最大容量,则还是设置为该最大容量
//最大容量必须是2的倍数,1<<30为2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的加载因子
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;

静态内部结点类

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
//HashMap的key-value结点类
static class Node<K,V> implements Map.Entry<K,V> {
  final int hash;
  final K key;
  V value;
  Node<K,V> next;
  Node(int hash, K key, V value, Node<K,V> next) {
    //属性赋值...
  }
	//get、set、hashCode、toString方法
  public final boolean equals(Object o) {
    if (o == this) return true;
    if (o instanceof Map.Entry) {
      Map.Entry<?,?> e = (Map.Entry<?,?>)o;
      //这里使用了java7引入的Objects工具类
      if (Objects.equals(key, e.getKey()) &&
          Objects.equals(value, e.getValue()))
        return true;
    }
    return false;
  }
}

属性

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
//保存键值对的桶数组
transient Node<K,V>[] table;
//键值对缓存
transient Set<Map.Entry<K,V>> entrySet;
//键值对的实际个数
transient int size;
//HashMap被修改结构的次数,用作迭代器的fail-fast机制中
transient int modCount;
//扩容的临界值,等于capacity * load factor
int threshold;
//加载因子
final float loadFactor;

构造方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public HashMap() {
  this.loadFactor = DEFAULT_LOAD_FACTOR;
}
public HashMap(int initialCapacity) {
  this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//初始容量和加载因子
public HashMap(int initialCapacity, float loadFactor) {
  //检测initialCapacity、loadFactor是否在允许范围中,省略代码...
  this.loadFactor = loadFactor;
  this.threshold = tableSizeFor(initialCapacity);
  //其实此时threshold并不是临界值的语意而是指定的容量,在resize扩容方法中会被重新赋值
  //这里为什么不是
  //this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;
  //我没有搞懂
}

通过 tableSizeFor 方法找到与指定的 initialCapacity 最接近的 $2^n$ 数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
static final int tableSizeFor(int cap) {
  int n = cap - 1; //-1是防止cap已经是2^n数
  //若n=0,则移位后还是0,最后+1得1
  //对于不等于0的n,则对应二进制总会有一位是1
  //从最高位的1开始,将所有低位都置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;
}

例如将 cap 指定为 10,即 …0 1001,执行 n |= n >>> 1 操作后变为 …0 1101,继续操作变为 …0 1111,最后 +1 得到 …1 0000 即 16

在构造方法中并没有对桶数组 table 做初始化,table 的初始化被放到了 resize 方法中,延迟初始化

resize 扩容

resize 方法有两种情况,初始化 table 桶数组、数组中元素个数超过 threshold 时进行扩容

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
final Node<K,V>[] resize() {
  Node<K,V>[] oldTab = table;
  int oldCap = (oldTab == null) ? 0 : oldTab.length;
  int oldThr = threshold;
  int newCap, newThr = 0;
  //table中有值,即对应扩容的情况
  if (oldCap > 0) {
    if (oldCap >= MAXIMUM_CAPACITY) {
      threshold = Integer.MAX_VALUE;
      return oldTab;
    }
    //若没有超过最大值,则扩容到原来的两倍,oldCap << 1,且扩容后的大小不能超过最大值
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
             //大于默认容量16的情况
             oldCap >= DEFAULT_INITIAL_CAPACITY)
      newThr = oldThr << 1; //threshold也相应地扩大一倍
  }
  
  //以下对应table初始化的情况
  //若构造时指定了initialCapacity,则用threshold作为table的容量
  else if (oldThr > 0) // initial capacity was placed in threshold
    newCap = oldThr;
  //若构造时没有指定initialCapacity,threshold的值为0,则table容量设为默认值16
  else {               
    newCap = DEFAULT_INITIAL_CAPACITY;
    //扩容临界值=加载因子*当前容量
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  }
  //计算指定了initialCapacity的情况的threshold
  if (newThr == 0) {
    float ft = (float)newCap * loadFactor;
    //判断ft是否超过最大值,若超过了则置为最大值
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
              (int)ft : Integer.MAX_VALUE);
  }
  //更新threshold
  threshold = newThr;
  
  //以下是新建table,即不管初始化还是扩容都会新建table
  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  table = newTab;
  //将table中原来的值复制到新的table
  if (oldTab != null) {
    //遍历table数组
    for (int j = 0; j < oldCap; ++j) {
      Node<K,V> e;
      if ((e = oldTab[j]) != null) {
        //table保存的是Node的引用,oldTab[j]=null只是清除了旧的table的引用
        //真正的node节点还在,现在正被e指向
        oldTab[j] = null;
        //对于没有冲突的情况,直接将其放到新表的目标位置
        if (e.next == null)
          newTab[e.hash & (newCap - 1)] = e;
        //若是由红黑树保存的冲突结点,则拆分红黑树
        else if (e instanceof TreeNode)
          //split暂时省略
          ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        //若是由链表保存的,则拆分链表
        else {
          //定义了lo和hi两个链表
          Node<K,V> loHead = null, loTail = null;
          Node<K,V> hiHead = null, hiTail = null;
          Node<K,V> next;
          //do while顺序遍历链表中的节点
          do {
            next = e.next;
            //重点拆分逻辑(e.hash & oldCap) == 0
            if ((e.hash & oldCap) == 0) {
              //插入lo链表
              if (loTail == null)
                loHead = e;
              else
                loTail.next = e;
              loTail = e;
            }
            else {
              //插入hi链表
              if (hiTail == null)
                hiHead = e;
              else
                hiTail.next = e;
              hiTail = e;
            }
          } while ((e = next) != null);
          //若lo链表非空,则将lo链表放到新的table的j位置 
          if (loTail != null) {
            loTail.next = null;
            newTab[j] = loHead;
          }
          //若hi链表非空,则将hi链表放到新的table的j + oldCap位置 
          if (hiTail != null) {
            hiTail.next = null;
            newTab[j + oldCap] = hiHead;
          }
        }
      }
    }
  }
  return newTab;
}

oldCap 为 $2^n$ ,newCap 为 oldCap 的两倍即 $2^{n+1}$ ,对 hash 值的取模 hash & (len - 1) 其实就是取 hash 的低 n 位,扩大一倍后 hash 取模即取低 n+1 位

例如,oldCap = 16,hash 对 16 取模后为 xxxx,扩大一倍后,hash 取模为 1xxxx 或 0xxxx,而 0xxxx 与扩容前相同,1xxxx 为扩容前的 xxxx + 10000,即 xxxx + oldCap ,即扩容后新的索引只有两种情况,要么不变,要么等于旧的 + oldCap

1
2
3
         e.hash = 1111 1111 1111 1111 1010 1111 1010 1100
     n - 1 = 31 = 0000 0000 0000 0000 0000 0000 0001 1111
 (n - 1) & hash = 0000 0000 0000 0000 0000 0000 0000 1100 = 12

扩容比较一下 (e.hash & oldCap) == 0

1
2
3
         e.hash = 1111 1111 1111 1111 1010 1111 1010 1100
    oldCap = 32 = 0000 0000 0000 0000 0000 0000 0010 0000
e.hash & oldCap = 0000 0000 0000 0000 0000 0000 0010 0000 != 0

所以新的索引位置为旧的 12 加上 oldCap 的 32 为 44,验证如下

1
2
3
         e.hash = 1111 1111 1111 1111 1010 1111 1010 1100
newCap - 1 = 63 = 0000 0000 0000 0000 0000 0000 0011 1111
 (n - 1) & hash = 0000 0000 0000 0000 0000 0000 0010 1100 = 32 + 12 = 44

put 插入

1
2
3
4
5
public V put(K key, V value) {
  return putVal(hash(key), key, value, false, true);
  //这里的false是指定的参数onlyIfAbsent,true指定的参数evict
  //onlyIfAbsent参数用于设置传入已存在的key是否保留,默认为false即覆盖旧值
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
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是否是为空,因为没有在构造方法中初始化
  if ((tab = table) == null || (n = tab.length) == 0)
    //若为空则通过resize方法进行初始化
    n = (tab = resize()).length;
  //(n - 1) & hash计算当前插入元素的索引
  //若数组对应位置没有元素则新建结点插入
  if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
  //若有元素了,即可能插入了重复值,或表示发生了哈希冲突
  else {
    Node<K,V> e; K k;
    //先判断当前插入元素的key是否存在
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
      //若存在则取出旧值到临时结点e
      e = p;
    //不存在重复key,即发生了哈希冲突
    //先判断是否是通过红黑树保存的冲突结点
    else if (p instanceof TreeNode)
      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    //不是红黑树则是通过链表保存
    else {
      //遍历链表
      for (int binCount = 0; ; ++binCount) {
        //若链表之前没有新插入的key, 则新建一个节点插在链表末尾
        if ((e = p.next) == null) {
          p.next = newNode(hash, key, value, null);
          //若链表的长度达到TREEIFY_THRESHOLD默认的8,则将其转换为红黑树
          if (binCount >= TREEIFY_THRESHOLD - 1)
            treeifyBin(tab, hash);
          break;
        }
        //若在链表中找到了目标key则退出循环,新插入的值保存在e中
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
          break;
        p = e;
      }
    }
   
    //以下对应两种情况,要么新插入的key已存在且e保存了旧值
    //要么新插入的key不存在,且已经新建了Node插入,e为null
    if (e != null) {
      V oldValue = e.value;
      //根据onlyIfAbsent判断是否要用重复值覆盖旧值
      if (!onlyIfAbsent || oldValue == null)
        e.value = value;
      //在LinkedHashMap中用到,这里为空函数
      afterNodeAccess(e);
      return oldValue;
    }
  }
  //插入了不重复的新值
  ++modCount;
  //判断是否需要扩容
  if (++size > threshold)
    resize();
  //在LinkedHashMap中用到, 这里为空函数
  afterNodeInsertion(evict);
  return null;
}

treeifyBin 链表变红黑树

1
2
3
4
5
6
7
8
9
final void treeifyBin(Node<K,V>[] tab, int hash) {
  int n, index; Node<K,V> e;
  if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    //当数组长度小于MIN_TREEIFY_CAPACITY的64时是通过扩容来解决哈希冲突而不是建树
    resize();
  else if ((e = tab[index = (n - 1) & hash]) != null) {
    //红黑树的部分以后再看吧...
  }
}

以上内容是玉山整理的笔记,如有错误还请指出