十分钟就要深入理解 HashMap 源码, 看完你能懂? 我觉得得再多看一分钟, 才能完全掌握!
终于来到比较复杂的 HashMap, 由于内部的变量, 内部类, 方法都比较多, 没法像 ArrayList 那样直接平铺开来说, 因此准备从几个具体的角度来切入.
桶结构
HashMap 的每个存储位置, 又叫做一个桶, 当一个 Key&Value 进入 map 的时候, 依据它的 hash 值分配一个桶来存储.
看一下桶的定义: table 就是所谓的桶结构, 说白了就是一个节点数组.
- transient Node<K,V>[] table;
- transient int size;
节点
HashMap 是一个 map 结构, 它不同于 Collection 结构, 不是存储单个对象, 而是存储键值对.
因此内部最基本的存储单元是节点: Node.
节点的定义如下:
- class Node<K,V> implements Map.Entry<K,V> {
- final int hash;
- final K key;
- V value;
- Node<K,V> next;
- }
可见节点除了存储 key,vaue,hash 三个值之外, 还有一个 next 指针, 这样一样, 多个 Node 可以形成一个单向列表. 这是解决 hash 冲突的一种方式, 如果多个节点被分配到同一个桶, 可以组成一个链表.
HashMap 内部还有另一种节点类型, 叫做 TreeNode:
- 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;
- }
TreeNode 是从 Node 继承的, 它可以组成一棵红黑树. 为什么还有这个东东呢? 上面说过, 如果节点的被哈希到同一个桶, 那么可能导致链表特别长, 这样一来访问效率就会急剧下降. 此时如果 key 是可比较的 (实现了 Comparable 接口),HashMap 就将这个链表转成一棵平衡二叉树, 来挽回一些效率. 在实际使用中, 我们期望这种现象永远不要发生.
有了这个知识, 就可以看看 HashMap 几个相关常量定义了:
- static final int TREEIFY_THRESHOLD = 8;
- static final int UNTREEIFY_THRESHOLD = 6;
- static final int MIN_TREEIFY_CAPACITY = 64;
TREEIFY_THRESHOLD, 当某个桶里面的节点数达到这个数量, 链表可转换成树;
UNTREEIFY_THRESHOLD, 当某个桶里面数低于这数量, 树转换回链表;
MIN_TREEIFY_CAPACITY, 如果桶数量低于这个数, 那么优先扩充桶的数量, 而不是将链表转换成树;
put 方法: Key&Value
插入接口:
- public V put(K key, V value) {
- return putVal(hash(key), key, value, false, true);
- }
- final int hash(Object key) {
- int h;
- return (key == null) ? 0 : (h = key.hashCode()) ^ (h>>> 16);
- }
put 方法调用了私有方法 putVal, 不过值得注意的是, key 的 hash 值不是直接用的 hashCode, 最终的 hash=(hashCode 右移 16)^ hashCode.
在将 hash 值映射为桶位置的时候, 取的是 hash 值的低位部分, 这样如果有一批 key 的仅高位部分不一致, 就会聚集的同一个桶里面.(如果桶数量比较少, key 是 Float 类型, 且是连续的整数, 就会出现这种 case).
执行插入的过程:
- V putVal(int hash, K key, V value, boolean onlyIfAbsent,
- boolean evict) {
- Node<K,V>[] tab; Node<K,V> p; int n, i;
- if ((tab = table) == null || (n = tab.length) == 0)
- n = (tab = resize()).length;
- // 代码段 1
- if ((p = tab[i = (n - 1) & hash]) == null)
- tab[i] = newNode(hash, key, value, null);
- else {
- Node<K,V> e; K k;
- // 代码段 2
- if (p.hash == hash &&
- ((k = p.key) == key || (key != null && key.equals(k))))
- e = p;
- // 代码段 3
- else if (p instanceof TreeNode)
- e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
- else {
- // 代码段 4
- for (int binCount = 0; ; ++binCount) {
- // 代码段 4.1
- if ((e = p.next) == null) {
- p.next = newNode(hash, key, value, null);
- if (binCount>= TREEIFY_THRESHOLD - 1) // -1 for 1st
- treeifyBin(tab, hash);
- break;
- }
- // 代码段 4.2
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k))))
- break;
- p = e;
- }
- }
- // 代码段 5
- if (e != null) { // existing mapping for key
- V oldValue = e.value;
- if (!onlyIfAbsent || oldValue == null)
- e.value = value;
- afterNodeAccess(e);
- return oldValue;
- }
- }
- // 代码段 6
- ++modCount;
- if (++size> threshold)
- resize();
- afterNodeInsertion(evict);
- return null;
- }
最开始的一段处理桶数组还没有分配的情况;
代码段 1: i = (n - 1) & hash, 计算 hash 对应的桶位置, 因为 n 是 2 的冥次, 这是一种高效的取模操作; 如果这个位置是空的, 那么直接创建 Node 放进去就 OK 了; 否则这个冲突位置的节点记为 P;
代码段 2: 如果节点 P 的 key 和传入的 key 相等, 那么说明新的 value 要放入一个现有节点里面, 记为 e;
代码段 3: 如果节点 P 是一棵树, 那么将 key&value 插入到这个棵树里面;
代码段 4:P 是链表头, 或是单独一个节点, 两种情况, 都可以通过扫描链表的方式来做;
代码段 4.1: 如果链表到了尾部, 插入一个新节点, 同时如果有必要, 将链表转成树;
代码段 4.2: 如果链表中找到了相等的 key, 和代码段 2 一样处理;
代码段 5: 将 value 存入节点 e
代码段 6: 如果 size 超过某个特定值, 要调整桶的数量, 关于 resize 的策略在下文会讲
remove 方法
了解了 put 方法, remove 方法就容易了, 直接讲解私有方法 removeNode 吧.
- public V remove(Object key) {
- Node<K,V> e;
- return (e = removeNode(hash(key), key, null, false, true)) == null ?
- null : e.value;
- }
- Node<K,V> removeNode(int hash, Object key, Object value,
- boolean matchValue, boolean movable) {
- Node<K,V>[] tab; Node<K,V> p; int n, index;
- // 代码段 1
- if ((tab = table) != null && (n = tab.length)> 0 &&
- (p = tab[index = (n - 1) & hash]) != null) {
- // 代码段 2:
- Node<K,V> node = null, e; K k; V v;
- if (p.hash == hash &&
- ((k = p.key) == key || (key != null && key.equals(k))))
- node = p;
- // 代码段 3:
- else if ((e = p.next) != null) {
- // 代码段 3.1:
- if (p instanceof TreeNode)
- node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
- else {
- // 代码段 3.2:
- do {
- if (e.hash == hash &&
- ((k = e.key) == key ||
- (key != null && key.equals(k)))) {
- node = e;
- break;
- }
- p = e;
- } while ((e = e.next) != null);
- }
- }
- // 代码段 4:
- if (node != null && (!matchValue || (v = node.value) == value ||
- (value != null && value.equals(v)))) {
- // 代码段 4.1:
- if (node instanceof TreeNode)
- ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
- // 代码段 4.2:
- else if (node == p)
- tab[index] = node.next;
- // 代码段 4.3:
- else
- p.next = node.next;
- ++modCount;
- --size;
- afterNodeRemoval(node);
- return node;
- }
- }
- return null;
- }
代码段 1: 这个 if 条件在判断 hash 对应的桶是否空的, 如果是话, 那么 map 里面肯定就没有这个 key; 否则第一个节点记为 P;
代码段 2: 如果 P 节点的 key 与参数 key 相等, 找到了要移除的节点, 记为 node;
代码段 3: 扫描桶里面的其他节点
代码段 3.1: 如果桶里面这是一颗树, 执行树的查找逻辑;
代码段 3.2: 执行链表扫描逻辑;
代码段 4: 如果找到了 node, 那么尝试删除它
代码段 4.1: 如果是树节点, 执行树的节点删除逻辑;
代码段 4.2:node 是链表头结点, 将 node.next 放入桶就 ok;
代码段 4.3: 删除链表中间节点
rehash
rehash 就是重新分配桶, 并将原有的节点重新 hash 到新的桶位置.
先看两个和桶的数量相关的成员变量
- final float loadFactor;
- int threshold;
loadFactor 负载因子, 是创建 HashMap 时设定的一个值, 即 map 所包含的条目数量与桶数量的比值上限; 一旦 map 的负载达到这个值, 就需要扩展桶的数量;
threshold map 的数量达到这个值, 就需要扩展桶, 它的值基本上等于桶的容量 * loadFactor, 我感觉就是一个缓存值, 加快相关的操作, 不用每次都去计算;
桶的扩展策略, 见下面的函数, 如果需要的容量是 cap, 真实扩展的容量是大于 cap 的一个 2 的冥次.
这样依赖, 每次扩展, 增加的容量都是 2 的倍数.
- 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;
- }
这是具体的扩展逻辑
- Node<K,V>[] resize() {
- // 此处省略了计算 newCap 的逻辑
- 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;
- // 分支 1
- if (e.next == null)
- newTab[e.hash & (newCap - 1)] = e;
- // 分支 2
- else if (e instanceof TreeNode)
- ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
- // 分支 3
- else { // preserve order
- // 此处省略了链表拆分逻辑
- }
- }
- }
- return newTab;
- }
首先分配新的桶数组;
扫描旧的桶, 将元素迁移过来;
分支 1: 桶里面只有一个新的节点, 那么放入到新桶对应的位置即可;
分支 2: 桶里面是一棵树, 执行树的拆分逻辑
分支 3: 桶里面是一个链表, 执行链表的拆分逻辑;
由于新桶的数量是旧桶的 2 的倍数, 所以每个旧桶都能对应 2 个或更多的新桶, 互不干扰. 所以上面的迁移逻辑, 并不需要检查新桶里面是否有节点.
可见, rehash 的代价是很大的, 最好在初始化的时候, 能够设定一个合适的容量, 避免 rehash.
最后, 虽然上面的代码没有体现, 在 HashMap 的生命周期内, 桶的数量只会增加, 不会减少.
迭代器
所有迭代器的核心就是这个 HashIterator
- abstract class HashIterator {
- Node<K,V> next; // next entry to return
- Node<K,V> current; // current entry
- int expectedModCount; // for fast-fail
- int index; // current slot
- final Node<K,V> nextNode() {
- Node<K,V>[] t;
- Node<K,V> e = next;
- if (modCount != expectedModCount)
- throw new ConcurrentModificationException();
- if (e == null)
- throw new NoSuchElementException();
- if ((next = (current = e).next) == null && (t = table) != null) {
- do {} while (index <t.length && (next = t[index++]) == null);
- }
- return e;
- }
- }
简单起见, 只保留了 next 部分的代码. 原理很简单, next 指向下一个节点, 肯定处在某个桶当中 (桶的位置是 index). 那么如果同一个桶还有其他节点, 那么一定可以顺着 next.next 来找到, 无论这是一个链表还是一棵树. 否则扫描下一个桶.
有了上面的节点迭代器, 其他用户可见的迭代器都是通过它来实现的.
- final class KeyIterator extends HashIterator
- implements Iterator<K> {
- public final K next() { return nextNode().key; }
- }
- final class ValueIterator extends HashIterator
- implements Iterator<V> {
- public final V next() { return nextNode().value; }
- }
- final class EntryIterator extends HashIterator
- implements Iterator<Map.Entry<K,V>> {
- public final Map.Entry<K,V> next() { return nextNode(); }
- }
视图
KeySet 的部分代码: 这并不是一个独立的 Set, 而是一个视图, 它的接口内部访问的都是 HashMap 的数据.
- final class KeySet extends AbstractSet<K> {
- public final int size() { return size; }
- public final void clear() { HashMap.this.clear(); }
- public final Iterator<K> iterator() { return new KeyIterator(); }
- public final boolean contains(Object o) { return containsKey(o); }
- public final boolean remove(Object key) {
- return removeNode(hash(key), key, null, false, true) != null;
- }
- }
EntrySet,Values 和 KeySet 也是类似的, 不再赘述.
要点总结
1,key&value 存储在节点中;
2, 节点有可能是链表节点, 也有可能是树节点;
3, 依据 key 哈希值给节点分配桶;
4, 如果桶里面有多个节点, 那么要么形成一个链表, 要么形成一颗树;
5, 装载因子限制的了节点和桶的数量比例, 必要时会扩展桶的数量;
6, 桶数量必然是 2 的冥次, 重新分配桶的过程叫做 rehash, 这是很昂贵的操作;
写在最后
来源: http://www.bubuko.com/infodetail-3119931.html