HashMap源码

时间:2021-7-3 作者:qvyue
public class HashMap extends AbstractMap
    implements Map, Cloneable, Serializable {

    private static final long serialVersionUID = 362498820763181265L;

    /**
     * The default initial capacity - MUST be a power of two.
     * map的默认大小。必须为2的幂次方。因为只需要左移一位即可完成扩容。
     * 附:1左移4位即10000。2的4次方。
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 =扩容阈值时,触发扩容机制。即 容量 * 2
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * The bin count threshold for using a tree rather than list for a
     * bin.  Bins are converted to trees when adding an element to a
     * bin with at least this many nodes. The value must be greater
     * than 2 and should be at least 8 to mesh with assumptions in
     * tree removal about conversion back to plain bins upon
     * shrinkage.
     * 1.8版本新增参数。树化阈值。当链表中数量大于此阈值时触发树化操作。
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * The bin count threshold for untreeifying a (split) bin during a
     * resize operation. Should be less than TREEIFY_THRESHOLD, and at
     * most 6 to mesh with shrinkage detection under removal.
     * 1.8版本新增参数。反树化阈值。当链表中小于此阈值时触发反树化操作。
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * The smallest table capacity for which bins may be treeified.
     * (Otherwise the table is resized if too many nodes in a bin.)
     * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
     * between resizing and treeification thresholds.
     * 1.8版本新增参数。最小树化数组容量。接上两个参数。当数组的容量小于此值时,
     * 即便链表中数量大于树化阈值,也不会触发树化操作。参考treeifyBin()方法中的使用。
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

    /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     * Map的基础元素。
     */
    static class Node implements Map.Entry {
        final int hash;// key的hash值,直接保存,减少比对过程中的hash运算次数。
        final K key;
        V value;
        Node next;

        Node(int hash, K key, V value, Node 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; }

       /**
        * 众所周知,重写了hashcode()方法,就必须要重写equals()方法
        * 对key和value进行hashcode运算,然后异或运算(^)。(只有0和1异或才能得1)
        * 2 ^ 6 = 4 
        *   0010(2)
        * ^ 0110(6)
        * ---------
        *   0100(4)
        * 另外,Object.hashCode()这个方法,只是将数据转换为十进制。
        * 即,Object.hashCode("a")=97; Object.hashCode(123456)=123456
        */
        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;
        }
    }

    /* ---------------- Static utilities -------------- */

    /**
     * 较为重要的一个方法,对key进行hash运算。
     * 这块儿1.8之后有了优化。因为1.8后有了红黑树,所以此hash算法优化的更简单了。
     * 1、如果key是null,获取到的值为0,即数组为0的下标位置。
     * 2、对key进行hashCode运算,同时,进行右移16位并做异或运算。
     * 
     * 为什么是16位呢?
     * 因为hashCode返回类型是int,最大为2的32次幂-1,也就是最大32位。
     * 拿高16位和低16位进行位运算,也叫扰动函数。
     * 1是位运算效率极高;2是降低hash碰撞的概率。
     */
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    /**
     * Returns x's Class if it is of the form "class C implements
     * Comparable", else null.
     *
     * Comparable这个接口,强行对实现它的每个类的对象进行整体排序。
     * 这个方法功能很简单,就是判断x是否实现了Comparable接口。
     * 如果实现了,就返回x的class类,否则返回null。
     *
     * 查询这个方法在本类中的使用,我们会发现这个功能是为了给TreeNode使用的。
     * 如果方法返回了null,下一步会执行tieBreakOrder()方法。
     *
     * 简单来说,如果key实现了Comparable接口,那就直接进行比较;如果没有,那就自定义一个去比较。
     * 这块儿需要结合TreeNode的查询操作看。
     */
    static Class> comparableClassFor(Object x) {
        if (x instanceof Comparable) {
            Class> c; Type[] ts, as; Type t; ParameterizedType p;
            if ((c = x.getClass()) == String.class) // bypass checks
                return c;
            if ((ts = c.getGenericInterfaces()) != null) {
                for (int i = 0; i  kc, Object k, Object x) {
        return (x == null || x.getClass() != kc ? 0 :
                ((Comparable)k).compareTo(x));
    }

    /**
     * Returns a power of two size for the given target capacity.
     * 这是位运算。(废话)。作者是真的牛逼。代码还少,效率还高。
     *
     * 获取第一个大于当前给定数据的2次幂数据。为防止直接给了2次幂数据,所以计算前先-1.
     * (比如,设置了5,经过此方法计算结果为8。设置了8,计算结果也为8)
     *
     * 目的就是用最高位的1替换所有低位。写个极端的例子。
     *   1000000000000001 
     *   0100000000000000  (>>> 1)
     *  ------------------
     *   1100000000000001  (或运算结果)
     *   0011000000000000  (>>> 2)
     *  ------------------
     *   1111000000000001  (或运算结果)
     *   0000111100000001  (>>> 4)
     *  ------------------
     *   1111111100000001  (或运算结果)
     *   0000000011111111  (>>> 8)
     *  ------------------
     *   1111111111111111  (或运算结果)
     *   0000000000000000  (>>> 16)
     *  ------------------
     *   1111111111111111  (最终结果)
     *
     * 获取到最终结果,只需要加1,即变成2的次幂数(2的16次幂)。
     */
    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 = MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

    /* ---------------- Fields -------------- */

    /**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     *
     * 后面几个参数都没再细看。注意关键字transient。
     */
    transient Node[] table;

    /**
     * Holds cached entrySet(). Note that AbstractMap fields are used
     * for keySet() and values().
     */
    transient Set> entrySet;

    /**
     * The number of key-value mappings contained in this map.
     */
    transient int size;

    /**
     * The number of times this HashMap has been structurally modified
     * Structural modifications are those that change the number of mappings in
     * the HashMap or otherwise modify its internal structure (e.g.,
     * rehash).  This field is used to make iterators on Collection-views of
     * the HashMap fail-fast.  (See ConcurrentModificationException).
     */
    transient int modCount;

    /**
     * The next size value at which to resize (capacity * load factor).
     *
     * @serial
     */
    // (The javadoc description is true upon serialization.
    // Additionally, if the table array has not been allocated, this
    // field holds the initial array capacity, or zero signifying
    // DEFAULT_INITIAL_CAPACITY.)
    // 这个关键字是扩容阈值。当数组的size大于它的时候会触发扩容操作。
    int threshold;

    /**
     * The load factor for the hash table.
     * 加载因子。上面有个默认加载因子0.75。
     *
     * @serial
     */
    final float loadFactor;

    /* ---------------- Public operations -------------- */

    /**
     * Constructs an empty HashMap 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  MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor HashMap 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 HashMap 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 HashMap with the same mappings as the
     * specified Map.  The HashMap is created with
     * default load factor (0.75) and an initial capacity sufficient to
     * hold the mappings in the specified Map.
     *
     * @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);
    }

    /**
     * Implements Map.putAll and Map constructor
     *
     * @param m the map
     * @param evict false when initially constructing this map, else
     * true (relayed to method afterNodeInsertion).
     *
     * a.putAll(b) -> b为空就直接结束。
     * 如果a为空,那么要对a进行初始化操作。
     * 上面if里面的逻辑,实际上就是为了通过b的大小来设置a合适的默认空间大小(2的幂次方)。
     * (个人推测:可能初始化b时给b设置容量为256,但是实际b只用了2,那么这里就已2为准,推测出a的合适大小。)
     * 如果b不为空,那么就判断b是否需要扩容。
     * 这块儿逻辑比较奇怪,put的时候不是会扩容吗?为什么这里还要判断一下?
     *
     * 在下面的for循环里面,实际上就是进行真正的put操作了。
     */
    final void putMapEntries(Map extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            if (table == null) { // pre-size
                // 由m的实际大小/加载因子,简单推测之前map的默认大小;
                // +1是为了向上取整数。比如计算结果为13.66,+1就是14.66,下面int强转时候变成14。
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft  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);
            }
        }
    }

    /**
     * Returns the number of key-value mappings in this map.
     *
     * @return the number of key-value mappings in this map
     */
    public int size() {
        return size;
    }

    /**
     * Returns true if this map contains no key-value mappings.
     *
     * @return true if this map contains no key-value mappings
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * 

More formally, if this map contains a mapping from a key * {@code k} to a value {@code v} such that {@code (key==null ? k==null : * key.equals(k))}, then this method returns {@code v}; otherwise * it returns {@code null}. (There can be at most one such mapping.) * *

A return value of {@code null} does not necessarily * indicate that the map contains no mapping for the key; it's also * possible that the map explicitly maps the key to {@code null}. * The {@link #containsKey containsKey} operation may be used to * distinguish these two cases. * * @see #put(Object, Object) */ public V get(Object key) { Node e; return (e = getNode(hash(key), key)) == null ? null : e.value; } /** * Implements Map.get and related methods * * @param hash hash for key * @param key the key * @return the node, or null if none * * 这里记录一下。和putVal()方法一样。 * 数组 + 链表 + 红黑树的结构, * 如果是链表,数组下标处存的就是Node,通过next查找下一个; * 如果是红黑树,数组下标处存的就是TreeNode,通过find寻找下一个。 */ final Node getNode(int hash, Object key) { Node[] tab; Node first, e; int n; K k; // 判断当前map不为空 // put的时候,根据key的hash值和数组大小进行与运算,获取到要存储的数组位置然后插入; // 所以get的时候,直接判断该数组位置不能为空。 // 这里有个小知识点。【在tab为2次幂时,hash % tab = tab[(n - 1) & hash]】。 // 总结说,我们要对hash值对数组长度取余,获取到具体的数组下标。 // 但是,数组长度是2次幂,所以正好可以用位运算将取余的操作替换掉,更提高了效率。 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // 从第一个开始查,判断key是否相等,key的hash是否相等 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)first).getTreeNode(hash, key); // 是链表,就直接从上往下遍历,判断key和key的hash值是否相等。 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; } /** * Returns true if this map contains a mapping for the * specified key. * * @param key The key whose presence in this map is to be tested * @return true if this map contains a mapping for the specified * key. * 还是走的上面方法 */ public boolean containsKey(Object key) { return getNode(hash(key), key) != null; } /** * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, the old * value is replaced. * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with key, or * null if there was no mapping for key. * (A null return can also indicate that the map * previously associated null with key.) */ public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } /** * Implements Map.put and related methods * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none * * 这里记录一下。和getNode()方法一样。 * 数组 + 链表 + 红黑树的结构, * 如果是链表,数组下标处存的就是Node,通过next查找下一个; * 如果是红黑树,数组下标处存的就是TreeNode,通过find寻找下一个。 */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; // 当前map为空,就初始化它的size 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); // 数组下标的数据存在,hash冲突了 else { Node e; K k; // 判断数组下标处的key和当前put的key是否相同。如果相同,就直接替换value值。 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 判断它的数据结构,是红黑树。 else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); // 是链表。 else { // 死循环,遍历查找 for (int binCount = 0; ; ++binCount) { // 它的下一个Node节点为空 if ((e = p.next) == null) { // 1、将值指定为当前Node的next();也就是尾插法 p.next = newNode(hash, key, value, null); // 2、判断是否需要触发树化操作 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // key和key的hash值比较,重复了。那就直接替换value值 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 如果,key对应的node为空,那么e为新数据;如果key对应的node不为空,那么e为旧数据。 if (e != null) { // existing mapping for key V oldValue = e.value; // 如果onlyIfAbsent为true,那么不修改已有数据。不过一般情况都为false。 if (!onlyIfAbsent || oldValue == null) e.value = value; // LinkedHashMap实现了具体的方法,就是把当前节点移至尾部。尾插法。 afterNodeAccess(e); return oldValue; } } ++modCount; // 判断是否需要扩容 if (++size > threshold) resize(); // LinkedHashMap实现了具体的方法,注释为:possibly remove eldest // 当初始化的时候,evict是false,其他情况为true。 // 如果我们设置了它的最大值100,当数量超过100的时候,这个方法支持删除最老的元素。 afterNodeInsertion(evict); return null; } /** * Initializes or doubles table size. If null, allocates in * accord with initial capacity target held in field threshold. * Otherwise, because we are using power-of-two expansion, the * elements from each bin must either stay at same index, or move * with a power of two offset in the new table. * * 首先,什么时候会触发resize()方法?当map中数据的容量大于扩容阈值threshold时,或map为空初始化时。 * * * @return the table */ final Node[] resize() { Node[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; // 旧map不为空 if (oldCap > 0) { // 旧map已满,重写下扩容阈值直接返回旧map。 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 旧map容量*2后小于最大容量并且旧map容量大于默认容量,旧的扩容阈值*2。 else if ((newCap = oldCap = DEFAULT_INITIAL_CAPACITY) newThr = oldThr 0) // initial capacity was placed in threshold newCap = oldThr; // 初始化无参map时走此分支,初始化容量和扩容阈值。 else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 什么时候newThr为空? // 往上看,1、初始化有参map时,2、扩容时,oldCap小于默认初始化大小,都没给newThr赋值; if (newThr == 0) { // 进来的目的是什么?ft是获取到了扩容阈值;同时设置新map的扩容阈值; float ft = (float)newCap * loadFactor; newThr = (newCap [] newTab = (Node[])new Node[newCap]; table = newTab; // oldTab==null就是初始化逻辑。 // 所以,下面逻辑才是真正的扩容要走的。旧map中的数据转移到新map中去。 if (oldTab != null) { // 遍历旧map中每一个数据 for (int j = 0; j e; // 将数据赋值给e if ((e = oldTab[j]) != null) { // 数组清空一位 oldTab[j] = null; // 链表结构下,如果数组下标下的数据只有一条数据, // 那么直接开始当前数组下标下数据的转移。 if (e.next == null) newTab[e.hash & (newCap - 1)] = e; // 如果是红黑树结构,那么通过split方法进行拆分。具体后聊。 else if (e instanceof TreeNode) ((TreeNode)e).split(this, newTab, j, oldCap); // 链表结构下,当前数组下标下的数据,还有next else { // preserve order Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node next; /** * 这块儿好好写下。 * * 与运算的时候,两边都为1,结果才为1。 1010 & 0110 = 0010 * * 我们put/get的时候,都是通过hash & [cap - 1],来定位所存放的数组位置。 * 但是在这里,稍微有些不同,与运算时候,是通过cap。 * * oldCap = 8;我们插入时,需要拿hash与7进行与运算。 * 1、9、17、25这四条数据与运算的结果都是1。也就是在数组1位置形成链表。 * * 现在,拿hash与8进行与运算,结果为[0 8 0 8] * 那也就是说, * 1和17组成新的链表,位置为1; * 9和25组成新的链表,位置为1+8; * */ do { next = e.next; // 与原oldCap与运算的结果只有两种:0、oldCap。 // 还是采用的尾插法插入数据。 if ((e.hash & oldCap) == 0) { // 为0的时候,存放lo相关; if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { // 为cap的时候,存hi相关; if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); // 遍历两个链表。lo链表直接移入对应数组下标处, // hi链表移入[j + oldCap]对应数组下标处; if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; } /** * Replaces all linked nodes in bin at index for given hash unless * table is too small, in which case resizes instead. */ final void treeifyBin(Node[] tab, int hash) { int n, index; Node e; if (tab == null || (n = tab.length) hd = null, tl = null; do { // 创建一个以tl为头结点的类似于双向链表结构的树型结构。 TreeNode p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) // 真正的树化操作 hd.treeify(tab); } } /** * Copies all of the mappings from the specified map to this map. * These mappings will replace any mappings that this map had for * any of the keys currently in the specified map. * * @param m mappings to be stored in this map * @throws NullPointerException if the specified map is null */ public void putAll(Map extends K, ? extends V> m) { putMapEntries(m, true); } /** * Removes the mapping for the specified key from this map if present. * * @param key key whose mapping is to be removed from the map * @return the previous value associated with key, or * null if there was no mapping for key. * (A null return can also indicate that the map * previously associated null with key.) */ public V remove(Object key) { Node e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } /** * Implements Map.remove and related methods * * @param hash hash for key * @param key the key * @param value the value to match if matchValue, else ignored * @param matchValue if true only remove if value is equal * @param movable if false do not move other nodes while removing * @return the node, or null if none */ final Node removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node[] tab; Node p; int n, index; // 简单的判空操作。数组不为空、长度不为0,数组下标下的数据不为空 if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { Node node = null, e; K k; V v; // 判断数组下标处的数据是否为我们需要查找的数据 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) node = p; // p的下一个节点不为空,判断它的数据结构,并准备遍历 else if ((e = p.next) != null) { // 走树的查找逻辑 if (p instanceof TreeNode) node = ((TreeNode)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)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; }

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:qvyue@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。