JAVA并发容器源码分析【二】ConcurrentHashMap源码翻译之基础

扫码关注公众号:Java 技术驿站

发送:vip
将链接复制到本浏览器,永久解锁本站全部文章

【公众号:Java 技术驿站】 【加作者微信交流技术,拉技术群】

文章首发于:clawhub.club


基于JDK8

        /* ---------------- Constants -------------- */

        /**
         * The largest possible table capacity.  This value must be
         * exactly 1<<30 to stay within Java array allocation and indexing
         * bounds for power of two table sizes, and is further required
         * because the top two bits of 32bit hash fields are used for
         * control purposes.
         * <p>
         * 最大的表容量。这个值必须恰好是1<<30,才能保持在Java数组分配和索引范围内,
         * 以获得两种表大小的幂,而且这个值是进一步需要的,因为32位哈希字段的前两位用于控制目的。
         */
        private static final int MAXIMUM_CAPACITY = 1 << 30;

        /**
         * The default initial table capacity.  Must be a power of 2
         * (i.e., at least 1) and at most MAXIMUM_CAPACITY.
         * 默认的表初始容量,必须是2的幂次方,最小是1,最大为MAXIMUM_CAPACITY
         */
        private static final int DEFAULT_CAPACITY = 16;

        /**
         * The largest possible (non-power of two) array size.
         * Needed by toArray and related methods.
         * 最大的数组大小(非2次幂)。toArray and related方法使用。
         */
        static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

        /**
         * The default concurrency level for this table. Unused but
         * defined for compatibility with previous versions of this class.
         * 表默认的并发级别,未使用,但为与该类的以前版本兼容而定义。
         */
        private static final int DEFAULT_CONCURRENCY_LEVEL = 16;

        /**
         * The load factor for this table. Overrides of this value in
         * constructors affect only the initial table capacity.  The
         * actual floating point value isn't normally used -- it is
         * simpler to use expressions such as {@code n - (n >>> 2)} for
         * the associated resizing threshold.
         * 表的默认加载因子,在构造函数中重写此值只影响初始表容量。
         * 通常不使用实际的浮点值 —— 对于相关的调整阈值,使用{@code n - (n >>> 2)}等表达式更简单。
         */
        private static final float 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.
         * 使用树(而不是列表)来设置bin计数阈值。当向至少具有这么多节点的bin添加元素时,bin将转换为树。
         * 该值必须大于2,并且应该至少为8,以便与树移除中关于收缩后转换回普通Bin的假设相吻合。
         */
        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.
         * 用于在调整大小操作期间反树化(拆分)bin的bin计数阈值,应该小于TREEIFY_THRESHOLD,
         * 最多6个,去吻合去缩检测。
         */
        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.)
         * The value should be at least 4 * TREEIFY_THRESHOLD to avoid
         * conflicts between resizing and treeification thresholds.
         * 最小的表容量,其中的箱子可以treeified。(否则,如果一个bin中有太多节点,则会调整表的大小。)
         * 该值应该至少为4 * TREEIFY_THRESHOLD,以避免调整大小和treeification阈值之间的冲突。
         */
        static final int MIN_TREEIFY_CAPACITY = 64;

        /**
         * Minimum number of rebinnings per transfer step. Ranges are
         * subdivided to allow multiple resizer threads.  This value
         * serves as a lower bound to avoid resizers encountering
         * excessive memory contention.  The value should be at least
         * DEFAULT_CAPACITY.
         * 每个转移步骤的最少复归数。范围被细分以允许多个调整大小的线程。
         * 此值用作下限,以避免调整大小器遇到过多的内存争用。
         * 该值至少应该是DEFAULT_CAPACITY。
         */
        private static final int MIN_TRANSFER_STRIDE = 16;

        /**
         * The number of bits used for generation stamp in sizeCtl.
         * Must be at least 6 for 32bit arrays.
         * 用于生成戳记的位的数目,单位为sizeCtl。
         * 32位数组必须至少为6。
         */
        private static int RESIZE_STAMP_BITS = 16;

        /**
         * The maximum number of threads that can help resize.
         * Must fit in 32 - RESIZE_STAMP_BITS bits.
         * 可以帮助调整大小的最大线程数。
         * 必须符合32-RESIZE_STAMP_BITS bits
         */
        private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;

        /**
         * The bit shift for recording size stamp in sizeCtl.
         * 用sizeCtl记录尺寸戳的位偏移。
         */
        private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;

        /*
         * Encodings for Node hash fields. See above for explanation.
         * 节点哈希字段的编码。见解释。
         */
        static final int MOVED = -1; // hash for forwarding nodes 转发节点的哈希
        static final int TREEBIN = -2; // hash for roots of trees 树根的哈希
        static final int RESERVED = -3; // hash for transient reservations 临时保留的哈希
        static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash 普通节点哈希的可用位

        /**
         * Number of CPUS, to place bounds on some sizings
         * cpu的数量,以限制某些大小
         */
        static final int NCPU = Runtime.getRuntime().availableProcessors();

        /**
         * For serialization compatibility.
         * 序列化的兼容性
         */
        private static final ObjectStreamField[] serialPersistentFields = {
                new ObjectStreamField("segments", Segment[].class),
                new ObjectStreamField("segmentMask", Integer.TYPE),
                new ObjectStreamField("segmentShift", Integer.TYPE)
        };

        /* ---------------- Nodes -------------- */

        /**
         * Key-value entry.  This class is never exported out as a
         * user-mutable Map.Entry (i.e., one supporting setValue; see
         * MapEntry below), but can be used for read-only traversals used
         * in bulk tasks.  Subclasses of Node with a negative hash field
         * are special, and contain null keys and values (but are never
         * exported).  Otherwise, keys and vals are never null.
         * 键值项。这个类永远不会作为用户可变的Map.Entry导出,但是可以用于批量任务中使用的只读遍历。
         * 具有负哈希字段的Node的子类是特殊的,包含空键和值(但从不导出)。否则,键和val永远不会为空。
         */
        static class Node<K, V> implements Entry<K, V> {
            //哈希码
            final int hash;
            //键
            final K key;
            //值
            volatile V val;
            //下一个节点
            volatile Node<K, V> next;

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

            public final K getKey() {
                return key;
            }

            public final V getValue() {
                return val;
            }

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

            public final String toString() {
                return key + "=" + val;
            }

            public final V setValue(V value) {
                throw new UnsupportedOperationException();
            }

            public final boolean equals(Object o) {
                Object k, v, u;
                Entry<?, ?> e;
                return ((o instanceof Map.Entry) &&
                        (k = (e = (Entry<?, ?>) o).getKey()) != null &&
                        (v = e.getValue()) != null &&
                        (k == key || k.equals(key)) &&
                        (v == (u = val) || v.equals(u)));
            }

            /**
             * Virtualized support for map.get(); overridden in subclasses.
             * 对map.get()的虚拟化支持;在子类覆盖。
             * h:待查找key的hash
             * k:待查找key
             */
            Node<K, V> find(int h, Object k) {
                //当前节点
                Node<K, V> e = this;
                //当如果当前节点不为空
                if (k != null) {
                    //迭代节点内的元素,获取制定的键的值
                    do {
                        K ek;
                        if (e.hash == h &&
                                ((ek = e.key) == k || (ek != null && k.equals(ek))))
                            return e;
                    } while ((e = e.next) != null);
                }
                return null;
            }
        }

        /* ---------------- Static utilities 静态工具 -------------- */

        /**
         * Spreads (XORs) higher bits of hash to lower and also forces top
         * bit to 0. Because the table uses power-of-two masking, sets of
         * hashes that vary only in bits above the current mask will
         * always collide. (Among known examples are sets of Float keys
         * holding consecutive whole numbers in small tables.)  So we
         * apply a transform that spreads the impact of higher bits
         * downward. There is a tradeoff between speed, utility, and
         * quality of bit-spreading. Because many common sets of hashes
         * are already reasonably distributed (so don't benefit from
         * spreading), and because we use trees to handle large sets of
         * collisions in bins, we just XOR some shifted bits in the
         * cheapest possible way to reduce systematic lossage, as well as
         * to incorporate impact of the highest bits that would otherwise
         * never be used in index calculations because of table bounds.
         * <p>
         * 将较高的哈希值扩展(XORs)为较低的哈希值,并将最高位强制为0。
         * 由于该表使用了2的幂掩码,因此仅在当前掩码之上以位为单位变化的散列集总是会发生冲突。
         * (已知的例子包括在小表中保存连续整数的浮点键集。)因此,我们应用一个转换,将更高位的影响向下传播。
         * 位扩展的速度、实用性和质量之间存在权衡。
         * 因为许多常见的散列集已经合理分布(所以不要受益于传播),在桶中我们用树来处理大型的碰撞,
         * 我们只是XOR一些改变以最划算的方式来减少系统lossage,以及最高位的影响,否则就不会因为表的边界而在索引计算中使用。
         */
        static final int spread(int h) {
            return (h ^ (h >>> 16)) & HASH_BITS;
        }

        /**
         * Returns a power of two table size for the given desired capacity.
         * See Hackers Delight, sec 3.2
         * 返回给定目标容量的2次幂
         */
        private static final int tableSizeFor(int c) {
            int n = c - 1;
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }

        /**
         * Returns x's Class if it is of the form "class C implements
         * Comparable<C>", else null.
         * 如果x实现了Comparable<C>接口,则返回此Class,否则返回null
         */
        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 < ts.length; ++i) {
                        if (((t = ts[i]) instanceof ParameterizedType) &&
                                ((p = (ParameterizedType) t).getRawType() ==
                                        Comparable.class) &&
                                (as = p.getActualTypeArguments()) != null &&
                                as.length == 1 && as[0] == c) // type arg is c
                            return c;
                    }
                }
            }
            return null;
        }

        /**
         * Returns k.compareTo(x) if x matches kc (k's screened comparable
         * class), else 0.
         * 比较大小
         */
        @SuppressWarnings({"rawtypes", "unchecked"}) // for cast to Comparable
        static int compareComparables(Class<?> kc, Object k, Object x) {
            return (x == null || x.getClass() != kc ? 0 :
                    ((Comparable) k).compareTo(x));
        }

        /* ---------------- Table element access 表元素访问,核心了-------------- */

        /*
         * Volatile access methods are used for table elements as well as
         * elements of in-progress next table while resizing.  All uses of
         * the tab arguments must be null checked by callers.  All callers
         * also paranoically precheck that tab's length is not zero (or an
         * equivalent check), thus ensuring that any index argument taking
         * the form of a hash value anded with (length - 1) is a valid
         * index.  Note that, to be correct wrt arbitrary concurrency
         * errors by users, these checks must operate on local variables,
         * which accounts for some odd-looking inline assignments below.
         * Note that calls to setTabAt always occur within locked regions,
         * and so in principle require only release ordering, not
         * full volatile semantics, but are currently coded as volatile
         * writes to be conservative.
         * 在调整大小时,易失性访问方法用于表元素以及正在进行中的下一个表的元素。
         * 调用者必须检查选项卡参数的所有使用是否为空。
         * 所有调用者还偏执地预先检查制表符的长度是否为零(或等效的检查),从而确保任何以散列值形式出现的索引参数(长度- 1)都是有效的索引。
         * 注意,要纠正用户的wrt任意并发性错误,这些检查必须对本地变量进行操作,这就解释了下面一些奇怪的内联分配。
         * 注意,对setTabAt的调用总是发生在锁定区域内,
         * 因此原则上只需要释放顺序,而不需要完全的volatile语义,但是目前将其编码为volatile写,以保持保守性。
         */

        @SuppressWarnings("unchecked")
        static final <K, V> Node<K, V> tabAt(Node<K, V>[] tab, int i) {
            //native 方法 获取当前节点
            return (Node<K, V>) U.getObjectVolatile(tab, ((long) i << ASHIFT) + ABASE);
        }

        static final <K, V> boolean casTabAt(Node<K, V>[] tab, int i,
                                             Node<K, V> c, Node<K, V> v) {
            //native 方法 cas 获取tab数组中索引为i的节点,如果是和c相同,则更新为节点v
            return U.compareAndSwapObject(tab, ((long) i << ASHIFT) + ABASE, c, v);
        }

        static final <K, V> void setTabAt(Node<K, V>[] tab, int i, Node<K, V> v) {
            // native 方法 更新节点
            U.putObjectVolatile(tab, ((long) i << ASHIFT) + ABASE, v);
        }

        /* ---------------- Fields 字段-------------- */

        /**
         * The array of bins. Lazily initialized upon first insertion.
         * Size is always a power of two. Accessed directly by iterators.
         * 桶的数组。在第一次插入时惰性初始化。大小总是2的幂。由迭代器直接访问。
         */
        transient volatile Node<K, V>[] table;

        /**
         * The next table to use; non-null only while resizing.
         * 要使用的下一个表;仅在调整大小时非空。
         */
        private transient volatile Node<K, V>[] nextTable;

        /**
         * Base counter value, used mainly when there is no contention,
         * but also as a fallback during table initialization
         * races. Updated via CAS.
         * 基本计数器值,主要在没有争用时使用,也可作为表初始化竞争期间的回退。通过CAS更新。
         */
        private transient volatile long baseCount;

        /**
         * Table initialization and resizing control.  When negative, the
         * table is being initialized or resized: -1 for initialization,
         * else -(1 + the number of active resizing threads).  Otherwise,
         * when table is null, holds the initial table size to use upon
         * creation, or 0 for default. After initialization, holds the
         * next element count value upon which to resize the table.
         * 表初始化和调整大小控制。当为负数时,表被初始化或调整大小:初始化为-1(1 +活动调整大小的线程的数量)
         * 否则,当表为空时,保留创建时使用的初始表大小,默认情况下为0。
         * 初始化之后,保存下一个元素count值,根据该值调整表的大小。
         * <p>
         * -1 :代表table正在初始化,其他线程应该交出CPU时间片
         * <p>
         * -N: 表示正有N-1个线程执行扩容操作(高 16 位是 length 生成的标识符,低 16 位是扩容的线程数)
         * <p>
         * 大于 0: 如果table已经初始化,代表table容量,默认为table大小的0.75,如果还未初始化,代表需要初始化的大小
         */
        private transient volatile int sizeCtl;

        /**
         * The next table index (plus one) to split while resizing.
         * 调整大小时要分割的下一个表索引(加上一个)。
         */
        private transient volatile int transferIndex;

        /**
         * Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
         * 自旋锁(通过CAS锁定),用于调整大小and/or 创建CounterCells。
         * cellsBusy是一个只有0和1两个状态的volatile整数
         * 它被当做一个自旋锁,0代表无锁,1代表加锁
         */
        private transient volatile int cellsBusy;

        /**
         * Table of counter cells. When non-null, size is a power of 2.
         * 计数器单元格表。当非空时,size是2的幂。
         */
        private transient volatile CounterCell[] counterCells;

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

        /**
         * Creates a new, empty map with the default initial table size (16).
         * 创建一个默认初始化容量为16的新的空的表
         */
        public ConcurrentHashMap() {
        }

        /**
         * Creates a new, empty map with an initial table size
         * accommodating the specified number of elements without the need
         * to dynamically resize.
         * 创建一个新的空映射,初始表大小可容纳指定数量的元素,而不需要动态调整大小。
         *
         * @param initialCapacity The implementation performs internal
         *                        sizing to accommodate this many elements. 初始容量
         * @throws IllegalArgumentException if the initial capacity of
         *                                  elements is negative
         */
        public ConcurrentHashMap(int initialCapacity) {
            if (initialCapacity < 0)
                throw new IllegalArgumentException();
            //如果初试容量大于最大初始容量无符号右移1位,则cap取值为最大初始容量,否则计算给定目标容量的最小2次幂的值
            int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                    MAXIMUM_CAPACITY :
                    tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
            //将表初始和扩容控制值 赋值
            this.sizeCtl = cap;
        }

        /**
         * Creates a new map with the same mappings as the given map.
         * 创建与给定映射具有相同映射的新映射。
         *
         * @param m the map
         */
        public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
            //默认表容量为16
            this.sizeCtl = DEFAULT_CAPACITY;
            //批量插入
            putAll(m);
        }

        /**
         * Creates a new, empty map with an initial table size based on
         * the given number of elements ({@code initialCapacity}) and
         * initial table density ({@code loadFactor}).
         * 用给定的初始容量和加载因子创建一个新的空的map,一个并发更新线程。
         *
         * @param initialCapacity the initial capacity. The implementation
         *                        performs internal sizing to accommodate this many elements,
         *                        given the specified load factor.  初始容量
         * @param loadFactor      the load factor (table density) for
         *                        establishing the initial table size 加载因子
         * @throws IllegalArgumentException if the initial capacity of
         *                                  elements is negative or the load factor is nonpositive
         * @since 1.6
         */
        public ConcurrentHashMap(int initialCapacity, float loadFactor) {
            this(initialCapacity, loadFactor, 1);
        }

        /**
         * Creates a new, empty map with an initial table size based on
         * the given number of elements ({@code initialCapacity}), table
         * density ({@code loadFactor}), and number of concurrently
         * updating threads ({@code concurrencyLevel}).
         * 根据给定的元素数量({@code initialCapacity})、表密度({@code loadFactor})和并发更新线程数量({@code concurrencyLevel})创建一个新的空映射,初始表大小。
         *
         * @param initialCapacity  the initial capacity. The implementation
         *                         performs internal sizing to accommodate this many elements,
         *                         given the specified load factor. 初始容量
         * @param loadFactor       the load factor (table density) for
         *                         establishing the initial table size 加载因子
         * @param concurrencyLevel the estimated number of concurrently
         *                         updating threads. The implementation may use this value as
         *                         a sizing hint. 并发等级
         * @throws IllegalArgumentException if the initial capacity is
         *                                  negative or the load factor or concurrencyLevel are
         *                                  nonpositive
         */
        public ConcurrentHashMap(int initialCapacity,
                                 float loadFactor, int concurrencyLevel) {
            //入参校验
            if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
                throw new IllegalArgumentException();

            //如果初始容量小于并发等级,则初始容量变为并发等级大小
            if (initialCapacity < concurrencyLevel)   // Use at least as many bins
                initialCapacity = concurrencyLevel;   // as estimated threads
            //计算表容量
            long size = (long) (1.0 + (long) initialCapacity / loadFactor);
            //如果表容量大于等于最大容量,则取最大容量值,否则取size值的最小2次幂的值
            int cap = (size >= (long) MAXIMUM_CAPACITY) ?
                    MAXIMUM_CAPACITY : tableSizeFor((int) size);
            //赋值 sizeCtl
            this.sizeCtl = cap;
        }

        // Original (since JDK1.2) Map methods
        // 原始的map方法

        /**
         * 计算容量
         * {@inheritDoc}
         */
        public int size() {
            long n = sumCount();
            return ((n < 0L) ? 0 :
                    (n > (long) Integer.MAX_VALUE) ? Integer.MAX_VALUE :
                            (int) n);
        }

        /**
         * 判断map是否为空
         * {@inheritDoc}
         */
        public boolean isEmpty() {
            return sumCount() <= 0L; // ignore transient negative values 忽略瞬时负值
        }

        /**
         * Returns the value to which the specified key is mapped,
         * or {@code null} if this map contains no mapping for the key.
         * <p>
         * 返回指定键映射到的值,如果此映射不包含键的映射,则返回{@code null}。
         *
         * <p>More formally, if this map contains a mapping from a key
         * {@code k} to a value {@code v} such that {@code key.equals(k)},
         * then this method returns {@code v}; otherwise it returns
         * {@code null}.  (There can be at most one such mapping.)
         * <p>
         * 更正式地说,如果这个映射包含一个键{@code k}到一个值{@code v}的映射,
         * 使得{@code key.equals(k)},那么这个方法返回{@code v};否则返回{@code null}。
         * (最多可以有一个这样的映射。)
         *
         * @throws NullPointerException if the specified key is null 如果指定的键为空
         */
        public V get(Object key) {
            Node<K, V>[] tab;
            Node<K, V> e, p;
            int n, eh;
            K ek;
            //扩展key的Hash值
            int h = spread(key.hashCode());
            //如果表格不为空且表格长度大于0且所查key的所在节点不为空,(n - 1) & h相当于取模操作,即获取其索引位置。
            if ((tab = table) != null && (n = tab.length) > 0 &&
                    (e = tabAt(tab, (n - 1) & h)) != null) {
                //如果获取到当前值
                if ((eh = e.hash) == h) {
                    if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                        //返回当前节点值
                        return e.val;
                }
                //如果当前节点hash值小于0,溢出的时候为负数
                else if (eh < 0)
                    //调用find方法,返回值,或者没找到则返回空
                    return (p = e.find(h, key)) != null ? p.val : null;
                //获取当前节点的下一个节点,如果非空,则判断是否相同,找到了即返回其值。
                while ((e = e.next) != null) {
                    if (e.hash == h &&
                            ((ek = e.key) == key || (ek != null && key.equals(ek))))
                        return e.val;
                }
            }
            return null;
        }

        /**
         * Tests if the specified object is a key in this table.
         * 测试指定的对象是否是该表中的键。
         *
         * @param key possible key 指定的键
         * @return {@code true} if and only if the specified object
         * is a key in this table, as determined by the
         * {@code equals} method; {@code false} otherwise
         * @throws NullPointerException if the specified key is null
         */
        public boolean containsKey(Object key) {
            return get(key) != null;
        }

        /**
         * Returns {@code true} if this map maps one or more keys to the
         * specified value. Note: This method may require a full traversal
         * of the map, and is much slower than method {@code containsKey}.
         * <p>
         * 如果此映射将一个或多个键映射到指定值,则返回{@code true}。
         * 注意:这个方法可能需要遍历整个map,并且比方法{@code containsKey}慢得多。
         *
         * @param value value whose presence in this map is to be tested
         * @return {@code true} if this map maps one or more keys to the
         * specified value
         * @throws NullPointerException if the specified value is null
         */
        public boolean containsValue(Object value) {
            if (value == null)
                throw new NullPointerException();
            Node<K, V>[] t;
            if ((t = table) != null) {

                //表遍历者,这个好消耗性能
                Traverser<K, V> it = new Traverser<K, V>(t, t.length, 0, t.length);
                for (Node<K, V> p; (p = it.advance()) != null; ) {
                    V v;
                    //存在此值,返回true
                    if ((v = p.val) == value || (v != null && value.equals(v)))
                        return true;
                }
            }
            return false;
        }

        /**
         * Maps the specified key to the specified value in this table.
         * Neither the key nor the value can be null.
         * <p>
         * 将指定的键映射到该表中的指定值。键和值都不能为空。
         *
         * <p>The value can be retrieved by calling the {@code get} method
         * with a key that is equal to the original key.
         * <p>
         * 可以通过调用{@code get}方法来检索该值,方法的键值等于原始键值。
         *
         * @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 {@code key}, or
         * {@code null} if there was no mapping for {@code key}
         * @throws NullPointerException if the specified key or value is null
         */
        public V put(K key, V value) {
            return putVal(key, value, false);
        }

        /**
         * Implementation for put and putIfAbsent
         * 实现put和putIfAbsent
         * onlyIfAbsent含义:如果我们传入的key已存在我们是否去替换,true:不替换,false:替换。
         */
        final V putVal(K key, V value, boolean onlyIfAbsent) {
            //键值都不为空
            if (key == null || value == null) throw new NullPointerException();
            //发散键的hash值
            int hash = spread(key.hashCode());
            //桶数量 0
            int binCount = 0;
            for (Node<K, V>[] tab = table; ; ) {
                Node<K, V> f;
                int n, i, fh;
                //检查表是否初始化
                if (tab == null || (n = tab.length) == 0)
                    //初始化表
                    tab = initTable();
                    //检查指定键所在节点是否为空
                else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                    //通过CAS方法添加键值对
                    if (casTabAt(tab, i, null,
                            new Node<K, V>(hash, key, value, null)))
                        break;                   // no lock when adding to empty bin 添加到空桶时没有锁
                }
                //如果当前节点的Hash值为MOVED
                else if ((fh = f.hash) == MOVED)
                    //如果还在进行扩容操作就先进行扩容
                    tab = helpTransfer(tab, f);
                else {
                    V oldVal = null;
                    //synchronized锁定此f节点
                    synchronized (f) {
                        //再次检测节点是否相同
                        if (tabAt(tab, i) == f) {
                            //如果此节点hash值大于0
                            if (fh >= 0) {
                                //桶数量为1
                                binCount = 1;
                                for (Node<K, V> e = f; ; ++binCount) {
                                    K ek;
                                    //获取到指定的键
                                    if (e.hash == hash &&
                                            ((ek = e.key) == key ||
                                                    (ek != null && key.equals(ek)))) {
                                        //保存老的值
                                        oldVal = e.val;
                                        //onlyIfAbsent:如果我们传入的key已存在我们是否去替换,true:不替换,false:替换。
                                        if (!onlyIfAbsent)
                                            //替换掉
                                            e.val = value;
                                        break;
                                    }
                                    Node<K, V> pred = e;
                                    //下一个节点为空
                                    if ((e = e.next) == null) {
                                        //新建节点
                                        pred.next = new Node<K, V>(hash, key,
                                                value, null);
                                        break;
                                    }
                                }
                            }
                            //如果时树节点
                            else if (f instanceof TreeBin) {
                                Node<K, V> p;
                                //桶数量为2
                                binCount = 2;
                                //找到插入的位置,插入节点,平衡插入
                                if ((p = ((TreeBin<K, V>) f).putTreeVal(hash, key,
                                        value)) != null) {
                                    oldVal = p.val;
                                    if (!onlyIfAbsent)
                                        p.val = value;
                                }
                            }
                        }
                    }
                    //如果桶数量不为0
                    if (binCount != 0) {
                        //如果桶数量大于树化阈值
                        if (binCount >= TREEIFY_THRESHOLD)
                            //将链表转为树
                            treeifyBin(tab, i);
                        //如果老的值存在,则返回
                        if (oldVal != null)
                            return oldVal;
                        break;
                    }
                }
            }
            //增加数量
            addCount(1L, binCount);
            return null;
        }

        /**
         * Copies all of the mappings from the specified map to this one.
         * These mappings replace any mappings that this map had for any of the
         * keys currently in the specified map.
         * <p>
         * 将指定映射的所有映射复制到此映射,这些映射替换了当前指定映射中任意键的映射。
         *
         * @param m mappings to be stored in this map
         */
        public void putAll(Map<? extends K, ? extends V> m) {
            //尝试调整表的大小以适应给定的元素数量。
            tryPresize(m.size());
            //迭代插入
            for (Entry<? extends K, ? extends V> e : m.entrySet())
                putVal(e.getKey(), e.getValue(), false);
        }

        /**
         * Removes the key (and its corresponding value) from this map.
         * This method does nothing if the key is not in the map.
         * <p>
         * 从映射中删除键(及其对应值)。如果键不在映射中,则此方法不执行任何操作。
         *
         * @param key the key that needs to be removed 指定移除的键
         * @return the previous value associated with {@code key}, or
         * {@code null} if there was no mapping for {@code key} 如果没有针对{@code key}的映射,则与{@code key}关联的前一个值或{@code null}
         * @throws NullPointerException if the specified key is null 如果指定的键为空
         */
        public V remove(Object key) {
            return replaceNode(key, null, null);
        }

        /**
         * Implementation for the four public remove/replace methods:
         * Replaces node value with v, conditional upon match of cv if
         * non-null.  If resulting value is null, delete.
         * 删除/替换的操作
         */
        final V replaceNode(Object key, V value, Object cv) {
            //发散hash
            int hash = spread(key.hashCode());
            //迭代表
            for (Node<K, V>[] tab = table; ; ) {
                Node<K, V> f;
                int n, i, fh;
                //如果表为空,且键所在节点为空,跳出循环
                if (tab == null || (n = tab.length) == 0 ||
                        (f = tabAt(tab, i = (n - 1) & hash)) == null)
                    break;
                    //如果key所在节点的hash值为MOVED
                else if ((fh = f.hash) == MOVED)
                    //如果还在进行扩容操作就先进行扩容
                    tab = helpTransfer(tab, f);
                else {
                    V oldVal = null;
                    //是否检验
                    boolean validated = false;
                    //锁当前节点
                    synchronized (f) {
                        //确认节点
                        if (tabAt(tab, i) == f) {
                            //节点的hash值大于0
                            if (fh >= 0) {
                                //校验
                                validated = true;
                                for (Node<K, V> e = f, pred = null; ; ) {
                                    K ek;
                                    //找到键位置
                                    if (e.hash == hash &&
                                            ((ek = e.key) == key ||
                                                    (ek != null && key.equals(ek)))) {
                                        //老的值
                                        V ev = e.val;
                                        //删除节点
                                        if (cv == null || cv == ev ||
                                                (ev != null && cv.equals(ev))) {
                                            oldVal = ev;
                                            if (value != null)
                                                e.val = value;
                                            else if (pred != null)
                                                pred.next = e.next;
                                            else
                                                setTabAt(tab, i, e.next);
                                        }
                                        break;
                                    }
                                    pred = e;
                                    if ((e = e.next) == null)
                                        break;
                                }
                            }
                            //是树形节点
                            else if (f instanceof TreeBin) {
                                validated = true;
                                TreeBin<K, V> t = (TreeBin<K, V>) f;
                                TreeNode<K, V> r, p;
                                //找到删除的key
                                if ((r = t.root) != null &&
                                        (p = r.findTreeNode(hash, key, null)) != null) {
                                    V pv = p.val;
                                    if (cv == null || cv == pv ||
                                            (pv != null && cv.equals(pv))) {
                                        oldVal = pv;
                                        if (value != null)
                                            p.val = value;
                                            //删除树节点
                                        else if (t.removeTreeNode(p))
                                            setTabAt(tab, i, untreeify(t.first));
                                    }
                                }
                            }
                        }
                    }
                    //检查
                    if (validated) {
                        if (oldVal != null) {
                            if (value == null)
                                //数量减一
                                addCount(-1L, -1);
                            return oldVal;
                        }
                        break;
                    }
                }
            }
            return null;
        }

        /**
         * Removes all of the mappings from this map.
         * 清空map
         */
        public void clear() {
            long delta = 0L; // negative number of deletions 删除次数为负数
            int i = 0;
            Node<K, V>[] tab = table;
            while (tab != null && i < tab.length) {
                int fh;
                //获取节点
                Node<K, V> f = tabAt(tab, i);
                if (f == null)
                    ++i;
                    //转发节点的哈希
                else if ((fh = f.hash) == MOVED) {
                    //如果还在进行扩容操作就先进行扩容
                    tab = helpTransfer(tab, f);
                    i = 0; // restart
                } else {
                    //锁定当前节点
                    synchronized (f) {
                        //确认节点
                        if (tabAt(tab, i) == f) {
                            //获取节点,包括树节点
                            Node<K, V> p = (fh >= 0 ? f :
                                    (f instanceof TreeBin) ?
                                            ((TreeBin<K, V>) f).first : null);
                            while (p != null) {
                                //数量减一
                                --delta;
                                //下一个节点
                                p = p.next;
                            }
                            //置空
                            setTabAt(tab, i++, null);
                        }
                    }
                }
            }
            if (delta != 0L)
                //计数
                addCount(delta, -1);
        }

        /**
         * Returns the hash code value for this {@link Map}, i.e.,
         * the sum of, for each key-value pair in the map,
         * {@code key.hashCode() ^ value.hashCode()}.
         * <p>
         * 返回这个{@link Map}的哈希码值,即,对于映射中的每个键值对,{@code key.hashCode() ^ value.hashCode()}的和。
         *
         * @return the hash code value for this map
         */
        public int hashCode() {
            int h = 0;
            Node<K, V>[] t;
            if ((t = table) != null) {
                Traverser<K, V> it = new Traverser<K, V>(t, t.length, 0, t.length);
                for (Node<K, V> p; (p = it.advance()) != null; )
                    //取键的Hash值与值的Hash值的异或 的 和
                    h += p.key.hashCode() ^ p.val.hashCode();
            }
            return h;
        }

        /**
         * Compares the specified object with this map for equality.
         * Returns {@code true} if the given object is a map with the same
         * mappings as this map.  This operation may return misleading
         * results if either map is concurrently modified during execution
         * of this method.
         * <p>
         * 重写的equals方法
         *
         * @param o object to be compared for equality with this map
         * @return {@code true} if the specified object is equal to this map
         */
        public boolean equals(Object o) {
            //如果栈中值不相等
            if (o != this) {
                //如果o未实现Map接口,则不相等
                if (!(o instanceof Map))
                    return false;
                Map<?, ?> m = (Map<?, ?>) o;
                Node<K, V>[] t;
                int f = (t = table) == null ? 0 : t.length;
                Traverser<K, V> it = new Traverser<K, V>(t, f, 0, f);
                //迭代,只要有一个值不相等,则返回false
                for (Node<K, V> p; (p = it.advance()) != null; ) {
                    V val = p.val;
                    Object v = m.get(p.key);
                    if (v == null || (v != val && !v.equals(val)))
                        return false;
                }
                //迭代视图
                for (Entry<?, ?> e : m.entrySet()) {
                    Object mk, mv, v;
                    if ((mk = e.getKey()) == null ||
                            (mv = e.getValue()) == null ||
                            (v = get(mk)) == null ||
                            (mv != v && !mv.equals(v)))
                        return false;
                }
            }
            return true;
        }

        /**
         * Stripped-down version of helper class used in previous version,
         * declared for the sake of serialization compatibility
         * <p>
         * 以前版本中使用的helper类的简化版本,为了序列化兼容性而声明
         * 继承自重入锁
         */
        static class Segment<K, V> extends ReentrantLock implements Serializable {
            private static final long serialVersionUID = 2249069246763182397L;
            final float loadFactor;

            Segment(float lf) {
                this.loadFactor = lf;
            }
        }

        // Overrides of JDK8+ Map extension method defaults

        /**
         * Returns the value to which the specified key is mapped, or the
         * given default value if this map contains no mapping for the
         * key.
         * 返回指定键映射到的值,如果此映射不包含键的映射,则返回给定的默认值。
         *
         * @param key          the key whose associated value is to be returned
         * @param defaultValue the value to return if this map contains
         *                     no mapping for the given key
         * @return the mapping for the key, if present; else the default value
         * @throws NullPointerException if the specified key is null
         */
        public V getOrDefault(Object key, V defaultValue) {
            V v;
            return (v = get(key)) == null ? defaultValue : v;
        }

来源:https://www.jianshu.com/p/a75d196731c0

赞(0) 打赏
版权归原创作者所有,任何形式的转载请联系博主:daming_90:Java 技术驿站 » JAVA并发容器源码分析【二】ConcurrentHashMap源码翻译之基础

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏