Java HashMap

阅读Java8的HashMap源码，写下了自己的一些笔记

相关常量

• DEFAULT_INITAL_CAPACITY=16，默认的HashMap的数组容量
• MAXINUM_CAPACITY=1<<30，默认的HashMap最大值
• DEFAULT_LOAD_FACTOR=0.75f，默认的HashMap负载因子，为0.75
• TREEIFY_THRESHOLD=8，默认的将链表转为红黑树的最小链表深度，大于等于8时转换
• UNTREEIFY_THRESHOLD=6，默认的将红黑树转为链表的深度，小于等于6时转换
• MIN_TREEIFY_CAPACITY=64，默认的最小的将链表转为红黑树的数组大小

相关变量

• transient int size当前Map的K-V对数目
• transient int modCount用于记录当前Map被修改的次数
  由于HashMap不是线程安全的，当HashMap在迭代开始时，会将modCount赋值给expectedModCount，迭代过程中，这两者如果不同，则说明此时该HashMap被修改了，会抛出异常ConcurrentModifiedException()
• final float loadFactor负载因子，可以大于1，不过效率会变低
• int threshold最大阈值
• transient Node<K,V>[] table存放node的数组
• Set<Map.Entry<K,V>> entrySet

四种构造函数

public HashMap(){
    this.loadFactor=DEFAULT_LOAD_FACTOR;
}

无参构造函数，将负载因子设置为默认的负载因子，HashMap无参构造函数不会初始化table、threshold等值

public HashMap(int initialCapacity){
    this(initialCapacity,DEFAULT_LOAD_FACTOR);
}

调用构造函数，负载因子使用默认负载因子

public HashMap(int initialCapacity,floaat loadFactor){
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + 
                                            initialCapacity);
    if (initialCapacity > MAXINUM_CAPACITY)
        initialCapacity = MAXINUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                            loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

对不符合要求的参数抛出异常，容量要满足0<capacity<=MAXINUM_CAPACITY，负载因子要大于0
Float.isNaN对那些非数的情况进行排除，比如0/0,0/∞等
将负载因子赋值，对容量调用tableSizeFor方法，返回大于等于capacity的最小2的整数幂

public HashMap(Map<? extends K, ? extends V> m){
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapRntries(m, false);
}

将负载因子设置为默认值，并调用putMapEntries方法
将Map中的所有的K-V对添加到新的Map中，并将新的map中的threshold设置为传入的map的threshold

相关方法（选择了部分方法）

hash

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

计算key的hash值，先判断是否为null，如果是则返回0，否则调用Object类的hashCode方法获得一个h值，将h与h逻辑右移16位之后的值异或，作为返回值

tableSizeFor

static final int tableSizeFor(int cap){
    int n = cap-1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1: (n >= MAXINUM_CAPACITY) ? MAXINUM_CAPACITY : n + 1;
}

tableSizeFor方法用于HashMap初始化时，在构造函数中，用于转换传入的容量的值，由于HashMap的容量必须为2的整数幂，因此tableSizeFor会返回大于等于cap的最小2的整数幂

putMapEntries

final void putMapEntries(Map<? extends K, ? entends V>m, boolean evict){
    int s = m.size();
    if (s > 0){
        if (table == null){
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXINUM_CAPACITY)?
                    (int)ft : MAXINUM_CAPACITY);
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        else if (s > threshold)
            resize();
        for (Map.Entry<? extends K, ? extends V>e : m.entrySet()){
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

将传入的map中的K-V对添加到自己的map中，如果传入的map的容量大于自己的map的容量就扩容。对于自己的map，如果table没有初始化，则将threshold设置为传入的map的threshold（在resize中会将threshold乘上loadFactor，注意数组的长度是capacity不是threshold）

put

final V put(K key, V value){
    return putVal(hash(key), key, value, false, true);
}

调用put方法，添加数据

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;
        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);
                    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;
            }
        }
        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;
                    
}

首先判断table是否为空，如果为空或者长度为0（此时长度已经赋给n），则扩容
其次判断根据计算hash并与(n-1)得到的位置是否为空，若为空直接占位置
若不为空，判断节点的类型是否是树节点，如果是，按照红黑树的插入方法插入
如果不是，按照链表的方式插入
遍历链表，如果有相同的元素则跳出循环，若没有，则插入到链表最后
如果链表长度大于等于8，则转换为红黑树
修改次数modCount++
如果++size大于阈值的话，扩容

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

这一段代码差一点没想起来，如果传入的是类，调用equals方法比较是否相同

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

这一段代码是留给未来的LinkedHashMap的，包括下面的afterNodeInsertion(evict)

resize

这一段代码是扩容相关的

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                    (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        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;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

扩容
可以看出阈值最大值可以达到Integer.MAX_VALUE，table的长度最大值可以达到1<<30
扩容过程会先确定新的table长度，和新的阈值threshold
当容量特别大的时候，可能会出现capacity*load_factor<threshold的情况
每次扩容的容量变为原来的2倍
申请好新的空间，并对旧数组的元素迁移
可以看出，映射到数组中的规则是
e.hash&(newCap-1)
由于newCap只可能是$2^n(n>=0)$，因此与出来的结果只会改变1位
由于容量扩充为原来的两倍，因此，旧的元素的位置迁移到新的数组中时，位置只有可能是

1. 原来的位置
2. 原来的位置+原来的数组长度

为什么会设置树化的阈值为8?
根据java8中的注释

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
more: less than 1 in ten million

当hash的结果均匀的时候，达到8以上的可能性极小
还有一个原因，红黑树的高度在3的时候，最多可以容纳7个节点

当节点为普通节点时，直接放入新的位置
当节点为红黑树节点时，调用红黑树的拆分方法，放到对应的位置
当节点为链表时，将链表分为两部分放到新的位置和原来的位置

do {
    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;
    }
} while ((e = next) != null);
if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
}
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}

这一段是链表放到放到新的位置和旧的位置的代码，e.hash&oldCap可以快速判断该节点是属于位置1还是位置2

clear

public void clear() {
    Node<K,V>[] tab;
    modCount++;
    if ((tab = table) != null && size > 0) {
        size = 0;
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
    }
}

清空map，将ta中所有元素置为null，并设置size=0

containsKey

public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

是否包含key值，直接调用getNode如果返回的不是空值，则返回true

containsValue

public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

是否包含Value值，遍历每一个table中的元素，并对每一个元素判断是否相同，这里的元素无论是链表还是红黑树，都使用next获取下一个元素(HashMap中的TreeNode继承LinkedHashMap中的Entry，Entry继承了HashMap的Node，Node中包含了next元素）

get

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

get方法，调用getNode，对null特判，返回节点的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;
}

不难理解，get方法对于null和长度为空等情况特判，判断是否是链表还是红黑树，然后返回节点的value，如果找不到则返回null

remove

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

移除节点，调用对应的removeNode方法

final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                            (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                                (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

先对null等情况特判，然后寻找该节点，单个节点，红黑树，链表，分三种情况寻找
找到之后，分三种情况，删除该节点，并返回该节点
size–，修改次数modCount++
如果找不到则返回null

replace

public boolean replace(K key, V oldValue, V newValue) {
    Node<K,V> e; V v;
    if ((e = getNode(hash(key), key)) != null &&
        ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
        e.value = newValue;
        afterNodeAccess(e);
        return true;
    }
    return false;
}

replace方法基本与put方法一致

 public boolean replace(K key, V oldValue, V newValue) {
    Node<K,V> e; V v;
    if ((e = getNode(hash(key), key)) != null &&
        ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
        e.value = newValue;
        afterNodeAccess(e);
        return true;
    }
    return false;
}

有一个重载，会判断oldValue是否与e.value一致

补充

HashMap继承了AbstractMap并实现了Map接口和Cloneable、Serializable接口

参考资料

• JDK1.8源码
• Java8系列之重新认识HashMap