Java的HashMap

Keane1998 2020-02-03 我要评论

HashMap

概述

HashMap是一个
jdk8源码

构造器
有4个构造器：

public HashMap()
public HashMap(int initialCapacity)
public HashMap(int initialCapacity, float loadFactor)
public HashMap(Map<? extends K, ? extends V> m)

除了显式设置loadFactor，其他情况都是设置为默认的0.75。
传入另外一个Map需要满足泛型上下界的要求，比如只能由<String,String>转成<Object,Object>。

主要成员变量

Node<K,V>[] table;
哈希表。
Set<Map.Entry<K,V>> entrySet;
用来遍历的Entry集合。
int size;
map中元素个数。
int modCount;
源码上说的是结构化修改的次数，关系不大。
int threshold;
阈值，当size大于这个阈值，就要resize
final float loadFactor;
加载因子，表示哈希表中元素的密集程度，默认是0.75。

put

table

哈希表，就是一个Node数组，而Node是HashMap里一个静态内部类，实现了Map接口里的Entry接口，可以看出Node类其实是一个链表节点，所以HashMap就是使用了链地址法来解决冲突的。
Node类重写了hashCode方法，把key和value的哈希值异或起来。

public final int hashCode() {
    return Objects.hashCode(key) ^ Objects.hashCode(value);
}

putVal

put方法内部是调用了putVal方法，putVal(hash(key), key, value, false, true)。
多了三个参数，第一个是哈希值，后两个是onlyIfAbsent和evict。
onlyIfAbsent是put方法用来判断是否覆盖。
evict应该是LinkedHashMap用到的，默认都为true。

第一步就是判断哈希表是否为空，若是进行resize()，保证哈希表的长度是2的k次方的形式。
第二步就是通过哈希值计算下标，计算的方法是(n - 1) & hash，因为n=2^k，所以这个操作就是取哈希值的低k位，其实就是取模。
第三步判断是否冲突了，若否就直接放一个新节点上去，存有hash值，key和value。
第四步就是解决冲突。

注意这里的相等比较用到了==和equals()，这是key覆盖的情况。

if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;

如果哈希表上不是链表节点，而是平衡树节点，调用putTreeVal方法。

else if (p instanceof TreeNode)
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

这是哈希位置相同而key不同的清空，也就是哈希冲突。
遍历对应位置的链表，加到表尾，如果链表中间有相等的key，也是覆盖。
当同一位置链表节点数大于等于8个时，调用treeifyBin方法进行树化，将链表转化为红黑树。

else {
    for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) {
            p.next = newNode(hash, key, value, null);
            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                treeifyBin(tab, hash);
            break;
        }
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            break;
        p = e;
    }
}

接下来是处理key覆盖的清空，会返回旧的value。
put方法的onlyIfAbsent是false，所以无论如何都会覆盖相同key的值。
putIfAbsent方法的onlyIfAbsent是true，所以只有当oldValue是null的时候，才会覆盖。

if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}

Test code1

import java.util.HashMap;

public class LearnHashMap {
    public static void main(String[] args) {
        HashMap<String,String> a=new HashMap<>();
        a.put("abc","FF");
        a.putIfAbsent("abc","FFF");  //不会覆盖，仍然是{"abc":"FF"}
        System.out.println(a.put("abc","kk"));
    }
}

最后是处理对应哈希表下标没有元素的清空，size要加1，如果大于threshold，就扩容。

++modCount;
if (++size > threshold)
    resize();
afterNodeInsertion(evict);
return null;

tableSizeFor

这个方法可以返回最近且大于cap的2的次幂，可以用来根据容量capacity来确定阈值threshold。
源码就不看了，神仙位运算看不懂。

resize

每次都是2倍的扩容，MAXIMUM_CAPACITY就是1<<30。

else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
         oldCap >= DEFAULT_INITIAL_CAPACITY)
    newThr = oldThr << 1; // double threshold

如果容量为0，而阈值大于0，直接让容量为阈值。

else if (oldThr > 0) // initial capacity was placed in threshold
    newCap = oldThr;

都为0，则用默认值，默认阈值等于默认容量默认加载因子，即160.75=12。

else {               // zero initial threshold signifies using defaults
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}

然后就是new一个新的节点数组，大小是原数组的两倍，然后将原数组的链表和红黑树copy过去。
这一步可以把原本一个节点的链表分成两个。

next = e.next;
if ((e.hash & oldCap) == 0) {
    if (loTail == null)
        loHead = e;
    else
        loTail.next = e;
    loTail = e;
}
else {
    if (hiTail == null)
        hiHead = e;
    else
        hiTail.next = e;
    hiTail = e;
}

treeifyBin

将链表转红黑树