HashMap浅析 - 969251639/study GitHub Wiki

HashMap是所有java都不会陌生的一个类,一个合格的java程序员一定要深入的一个知识点。

首先,HashMap继承了AbstractMap,实现了Map,Cloneable,Serializable接口,说明它有基本的Map的功能实现,也有克隆,可序列化的功能。

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

接下来是几个主要的成员变量

//默认容量大小,即2的4次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16(10000)
//最大的容量大小,即2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;//(1000000000000000000000000000000)
//默认的负载因子,即当容量被使用超过75%时需要扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//当一个桶的数量大小超过8(包含8)时转红黑树存储
static final int TREEIFY_THRESHOLD = 8;

//存储桶的数组
transient Node<K,V>[] table;
//存储Key,Value的Set
transient Set<Map.Entry<K,V>> entrySet;
//实际存储的键值对的数量
transient int size;
//修改次数
transient int modCount;
//容器大小,默认为上面的DEFAULT_INITIAL_CAPACITY 
int threshold;
//当容量被使用超过loadFactor%时需要扩容,默认为上面的DEFAULT_LOAD_FACTOR
final float loadFactor;

可以看到HashMap用于存储的也是一个数组结构,称之为节点,也就是一个桶

    transient Node<K,V>[] table;
    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;
        }
    }

可以看到一个节点包含了hash值,key,value和指向联编第一个元素的指针(hash冲突时用链表,所有有该指针,并且是单向),其中重写了hashcode方法和equals方法,大概如下结构存放(Node本身也是个Entry,next指向下一个Entry,即Entry1): 注:当一个Node下面的数量大于或等于threshold时会从链表转成红黑树结构进行存储

接下来看它的构造方法

    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and load factor.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    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;
        this.threshold = tableSizeFor(initialCapacity);
    }

    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and the default load factor (0.75).
     *
     * @param  initialCapacity the initial capacity.
     * @throws IllegalArgumentException if the initial capacity is negative.
     */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * Constructs an empty <tt>HashMap</tt> with the default initial capacity
     * (16) and the default load factor (0.75).
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    /**
     * Constructs a new <tt>HashMap</tt> with the same mappings as the
     * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
     * default load factor (0.75) and an initial capacity sufficient to
     * hold the mappings in the specified <tt>Map</tt>.
     *
     * @param   m the map whose mappings are to be placed in this map
     * @throws  NullPointerException if the specified map is null
     */
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

共4个,比较简单,无非就是设置下容量大小或者负载因子或者是初始化另一个容器的内容

获取数量和容器是否为空都直接用size变量即可

    public int size() {
        return size;
    }
    public boolean isEmpty() {
        return size == 0;
    }

接下来就重点分析它的增删改查
1. get方法

    public V get(Object key) {
        Node<K,V> e;
        //调用getNode方法,如果为空就返回null,否则返回Entry.value
        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;
        /**
         * 1. 判断当前存放数据的table是否为空,为空返回null -> (tab = table) != null
         * 2. 判断容器内的key,value数量是否0,为0返回null -> (n = tab.length) > 0
         * 3. 根据hash值计算出对应的桶位置,并且桶的第一个位置的Entry不能空,即该Node上肯定有存放Entry -> (first = tab[(n - 1) & hash]) != 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))))//判断链表的第一个Entry是否是需要get的Entry
                return first;
            if ((e = first.next) != null) {//如果Entry有下一个Entry,则遍历节点下的Entry
                if (first instanceof TreeNode)//如果存放的Entry是红黑树,则走红黑树的获取方法
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {//遍历链表,直至找到对应的Entry,这里需要注意的是判断一个key相等需要满足两个条件
                    if (e.hash == hash && //1. 两个key计算出来的hash值要相等
                        ((k = e.key) == key || (key != null && key.equals(k))))//2. 两个key的地址引用相等或调用equals方法相等
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

2. 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) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //如果是空容器,那么直接调用resize,创建一个新的出来
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //如果根据hash值找出对应的Node是null,说明该Node上没有任何Entry,直接newNode一个新的放进去
        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))))//如果key相同,则覆盖,这里是Node的第一个Entry
                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);//创建一个新的Entry,且上一个Entry的next指向它
                        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))))//如果key相同,则覆盖
                        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;//修改次数+1
        if (++size > threshold)//是否需要扩容
            resize();
        afterNodeInsertion(evict);//空方法,用于put成功后回调
        return null;
    }
    void afterNodeInsertion(boolean 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 扩容后的大小,原来的大小左移一位,即oldThr * 2,也就是按两倍扩容
        }
        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;//将新的存储节点的数组赋给table
        if (oldTab != null) {//如果旧容器不为空,开始迁移
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {//如果对应的Node有Entry
                    oldTab[j] = null;//方便GC
                    if (e.next == null)//没有下一个,也就是该Node只存储了一个Entry,没有桶冲突的情况
                        //直接通过hash值放到新容器中,这里是不需要重新计算hash,放的位置直接根据容器的数量即可确定位置
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)//红黑树的存放方式
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order 哈希碰撞情况,迁移该Node下的链表Entry
                        //高低位链表的头结点、尾节点
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {//遍历链表,直至next == null
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {//判断将旧Entry放到新容器中的高位还是低位节点
                                if (loTail == null)//Node为空,存放第一个Entry
                                    loHead = e;
                                else//否则存放在next节点下
                                    loTail.next = e;
                                loTail = e;//将自己置为尾节点
                            }
                            else {
                                if (hiTail == null)//Node为空,存放第一个Entry
                                    hiHead = e;
                                else//否则存放在next节点下
                                    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;
    }

注:由于HashMap是非线程安全,多线程下还是不建议用,另外jdk1.8跟之前的旧版本有些不太一样。

//在扩容时计算出新的threshold和capacity后就直接将新的table赋给当前map了,那么这时候新的table是空,多线程下如果有线程在这个过程中去get有可能get到空数据,但这样做带来了另一个好处是可以让更少的线程去参与resize,防止数据混乱,因为在搬运数据前其他线程的put数据都会put到新的table中去,而旧版本是先搬运数据,搬运完后才去覆盖旧的table,那么多线程下肯定有很多线程去做resize;另外重组数据的时候旧版本是倒序插入到新table,而jdk1.8是不改变顺序,解决了死循环问题
table = newTab;//将新的存储节点的数组赋给table

put的另一个重要方法是newNode,也就是真正存储内容的数据结构;

    Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
        return new Node<>(hash, key, value, next);
    }
    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;
        }
    }

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

上面的代码比较简单,先通过key找到对应的位置是否有Entry,如果有则有两种情况

  1. 命中的Node上的第一个元素就是要remove的Entry,即node == p这种情况,那么只需要将原有的node.next赋给Node的第一个Entry
  2. 命中的Node不是第一个元素,那么需要将待remove的Entry的next赋给它的前一个Entry的next即p.next = node.next
⚠️ **GitHub.com Fallback** ⚠️