源码阅读-HashMap

HashMap的原理就是用一个数组存储一系列 K-V 结构的 Node 实体，存储位置通过对 key 的 hashCode 计算得到，Node 对象有 next 指针，作为单链表的一个节点。如果发生 hash 冲突，就将新的 Node 插入链表里。链表过长超过阈值的话为了提高查询效率会转为红黑树（JDK 1.8以后）。

成员变量

//默认初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认负载因子 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//桶中链表树化的阈值 8
static final int TREEIFY_THRESHOLD = 8;
//树转为链表的阈值 6
static final int UNTREEIFY_THRESHOLD = 6;
//table最小树化容量 64
static final int MIN_TREEIFY_CAPACITY = 64;
//hashmap 中键值对的个数
transient int size;
//扩容阈值（容量×载因子）
int threshold;
//真正存放数据的地方
transient Node<K,V>[] table;

hashMap默认初始化长度是多少？为什么是这么多？

默认初始化长度是 1<<< 4，之所以不直接写16，是因为位运算比算术运算效率高，之所以选择16，是为了服务与 index 的计算公式 index = hash & (length - 1)（这里采用与运算和取模的效果一样，但性能更好），初始化长度减1后为15，二进制位1111，和 hash 值运算后的结果等同于 hash 后几位的值，只要 hash 值本身分布均匀，那 hash 算法的结果就是均匀的，从而实现均匀分布。

为什么树化标准是8个？

在源码注释中有提到：如果 hashCode 分布良好的话，很少出现链表比较长的情况。理想情况下，链表的长度符合泊松分布。各长度的概率如下

/* 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
 */

当链表长度为8时，概率为0.00000006，概率非常小，红黑树的转换基本不会发生。当然也会有用到：用户使用自己的 hash 算法，导致 hashCode 分布离散很差，链表很长的情况。

为什么树退化为链表的阈值是6个？

增加一个过渡，防止在临界值时增加/删除一个元素时，在树和链表之间频繁的转换，降低性能。

初始化方法

// 最常用的一个，负载因子0.75
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 指定初始化容量，负载因子0.75
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 指定初始化容量和负载因子
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                loadFactor);
    this.loadFactor = loadFactor;
    // 取二次幂里比指定容量大且最接近的一个，比如指定容量10，则输出16
    this.threshold = tableSizeFor(initialCapacity);
}
// 将传入的map的键值对复制一份放hashmap里，不常用
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

hash方法

hash() 方法是 HashMap 的核心方法，算出 key 的 hashCode 后，将算出的结果右移16位，与原 hashCode 按位异或得到 hash 后的值，

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

为什么要右移16位？

让 hashCode 的高16位也参与运算，增加扰动，减少碰撞冲突，因为大部分元素的 hashCode 在低位是相同的。

相关问题：String的hashCode的实现？

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;
        
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

简单来说就是给字符串的每一位，按位乘31的n次幂，再相加，用自然溢出来等效取模。选择31因为这个质数不大不小，且可以被虚拟机优化，运算效率更高。i*31 = i*(32-1) = i<<5-1

put方法

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // tab:引用当前HashMap的散列表
    // p:表示当前散列表的元素
    // n:当前散列表数组长度
    // i:表示路由寻址结果
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 延迟初始化逻辑，第一次调用putVal方法时初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 找到的桶位为null,将key,valuef封装成node对象，放进去就ok
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 桶位中的元素与当前插入元素的key一致，后续会进行value的替换操作
        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;
                }
                // 找到一个元素与当前要插入的元素的key一致
                if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 找到了一致的元素，用新的value替换原来的value
        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;
}

在 putVal 方法中为什么要用 i = (n-1) & hash 作为索引运算呢？

这其实是种优化手段，由于数组的大小永远是一个2次幂，在扩容后，一个元素的新索引要么在原位置，要么在原位置+扩容前的容量。这个方法的巧妙处全在于&运算，&运算只会关注 n-1（n=数组长度）的有效位，当扩容后，n的有效位相比之前会多增加一位（n会变成之前的两倍，所以确保数组长度永远是2次幂很重要），然后只需要判断 hash 在新增的有效位的位置是 0 还是 1 就可以算出新的索引位置，如果是 0，如果是 2，索引就是原索引+扩容前的容量。

resize方法

resize()方法主要是用来扩容，具体操作是新建一个hash表，然后将旧表中的内容重新散列复制到新表中。源码主要分为2部分：

• 第一部分主要用于判断当前操作的类型（初始化or扩容）并且计算出新生成的表的容量和阈值。
• 第二部分只用于扩容操作时，将旧表中的元素重新散列放入新表。

//扩容方法
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table; // 引用扩容前的哈希表
    int oldCap = (oldTab == null) ? 0 : oldTab.length;  // 扩容前table的容量
    int oldThr = threshold;     // 扩容前的阈值
    int newCap, newThr = 0;
    if (oldCap > 0) {
        // 扩容前table数组大小已达到最大值，则不扩容，且扩容条件设置为int最大值
        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
    }
    // oldCap==0，oldThr>0 说明哈希表中的散列表还未初始化，在使用带参构造的时候会发生
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    //oldCap==0，oldThr>0 使用无参构造的时候
    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) {
                // 方便JVM回收内存
                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;
                        // 通过将hash值与 oldCap 相与，将原来的链表拆分为高位链、低位链
                        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;    //放进新table
                    }
                }
            }
        }
    }
    return newTab;
}

get方法

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) {
        // 第一种情况：定位出的桶元素即为要get的数据
        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;
}

remove方法

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

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