[Java]-Map源码分析-HashMap

发表于 | 分类于 | 阅读次数

HashMap也是一个储存价值对的常用方法，她的底层由哈希表实现（数组），用拉链法解决哈希碰撞（链表）。

它继承于AbstractMap，实现了Map<K,V>, Cloneable, Serializable接口。

jdk1.8引入了红黑树，来解决链表长度过长导致的查询速度下降问题,当碰撞过多，链表过长，这时我们将链表用红黑树来替代，以降低查询效率，所以在hashMap中同时有链表节点（Node）的结构，也有树节点（TreeNode）的结构

Node & TreeNode

普通节点Node：hash值，key，value，只想下一个节点的指针

树节点TreeNode：

成员变量：父节点，左孩子，右孩子，前一个键值对，颜色。hash, K key, V val, Node<K,V> next

方法：取跟节点root（），根据哈希值和key取树节点，将链表树化，将树链表化，向树添加一个节点，删除一个节点，split截取等

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
// 普通节点
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    // ...
}

// 树节点，继承自LinkedHashMap.Entry
// 这是因为LinkedHashMap是HashMap的子类，也需要支持树化
static final 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(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }
    // ...
}

// LinkedHashMap.Entry的实现
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

成员变量

从成员变量就可以看出来大概的设计。

和ArrayDeque类似，数组长度是不大于2的30次方的2的次幂，当数组被填充75%以上时进行数组扩展。

当链表的长度达到8就转为红黑树

树的大小到6就转回链表

当整个hashmap的容量超过64之后才能转成树

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
// capacity初始值，为16，必须为2的次幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

// capacity的最大值，为2^30
static final int MAXIMUM_CAPACITY = 1 << 30;

// load factor，是指当容量被占满0.75时就需要rehash扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 链表长度到8，就转为红黑树
static final int TREEIFY_THRESHOLD = 8;

// 树大小为6，就转回链表
static final int UNTREEIFY_THRESHOLD = 6;

// 至少容量到64后，才可以转为树
static final int MIN_TREEIFY_CAPACITY = 64;

// 保存所有元素的table表
transient Node<K,V>[] table;

// 通过entrySet变量，提供遍历的功能
transient Set<Map.Entry<K,V>> entrySet;

// 下一次扩容值
int threshold;

// load factor
final float loadFactor;

方法

增加一个元素

既然是hash，就需要选一个hash函数来将元素散列。

这里的hash函数如下，这里用到的方法很简单，就是把key与其高16位异或。这是一个权衡了速度，散裂度等因素之后的一个这种方法

1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

添加过程如下：

  • 添加元素先判断是不是空表，是则初始化。

  • 根据hash来查看tab[i = (n - 1) & hash]) 是不是空值，是空值则直接插入

  • 不是的话，判断tab[i = (n - 1) & hash])的key是不是将要插入的元素的key，是则修改值。

  • 判断tab[i = (n - 1) & hash])是不是树节点if (p instanceof TreeNode)，如果是，则将该节点添加进红黑树 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

  • 若不是树结构，则说明要使用链表结构，将元素添加到链表尾部。添加过程需要向后循环，若发现节点数大于TREEIFY_THRESHOLD则需要从链表变成树结构，调用treeifyBin(tab, hash);,若果发现key相同则修改元素的值。

  • 添加后看容量是否到达了75%，是的话就扩充容量，还有一些别的插入后的操作

扩容

判断是否超过了最大容量，是的话返回原来的表。否则扩大二倍，若扩大二倍后超过了最大容量则返回最大的容量表。

扩容结束后需要将原来的表复制到新的表。

总结

设计的key对象一定要实现hashCode方法，并尽可能保证均匀少重复。

如果可以预先估计数量级，可以指定initial capacity，以减少rehash的过程。

虽然HashMap引入了红黑树，但它的使用是很少的，如果大量出现红黑树，说明数据本身设计的不合理，我们应该从数据源寻找优化方案。