HashMap-1.7和1.8的区别

发表于 更新于 分类于 阅读次数： 阅读次数：

jdk7

存放数据的数组

put方法

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
public V put(K key, V value) {
　　　　　//数组为空就进行初始化
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
　　　　　//key 进行哈希计算
    int hash = hash(key);
　　　　　//获取数组下标
    int i = indexFor(hash, table.length);
　　　　　//如果此下标有值，遍历链表上的元素，key 一致的话就替换 value 的值
    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++;
　　　　　//新增一个key
    addEntry(hash, key, value, i);
    return null;
}

addEntry方法

1
2
3
4
5
6
7
8
9
void addEntry(int hash, K key, V value, int bucketIndex) {
　　　　　//数组长度大于阈值且存在哈希冲突（即当前数组下标有元素），就将数组扩容至2倍
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
}

createEntry方法

1
2
3
4
5
6
void createEntry(int hash, K key, V value, int bucketIndex) {
　　　　　//此位置有元素，就在链表头部插入新元素（头插法）
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

总结

jdk 1.7扩容的条件是：数组长度大于阈值且存在哈希冲突，由此我们可以想象，默认长度为16的情况下，数组最多可以存27个元素后才扩容，原因是在一个下标存储12个元素后（阈值为12），在剩下的15个下标各存一个元素，最多就可存27个元素，当然这种是很偶然的情况。不过也可以看到 jdk1.7 中，这个阈值的作用并不是特别的大，并不是超过阈值就一定会扩容。

jdk8

put方法

1
2
3
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

putVal方法

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
final 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;
　　　　　//当前下标为空，就直接插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
　　　　　　　//key 相同就覆盖原来的值
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
　　　　　　　//树节点插入数据
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
　　　　　　　　　　　　//链表，尾插法插入数据
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
　　　　　　　　　　　　　　//链表长度超过8，就把链表转为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
　　　　　　　　　　　　//key相同就覆盖原来的值
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
　　　　　//数组长度大于阈值，就扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

treeifyBin 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
　　　　　//链表转为红黑树时，若此时数组长度小于64，扩容数组
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
　　　　　　　//链表转为树结构
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

总结

1.8中，数组有两种情况会发生扩容，一种是超过阈值，一种是链表转为红黑树且数组元素小于64时，由此在jdk1.8中，默认长度为16情况下，要么元素一直放在同一下标，数组长度为9时就会扩容，要么超过阈值12时才会扩容。

主要区别

  1. 出现哈希冲突时，1.7把数据存放在链表，1.8是先放在链表，链表长度超过8就转成红黑树
  2. 1.7扩容条件是数组长度大于阈值且存在哈希冲突，1.8扩容条件是数组长度大于阈值或链表转为红黑树且数组元素小于64时