HashMap原理

HashMap

HashMap是比较常用的集合类，要想更好的使用，了解原理是最好的方法

• HashMap是数组＋链表式的结构组成的

/**
 * 存储结构是node数组
 */
transient Node<K,V>[] table;

/**
 * 由node的属性可以看出存在链表结构
 */
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

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

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}
    

• 初始大小为16

/**
 * 初始化大小默认为16
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

• 默认扩容因子为0.75

/**
 * 默认扩容因子为0.75
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

• 当链表长度大于8的时候会转换成红黑树的结构

/**
 * 链表长度大于8则转换成为红黑树结构
 */
static final int TREEIFY_THRESHOLD = 8;

• 当红黑树大小小于6的时候会转换成链表的结构

/**
 * 红黑树结构小于6则转换成为链表结构
 */
static final int UNTREEIFY_THRESHOLD = 6;

• HashMap的key和value都是可以为null的
• 体现红黑树结构的源码

prve存在疑问，目前的理解是原链表中前一个节点，是为了记录以便转成链表结构时，方便设置节点关系，也就是Node中next属性

/**
 * 红黑树结构
 * parent 代表父节点
 * left 代表左子节点
 * right 代表右子节点
 * prve 代表链表转红黑树之前的节点，原链表中的前一个节点
 * 红黑树结构代码较多，这里只粘贴了部分，感兴趣可自行观看源码
 */
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

        /**
         * Returns root of tree containing this node.
         */
        final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
            }
        }
......