HashMap

HashMap

数组长度为什么必须是 2 的指数幂

减少哈希冲突,均匀分布元素。

1)通过将 Key 的 hash 值与 length-1 进行 & 运算,实现了当前 Key 的定位,2 的幂次方可以减少冲突(碰撞)的次数,提高 HashMap 查询效率;

2)如果 length 为 2 的次幂,则 length-1 转化为二进制必定是 11111…… 的形式,在于 h 的二进制与操作效率会非常的快,而且空间不浪费;如果 length 不是 2 的次幂,比如 length 为 15,则 length-1 为 14,对应的二进制为 1110,在于 h 与操作,最后一位都为 0,而 0001,0011,0101,1001,1011,0111,1101 这几个位置永远都不能存放元素了,空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率!这样就会造成空间的浪费。

如何扩容的

初始扩容因子

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;

为什么是 0.75 这个值呢?

这是因为对于使用链表法的哈希表来说,查找一个元素的平均时间是 O(1+n),这里的 n 指的是遍历链表的长度,因此加载因子越大,对空间的利用就越充分,这就意味着链表的长度越长,查找效率也就越低。如果设置的加载因子太小,那么哈希表的数据将过于稀疏,对空间造成严重浪费。

何时扩容

首次 put 的时候,如果 table 为空,会执行扩容:

if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

put 方法中,size++ 之后的值如果大于 threshold,那么也会执行 resize 方法。

if (++size > threshold)
    resize();

扩容扩多少

首次扩容:

newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

非首次扩容,新的容量和新的 threshold 都是翻一倍

newCap = oldCap << 1;
newThr = oldThr << 1;

元素如何迁移

  • 创建新的数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  • 遍历旧数组
for (int j = 0; j < oldCap; ++j) {
    Node<K,V> e;
    if ((e = oldTab[j]) != null) {
        // ...
    }
}
  • 如果 e.next 不为空,即数组里面只存储了这一个元素
newTab[e.hash & (newCap - 1)] = e;
  • 如果 eTreeNode
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  • 如果 enext,维持原来的顺序,挂到新的数组上

原来的元素在重新计算 hash 之后,会放到两个数组的坑里面。

// (e.hash & oldCap) == 0 的属于 loHead
newTab[j] = loHead;
// 否则属于 hiHead
newTab[j + oldCap] = hiHead;

头插法设计思路

JDK1.7是考虑新增数据大多数是热点数据,所以考虑放在链表头位置,也就是数组中,这样可以提高查询效率,但这种方式会出现插入数据是逆序的。在JDK1.8开始hashmap链表在节点长度达到8之后会变成红黑树,这样一来在数组后节点长度不断增加时,遍历一次的次数就会少很多,相比头插法而言,尾插法操作额外的遍历消耗已经小很多了。

也有很多人说避免多线程情况下hashmap扩容时的死循环问题,我个人觉得避免死循环的关键不在尾插法的改变,而是扩容时,用了首尾两个指针来避免死循环。这个我会在后面的多线程中讲到hashmap扩容导致死循环的问题。

get 方法如何实现的

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}
  • 首先使用 (n - 1) & key.hash 定位到这个 key 应该落到 table 的哪一个里面,其中 n 是指 table 的长度。
  • 然后看这个桶里面的 first 元素是否是目标值,如果是,直接返回。
  • 否则看 first 是否属于 TreeNode,如果是 TreeNode,则调用 getTreeNode 方法;否则沿着 e.next 往下遍历,并依次检查条件 key.hash == k.hash 并且 key.equals(k)

红黑树

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;

Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins. In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-0.5) pow(0.5, k) / factorial(k)). The first values are:

根据泊松分布实验发现,假设hashmap长度length为16,假设放入12(0.75*16)个数据到hashmap中,链表中存放8个节点的概率仅为0.00000006,而链表中存放1~7节点的概率为:

0:    0.60653066
1:    0.30326533
2:    0.07581633
3:    0.01263606
4:    0.00157952
5:    0.00015795
6:    0.00001316
7:    0.00000094
8:    0.00000006