HashMap源码分析

HashMap

key、value形式存储数据

JDK8：数组 + 链表/红黑树

hash

static final int hash(Object key) {
    int h;
    // hashCode ^ hashCode >>> 16，可防止一些特殊的hashCode例如Double、Float，因为它们的低16位基本全是0
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

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;
    // 当前table不为null且长度大于0, 并且头结点不为null
    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;
        // 头结点的下一个节点不会null
        // 非头结点, 链表或者红黑树
        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;
}

put

// 会覆盖原有的值
// putIfAbsent 不会覆盖原来的值
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) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // table为null或者长度为0, 则初始化table
    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);
                    // 链表长度 >= 8
                    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;
            // 是否只在value不存在或者为null时, 赋值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // map大小 > 阈值
    if (++size > threshold)
        // 扩容
        resize();
    // 什么也没做
    afterNodeInsertion(evict);
    return null;
}

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) {
        // 超过 MAXIMUM_CAPACITY, 直接更新阈值
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 更新阈值和容量(阈值和容量都x2)
        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) {
        // 遍历旧table
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // 只有一个头结点, 则直接挂载到新table
                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
                    // 低位头部, 低位尾部
                    Node<K,V> loHead = null, loTail = null;
                    // 高位头部, 高位尾部
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 存入到新容量一半的左边
                        // 因为容量是2^n次, 所以是存入到低部还是高部
                        // 放入数据时所求下标(table.lenght - 1) & hash == (2^n - 1) & hash
                        if ((e.hash & oldCap) == 0) {
                           // 第二次进入loTail不等于null
                            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;
                    }
                    // 高位在 原始位置 + 旧的table的容量
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

remove

public V remove(Object key) {
    Node<K,V> e;
    // 移出成功返回移出节点的值, 失败返回null
    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;
    // table不为null 并且长度大于0 并且hash所对应的头结点不为null
    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);
            }
        }
        // 找到了
        // matchValue 是否需要匹配值
        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 是node的前一个节点
                // 将node移出
                p.next = node.next;
            ++modCount;
            --size;
            // 什么都没做，只是声明
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

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)
            // 所有头结点置null
            tab[i] = null;
    }
}

size

public int size() {
    return size;
}

containsValue

public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        // 遍历table
        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;
}

containsKey

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

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

values

// 返回所有值, 不是插入顺序, 而是HashMap的存储顺序
// Values并不能添加add，因为Value没有实现
// 但是有Iterator
public Collection<V> values() {
    Collection<V> vs = values;
    if (vs == null) {
        // Values
        vs = new Values();
        values = vs;
    }
    return vs;
}

getOrDefault

// 如果没有就返回设置的默认值
public V getOrDefault(Object key, V defaultValue) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}

putIfAbsent

// 不存在才添加, 且不会覆盖
public V putIfAbsent(K key, V value) {
    // 会返回旧的值, 如果有这个节点的话
    return putVal(hash(key), key, value, true, true);
}

replace

public V replace(K key, V value) {
    Node<K,V> e;
    // 通过key找到了
    if ((e = getNode(hash(key), key)) != null) {
        // 旧值保存
        V oldValue = e.value;
        // 换上新值
        e.value = value;
        // 什么都没做
        afterNodeAccess(e);
        // 返回旧值
        return oldValue;
    }
    return null;
}
// LinkedHashMap 有实现, HashMap并又没做什么
void afterNodeAccess(Node<K,V> p) { }

computeIfAbsent

public V computeIfAbsent(K key,
                         Function<? super K, ? extends V> mappingFunction) {
    // 未传入mappingFunction，抛异常
    if (mappingFunction == null)
        throw new NullPointerException();
    int hash = hash(key);
    Node<K,V>[] tab; Node<K,V> first; int n, i;
    int binCount = 0;
    TreeNode<K,V> t = null;
    Node<K,V> old = null;
    // 扩容或初始化table
    if (size > threshold || (tab = table) == null ||
        (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 头结点不为null
    if ((first = tab[i = (n - 1) & hash]) != null) {
        // 是否是红黑树
        if (first instanceof TreeNode)
            old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
        else {
            // 链表
            Node<K,V> e = first; K k;
            do {
                // 循环到链尾，或者找到对应节点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))) {
                    old = e;
                    break;
                }
                // 操作次数++
                ++binCount;
            } while ((e = e.next) != null);
        }
        V oldValue;
        // 对应key的节点存在直接返回
        if (old != null && (oldValue = old.value) != null) {
            afterNodeAccess(old);
            return oldValue;
        }
    }
    // 函数式接口apply方法参数为上方的key, 返回一个将要赋值到old上的value
    V v = mappingFunction.apply(key);
    // apply返回的V为null，直接返回
    if (v == null) {
        return null;
        // old的value赋值v, 对于链表存在old并且value为null
    } else if (old != null) {
        old.value = v;
        afterNodeAccess(old);
        return v;
    }
    // 添加到树中,对于红黑树,并且是root存在
    else if (t != null)
        t.putTreeVal(this, tab, hash, key, v);
    else {
        // 没有头结点
        // 以上都不是，则新建Node
        tab[i] = newNode(hash, key, v, first);
        if (binCount >= TREEIFY_THRESHOLD - 1)
            treeifyBin(tab, hash);
    }
    ++modCount;
    ++size;
    afterNodeInsertion(true);
    return v;
}

clone

public Object clone() {
    HashMap<K,V> result;
    try {
       	// 调用父类clone
        result = (HashMap<K,V>)super.clone();
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
    // 初始化成员变量
    result.reinitialize();
    // 将原数据装入到result中
    result.putMapEntries(this, false);
    return result;
}

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        // 初始化阈值
        if (table == null) { // pre-size
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        // 原map容量大于新map容量, 进行扩容
        else if (s > threshold)
            resize();
        // 将原map中的值装到新map中
        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);
        }
    }
}

forEach

public void forEach(BiConsumer<? super K, ? super V> action) {
    Node<K,V>[] tab;
    if (action == null)
        throw new NullPointerException();
    // 判定table不为null
    if (size > 0 && (tab = table) != null) {
        int mc = modCount;
        // 遍历table
        for (int i = 0; i < tab.length; ++i) {
            // 遍历头结点
            for (Node<K,V> e = tab[i]; e != null; e = e.next)
                // action消费
                action.accept(e.key, e.value);
        }
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}