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 | static class Entry<K,V> implements Map.Entry<K,V> { |
2.2 HashMap的重要成员变量
transient Entry[] table;
:实际存储键值对的表。transient
关键字仅可修饰成员变量,表示“禁止序列化该数据”,其意义是:HashMap 本身的数组,通常会有很多空闲的节点,对空闲的节点空间序列化没有意义,所以其手动实现了writeObject()
方法进行实际的序列化。table
、size
、modCount
都被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 后映射进数组节点中时,经过了如下运算:
- 计算 key 的 二次 hash;
- 将 hash 值的二进制与 HashMap 的 (length - 1) 的二进制进行 & 与运算;
- 得出的结果即为需要存进的数组节点下标。
(1)如果数组长度为 2 的幂,则 (length - 1) 的二进制一定是各个位都是 1,例如:
1 | 2^4 - 1 = 15(d) = 1111(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 | for (Entry<K,V> e = table[i]; e != null; e = e.next) { |
若遍历链表中已存储的键值对对象 e 时发现已存在,即:e.hash == hash
,则直接用新的 value
取代旧的并退出,否则也即遍历 e = e.next
直到 e == null
,则调用:
1 | addEntry(hash, key, value, i); |
将当前键值对存储到链表末端,并使前一个 e.next
指向该新键值对。
4. 其他
HashMap
、HasTable
、ConcurrentHashMap
的关联与区别:
- 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
关键字,确保读操作获取到的是最新的数据,因此是线程安全的。