HashMap详解

发表于 | 分类于 |

什么是HashMap

HashMap一个用于存储Key-Value键值对的集合，每一个键值对称之为Entry分散存储在一个数组中。这个数组每一个元首初始值都是Null。

HashMap的常用操作就是GET和PUT

PUT

我们在调用put方法的时候，会利用一个哈希函数来确定Entry的插入位置。为了解决哈希冲突的问题，HashMap采用链表法来解决这个问题。
注意：位置0上存放的一定是Null

1
2
3
4
5
6
7
8
9
10
11
12
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
}
modCount++;
addEntry(hash, key, value, i);
return null;

在遇到Hash冲突的时候，就将Entry以链表的形式给插入到相应的位置，这里需要注意的是：HashMap采用的是头插法的形式。这是因为设计者认为最新加入的Entry更有可能被访问。
此时HashMap的结构为数组加链表

当HashMap中有大量的元素都存放在同一个位置的时候，这个位置就有存在一条很长的链表；这个时候的HashMap相当于一个单链表。
于是在JDK1.8中引入了红黑树来优化这个问题。当某一个位置上的链表长度大于等于8的时就使用红黑树来进行存储。
在元素值小于6的时候就将红黑树又转换成链表形式。
此时HashMap的结构为数组加链表加红黑树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//一个桶的树化阈值
//当桶中元素个数超过这个值时，需要使用红黑树节点替换链表节点
//这个值必须为 8，要不然频繁转换效率也不高
static final int TREEIFY_THRESHOLD = 8;
 
//一个树的链表还原阈值
//当扩容时，桶中元素个数小于这个值，就会把树形的桶元素 还原（切分）为链表结构
//这个值应该比上面那个小，至少为 6，避免频繁转换
static final int UNTREEIFY_THRESHOLD = 6;
 
//哈希表的最小树形化容量
//当哈希表中的容量大于这个值时，表中的桶才能进行树形化
//否则桶内元素太多时会扩容，而不是树形化
//为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;

GET

在HashMap的GET函数中，首先会通过计算键值的哈希值获取到Entry所在的位置，然后通过遍历链表或红黑树中的Entry来确定是否是我们需要的值。

HashMap在遍历链表比较时使用的Java对象的equals()函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }
    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

通过这段代码，我们也可以看出：HashMap是可以存放键为Null的对象

HashMap的遍历方式

1
2
3
4
5
6
7
8
9
10
11
Iterator<Map.Entry<String, Integer>> entryIterator = map.entrySet().iterator();
        while (entryIterator.hasNext()) {
            Map.Entry<String, Integer> next = entryIterator.next();
            System.out.println("key=" + next.getKey() + " value=" + next.getValue());
        }
        
Iterator<String> iterator = map.keySet().iterator();
        while (iterator.hasNext()){
            String key = iterator.next();
            System.out.println("key=" + key + " value=" + map.get(key));
        }

推荐使用第一种方式，第一种方式会将KV同时取出，而第二种方式还需要通过key取一次value，效率比较低。

HashMap默认初始化长度

首先，我们要明确的一点就是：HashMap的默认初始化长度是16，并且每次扩容和缩容后的长度大小都是2的幂。

为什么会有以上的限制呢？
这是因为需要实现尽可能分布均匀的Hash函数。HashMap中使用了位取模的方式来计算哈希值。
index = HashCode（Key） & （Length - 1）

这样做不但效果上等同于取模，而且大大提升了性能。
使用位运算的方式，相当于只取hash函数的后几位，分布情况取决于hash函数。
而使用其他方式，如取模，则可能会导致某些index结果出现的几率大大提升;此外，如果length不是2的幂的话，有些index的结果可能永远不会出现。

Hash的Rehash

HashMap的容量是有限的。当经过多次元素插入，使得HashMap达到一定饱和度时，Key映射位置发生冲突的几率会逐渐提高。
这个时候的HashMap会需要进行扩容行为了。

影响HashMap扩容的因素有两个：

  • Capacity：当前长度
  • LoadFactor：负载因子，默认是0.75f

HashMap.Size >= Capacity * LoadFactor时就会进行扩容操作了

HashMap的扩容操作分两步：

  1. 创建一个新的数组，大小是原来数组的2倍。
  2. 遍历原数组，将原数组的所有元素重新Hash到新数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Transfers all entries from current table to newTable.
 */
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

HashMap每次扩容或缩容都是以2的倍数进行的。
这是因为在这样的流程中，HashMap中的Entry需要迁移的只有一半，大大的节省了扩缩容的消耗。

高并发下的HashMap

HashMap并不是线程安全的，在多线程操作下可能会导致很多意想不到的情况发生。比如死循环。

比如在上一小节中讲的Rehash，如果有多个线程同时进行扩容操作就会出现问题。
假设一个HashMap已经到了Resize的临界点。此时有两个线程A和B，在同一时刻对HashMap进行Put操作：
-w564
-w496
此时达到Resize条件，两个线程各自进行Rezie的第一步，也就是扩容：
-w748
这时候，两个线程都走到了ReHash的步骤。让我们回顾一下ReHash的代码：

假如此时线程B遍历到Entry3对象，刚执行完红框里的这行代码，线程就被挂起。对于线程B来说：

1
2
e = Entry3
next = Entry2

这时候线程A畅通无阻地进行着Rehash，当ReHash完成后，结果如下（图中的e和next，代表线程B的两个引用）：
-w778
直到这一步，看起来没什么毛病。接下来线程B恢复，继续执行属于它自己的ReHash。

1
2
e = Entry3
next = Entry2


当执行到上面这一行时，显然 i = 3，因为刚才线程A对于Entry3的hash结果也是3。

我们继续执行到这两行，Entry3放入了线程B的数组下标为3的位置，并且e指向了Entry2。此时e和next的指向如下：

1
2
e = Entry2
next = Entry2

整体情况如图所示：
-w702
接着是新一轮循环，又执行到红框内的代码行：

整体情况如图所示：
-w762
接下来执行下面的三行，用头插法把Entry2插入到了线程B的数组的头结点：

整体情况如图所示：
-w746
第三次循环开始，又执行到红框的代码：

1
2
e = Entry3
next = Entry3.next = null

最后一步，当我们执行下面这一行的时候，见证奇迹的时刻来临了：

1
2
3
4
newTable[i] = Entry2
e = Entry3
Entry2.next = Entry3
Entry3.next = Entry2

链表出现了环形！

整体情况如图所示：
-w751
此时，问题还没有直接产生。当调用Get查找一个不存在的Key，而这个Key的Hash结果恰好等于3的时候，由于位置3带有环形链表，所以程序将会进入死循环！