Java-HashMap

Java-HashMap

1. 哈希散列表

HashMap的最基本原理就是哈希表,哈希表也就是,把一组不相干的数据,通过哈希函数计算后,映射到一个数组中,这样通过数组下标就能直接确认原来数据的存储位置。但哈希映射有可能会导致哈希碰撞,解决方案有:开放定址法、再散列函数法、链地址法,而HashMap采用的是链地址法。

1.1 开放定址法

开放定址法的核心思想就是增加偏移量,其中增加偏移量的方法有多种:线性探测、平方探测等,但整体思路是类似的。当插入一个新的数据时,发现经过哈希计算后,原Key的目标插入节点已经被占用了,发生碰撞,则向后偏移一位,再次检测,如果仍旧发生碰撞则继续偏移,直到到达数组尾端,根据不同的策略,可以绕回到数组头(负偏移)或扩大散列表。

线性探测会导致元素聚集,这和哈希散列表的初衷不符。

平方探测则是用:1, -1, 4, -4 ... 这样的方式进行左右跳跃性查找。

伪随机探测,即一开始就定义一个伪随机数列,每次发生冲突即从伪随机数列中取出下一个伪随机数作为偏移量。

1.2 再散列函数法

也即每次发生冲突时,就再用哈希函数散列一次。缺点是增大计算量。

1.3 链地址法

也即,哈希表的主体是一个数组,数组的每一个结点,都是一个链表,当发生哈希碰撞时,后插入的Key则插入到对应结点的链表的末端。

如果不存在哈希冲突,也即 HashMap 数组中不包含链表,则每次添加、查找都是单次寻址,时间复杂度为 O(1)。如果目标节点存在哈希冲突,则添加、查找都需要遍历整个链表,时间复杂度为 O(n),其中:查找时,通过 key 对象的 equals 方法逐一比较,相同则返回;新增时,遍历链表,若存在相同 key,则覆盖,否则新增至链表末端。

hashMap 与 hashTable 其中不同的一点是 HashMap 允许 key 为 null,把 key 为 null 的对象存在数组首位(table[0])。


2. HashMap源码分析

2.1 静态内部类Entry

HashMap 有一个静态内部类 Entry,其源码清晰描述了 HashMap 数组 + 链表 的数据结构:

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
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;

// 存储指向下一个Entry的引用,单链表结构
Entry<K,V> next;

// 对key的hashcode值进行hash运算后得到的值,存储在Entry,避免重复计算
int hash;

/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}

public final K getKey() {
return key;
}

public final V getValue() {
return value;
}

public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
}

2.2 HashMap的重要成员变量

  • transient Entry[] table;:实际存储键值对的表。
    transient 关键字仅可修饰成员变量,表示“禁止序列化该数据”,其意义是:HashMap 本身的数组,通常会有很多空闲的节点,对空闲的节点空间序列化没有意义,所以其手动实现了 writeObject() 方法进行实际的序列化。tablesizemodCount 都被 transient 关键字修饰,是因为每次 HashMap 执行 put 或 remove 操作后,三者都会发生变化,由于三者状态常变,所以没有必要在默认序列化类对象时将其指代入。
  • static final int DEFAULT_INITIAL_CAPACITY = 16;:默认初始容量为 16,必须为 2 的幂。
  • static final int MAXIMUM_CAPACITY = 1 << 30;:最大容量,必须为 2 的幂且要小于 2 的 30 次方,传入大于该值的参数将被该值替换。
  • static final float DEFAULT_LOAD_FACTOR = 0.75f;:默认加载因子。
  • final float loadFactor;:实际加载因子。

为了降低哈希冲突的概率,默认当 HashMap 中的键值对达到数组大小的 75% 时,会触发扩容操作。因此如果预估容量是 100,即需要设定 100 / 0.75 = 134 的数组大小。

  • transient int size:Map 中实际存储的键值对个数。
  • threshold:阈值。
  • transient volatile int modCount;:HashMao 被改变的次数,用于快速失败。

volatile 关键字修饰的成员变量,可以阻禁止代码重排序,保证所有的写操作都在读操作之前,使得变量在内存中的变化可以被多线程所知。由于 HashMap 线程不安全,modCount 用于快速失败机制,所以写线程执行时带来的变化需要及时被读线程所知。

put 操作时,若 key 已存在替换 value 时,modCount 不会增加,不存在新增时才会增加。也即,只有 HashMap 中元素的数量增多或减少时,才认为 HashMap 的结构发生了变化。

2.3 HashMap长度必须为2的幂

HashMap 在将一个 key 经过 hash 后映射进数组节点中时,经过了如下运算:

  1. 计算 key 的 二次 hash;
  2. 将 hash 值的二进制与 HashMap 的 (length - 1) 的二进制进行 & 与运算;
  3. 得出的结果即为需要存进的数组节点下标。

(1)如果数组长度为 2 的幂,则 (length - 1) 的二进制一定是各个位都是 1,例如:

1
2
2^4 - 1 = 15(d) = 1111(b)
2^5 - 1 = 31(d) = 11111(b)

由于与运算是“两位为 1 才为 1”,因此用 hash 的二进制和 (length - 1) 的二进制做与运算,其结果就完全取决于 hash 的二进制数。例如:

  • 若 hash = 1011011,(length - 1) = 1111,则 hash & (length - 1) = 1011。
  • 若 hash = 1101100010,(length - 1) = 11111,则 hash & (length - 1) = 10。

这样可以使得键值对尽可能均匀的分布在 HashMap 数组的各个节点。并且在扩容时,由于二进制的每一位只有可能是 1 或者 0,且扩容后的 (length - 1) 依然是各个位全为 1 的二进制数,也即经过与运算后,有一半几率该点依然位于原来的数组节点(而在链表中的位置则不确定),另一半的几率会被重新分配到其他的数组节点,从而可以保障扩容后键值对存储位置的均衡性。

(2)假如 HashMap 的长度不是 2 的幂,也即 (length - 1) 的二进制中可能存在 0,例如:

  • 若 hash = 1011011,(length - 1) = 1001,则 hash & (length - 1) = 1001。
  • 若 hash = 1101101111,(length - 1) = 1001,则 hash & (length - 1) = 1001。

不仅会导致哈希碰撞的概率增大,并且在上例中,由于 (length - 1) = 1001,则注定任何一个 hash 与之做与运算,其第 2、3 位都一定是 0,也即有些 HashMap 的数组节点则一定不会被用到。比如上例中当数组长度为 10 时,(length - 1) = 1001,则下标为:0111(b) = 7(d)0101(b) = 5(d)0011(b) = 3(d)0010(b) = 2(d) 的数组节点一定不会被用于存储,这是显然不符合 Hash 散列表特性的。


3. HashMap流程

在向 HashMap 存储数据时,会首先判断 key 是否为 null,如果为 null,则直接存入 table[0] 中,每次存储都会直接覆盖。若 key 不为 null,则会对 key 进行重哈希,也即哈希两次:

1
int hash = hash(key.hashCode());

通过计算出来的 hash 值,判断该键值对的目标数组节点下标:

1
int i = indexFor(hash, table.length);

然后遍历该节点中的链表,依次与之比较 hash 值:

1
2
3
4
5
6
7
8
9
10
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 若“该key”对应的键值对已经存在,则用新的value取代旧的value。然后退出!
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

若遍历链表中已存储的键值对对象 e 时发现已存在,即:e.hash == hash,则直接用新的 value 取代旧的并退出,否则也即遍历 e = e.next 直到 e == null,则调用:

1
addEntry(hash, key, value, i);

将当前键值对存储到链表末端,并使前一个 e.next 指向该新键值对。


4. 其他

HashMapHasTableConcurrentHashMap 的关联与区别:

  • HashTable 的 Key 和 Value 都不能为 Null,线程安全,在修改数据时给 put() 加锁锁住整个 HashTable。
  • HashMap 的 Key 和 Value 都可以是 Null,线程不安全。
    • 所以当 HashMap.get(key) 方法返回 null 时,可能是 key 对应的 value 为 null,也可能是没有找到对应的 key,因此判断 HashMap 中是否含有某个 key 时,应调用 containsKey() 方法。
    • HashMap 是线程不安全的,其迭代器是 Fail-Fast(快速失败)的,也即:当有其他线程改变了 HashMap 的结构(增加或移除了元素),则有可能抛出 ConcurrentModificationException 异常,但迭代器本身的 remove() 则不会引起该异常。
  • ConcurrentHashMap 将整个 Map 分段为 N 个 Segment,每个 Segment 独立加锁,对于需要跨段的操作(如 size()containsValue())则按顺序锁住所有段,操作完毕后再按顺序释放所有段的锁。且 Entry#value 添加了 volatile 关键字,确保读操作获取到的是最新的数据,因此是线程安全的。

参考文献