重读HashMap

Posted on Edited on

精简篇幅，本篇暂不讨论为java stream服务的特性

1. Interfaces

  • Map<K,V>
  • Cloneable
  • Serializable

2. Abstract super class

  • AbstractMap<K,V>

3. Static fields

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
/**
		 * The default initial capacity - MUST be a power of two.
	   */
// 初始化容量, 默认16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
		 * The maximum capacity, used if a higher value is implicitly specified
		 * by either of the constructors with arguments.
		 * MUST be a power of two <= 1<<30.
		 */
// 最大容量，默认最大int
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
		 * The load factor used when none specified in constructor.
		 */
// 负载因子，触发resize的阀值，默认0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
		 * The bin count threshold for using a tree rather than list for a
     * bin.  Bins are converted to trees when adding an element to a
     * bin with at least this many nodes. The value must be greater
     * than 2 and should be at least 8 to mesh with assumptions in
     * tree removal about conversion back to plain bins upon
     * shrinkage.
     */
// 链表转红黑树的阀值（防止hash碰撞过于严重）
static final int TREEIFY_THRESHOLD = 8;

/**
     * The bin count threshold for untreeifying a (split) bin during a
     * resize operation. Should be less than TREEIFY_THRESHOLD, and at
     * most 6 to mesh with shrinkage detection under removal.
     */
// 红黑树转链表的阀值
static final int UNTREEIFY_THRESHOLD = 6;

/**
     * The smallest table capacity for which bins may be treeified.
     * (Otherwise the table is resized if too many nodes in a bin.)
     * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
     * between resizing and treeification thresholds.
     */
// 转红黑树的前提阀值（先扩容table，再扩容bin）
static final int MIN_TREEIFY_CAPACITY = 64;

4. class fields

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
/**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     */
// hashMap数据存储的地方
transient Node<K,V>[] table;

/**
     * Holds cached entrySet(). Note that AbstractMap fields are used
     * for keySet() and values().
     */
// hashMap数据访问对象(视图/缓存实例)，依赖HashIterator实现entry访问
transient Set<Map.Entry<K,V>> entrySet;

/**
     * The number of key-value mappings contained in this map.
     */
// map元素数量
transient int size;

/**
     * The number of times this HashMap has been structurally modified
     * Structural modifications are those that change the number of mappings in
     * the HashMap or otherwise modify its internal structure (e.g.,
     * rehash).  This field is used to make iterators on Collection-views of
     * the HashMap fail-fast.  (See ConcurrentModificationException).
     */
// map修改次数，包括put\remove
// 在迭代map数据前后，做双重检查。并发访问，抛出运行时异常
transient int modCount;

/**
     * The next size value at which to resize (capacity * load factor).
     *
     * @serial
     */
    // (The javadoc description is true upon serialization.
    // Additionally, if the table array has not been allocated, this
    // field holds the initial array capacity, or zero signifying
    // DEFAULT_INITIAL_CAPACITY.)
// 下次扩容阀值
int threshold;

/**
     * The load factor for the hash table.
     *
     * @serial
     */
// 扩容因子
final float loadFactor;

/**
     * Each of these fields are initialized to contain an instance of the
     * appropriate view the first time this view is requested.  The views are
     * stateless, so there's no reason to create more than one of each.
     *
     * <p>Since there is no synchronization performed while accessing these fields,
     * it is expected that java.util.Map view classes using these fields have
     * no non-final fields (or any fields at all except for outer-this). Adhering
     * to this rule would make the races on these fields benign.
     *
     * <p>It is also imperative that implementations read the field only once,
     * as in:
     *
     * <pre> {@code
     * public Set<K> keySet() {
     *   Set<K> ks = keySet;  // single racy read
     *   if (ks == null) {
     *     ks = new KeySet();
     *     keySet = ks;
     *   }
     *   return ks;
     * }
     *}</pre>
     */
// 类似entrySet的key访问对象
transient Set<K>        keySet;
// 类似entrySet的value访问对象
transient Collection<V> values;

5. Inner classes

5.1简单存储对象

simpleEntry：键值对存储对象。

simpleImmutableEntry：不支持修改的键值对存储对象。

共性：都重写了equal方法，比较key & value

5.2 hash与红黑树

e g:

  • hash散列作用
  • hash算法选择
  • hash算法不可控因素
  • 数组与红黑树转换条件、原因
  • 红黑树机制简单介绍
5.2.1 什么是hash算法

又称散列算法，是一种从任意文件中创造小的数字「指纹」的方法。

与指纹一样，散列算法就是一种以较短的信息来保证文件唯一性的标志，这种标志与文件的每一个字节都相关，而且难以找到逆向规律。因此，当原有文件发生改变时，其标志值也会发生改变，从而告诉文件使用者当前的文件已经不是你所需求的文件。

特点：

  • 正向快速
  • 逆向困难
  • 输入敏感
  • 冲突避免：很难找到两段内容不同的明文，使得它们的 hash 值一致（发生冲突）。

常见实现方式：取模/异或/位运算

下面给出在Java中几个常用的哈希码(hashCode)的算法。

  1. Object类的hashCode. 返回对象的经过处理后的内存地址，由于每个对象的内存地址都不一样，所以哈希码也不一样。这个是native方法，取决于JVM的内部设计，一般是某种C地址的偏移。
  2. String类的hashCode. 根据String类包含的字符串的内容，根据一种特殊算法返回哈希码，只要字符串的内容相同，返回的哈希码也相同。
  3. Integer等包装类，返回的哈希码就是Integer对象里所包含的那个整数的数值，例如Integer i1=new Integer(100), i1.hashCode的值就是100 。由此可见，2个一样大小的Integer对象，返回的哈希码也一样。
  4. int，char这样的基础类，它们不需要hashCode，如果需要存储时，将进行自动装箱操作，计算方法同上。
5.2.2 散列

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

取hashcode参与运算，因为hashcode返回值为int（32位）

所以，将hashcode右移16位，再做异或运算，混合了高低位信息。

5.2.3 从hash到index

i = (tab.length - 1) & hash；

与运算 – 取一个数中指定位

index取值范围[0, tab.lenth -1]

与运算后，即为对应index。

从上文 [从hash到index](#####5.2.3 从hash到index)可以发现，在寻找map元素位置过程中，使用了与运算取hash结果中指定位。结合map容量字段定义，可以发现，容量为2的指数倍，才能刚好取hash结果中指定位。另一个可得结果是，map的数组大小，不会超过2的16次方。

5.2.4 hash碰撞

散列算法分布均为，也无法控制输入的数据分布。所以碰撞时必然的，甚至分布十分集中。

数组中存储 Node 对象。

当该index中对象碰撞较少时，以链表存储。新node放置在最前面。

当该index中对象碰撞较多时，链表转换为红黑树TreeNode。红黑树高度为log n，所以其查找、插入、删除操作复杂度均为O(log N)。

5.2.5 红黑树介绍（省略……哈哈）

5.3 并行处理API（忽略）

5.4 map数据访问对象

  • entrySet
  • keySet
  • valueSet

隐藏了底层复杂的数据结构（数组、链表、红黑树）。简化数据遍历。

实例化的内部类，持有hashmap的字段信息。同时自身也会被作为hashmap中字段存储，可视为map的视图。

5.4.1 map数据遍历与删除对象

set对象内部封装了迭代器，允许在迭代器中遍历、删除对象。

iterator 保存了当前Node 和下一个Node 。如果此时其他线程修改了map结构（增加删除key），那么下一个Node可能就不再存在，或者变成别的。

fast-fail

hashmap是不允许并发操作的（get除外）

  • 并发put/remove
    • hash碰撞时，链表新元素插入头部。先put的可能消失
    • hash碰撞时，红黑树同上（根结点会被替换）
  • 并发(put/remove) 和 iterator
    • 每次key发生变化，modCount就会+1。iterator每次next后，都会检查next操作后modCount与iterator保存的expectedModCount是否一致。一旦不一致，就会抛出ConcurrentModificationException。

Ps: fast-fail可以作为一个代码bug的提示。hashmap普通的修改操作不支持并发，可能会丢数据（扩容问题cover later）。iterator操作时，完全不允许key发生变更，故一旦发现操作数发生变化，抛出异常。

6. 扩容过程&并发扩容问题

死循环

参考文献