class Solution {
    public int secondHighest(String s) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);

        for (int i = 0; i < s.length(); i++) {
            if (Character.isDigit(s.charAt(i))) {
                pq.offer(s.charAt(i) - '0');
            }
        }

        if (pq.size() < 2) return -1;
        int val = pq.poll();
        int res = -1;
        // 相同元素出队
        while (!pq.isEmpty() && (res = pq.poll()) == val) {
        }
        return res==val?-1:res;
    }
}

import java.util.HashMap;
import java.util.Map;

class AuthenticationManager {
    int ttl = 0;
    Map<String, Integer> map;

    public AuthenticationManager(int timeToLive) {
        this.ttl = timeToLive;
        map = new HashMap<>();
    }

    public void generate(String tokenId, int currentTime) {
        map.put(tokenId, currentTime);
    }

    public void renew(String tokenId, int currentTime) {
        if (map.containsKey(tokenId) && currentTime - map.get(tokenId) < ttl) {
            map.put(tokenId, currentTime);
        }
    }

    public int countUnexpiredTokens(int currentTime) {
        int res = 0;
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (currentTime - entry.getValue() < ttl) {
                res++;
            }
        }
        return res;
    }
}

/**
 * Your AuthenticationManager object will be instantiated and called as such:
 * AuthenticationManager obj = new AuthenticationManager(timeToLive);
 * obj.generate(tokenId,currentTime);
 * obj.renew(tokenId,currentTime);
 * int param_3 = obj.countUnexpiredTokens(currentTime);
 */

class Solution {
    public int getMaximumConsecutive(int[] coins) {
        int x=0;// 事实上，x记录的是前缀和
        Arrays.sort(coins);
        for(int y:coins){
            // 如果前面的前缀和小于后面的这个元素，那么后面的这个元素不可以通过前面的这些元素计算出来
            if(x+1<y){
                break;
            }
            // 前缀和累计
            x+=y;
        }
        // 返回前缀和+1，因为有0
        return x+1;
    }
}

import java.util.*;

public class Main {

    static Integer arr[] = new Integer[2];

    public static void main(String[] args) {
        for (int i = 0; i < 2; i++) {
            arr[i] = new Integer(i);
        }

        Test1 t1 = new Test1();
        Test2 t2 = new Test2();

        Thread thread1 = new Thread(t1);
        Thread thread2 = new Thread(t2);

        thread1.start();
        thread2.start();
    }


    private static class Test1 implements Runnable {
        @Override
        public void run() {
            Integer i1 = arr[0];
            synchronized (i1) {
                try {
                    System.out.println("----------数组元素0加锁-----------");
                    Thread.sleep(5000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }

    }

    private static class Test2 implements Runnable {

        @Override
        public void run() {
            Integer i2 = arr[1];
            synchronized (i2) {
                try {
                    System.out.println("----------数组元素1加锁-----------");
                    Thread.sleep(5000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }

}

package java.util.concurrent;

import java.io.ObjectStreamField;
import java.io.Serializable;
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
import java.util.AbstractMap;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.Enumeration;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.Spliterator;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.locks.LockSupport;
import java.util.concurrent.locks.ReentrantLock;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.BinaryOperator;
import java.util.function.Consumer;
import java.util.function.DoubleBinaryOperator;
import java.util.function.Function;
import java.util.function.IntBinaryOperator;
import java.util.function.LongBinaryOperator;
import java.util.function.ToDoubleBiFunction;
import java.util.function.ToDoubleFunction;
import java.util.function.ToIntBiFunction;
import java.util.function.ToIntFunction;
import java.util.function.ToLongBiFunction;
import java.util.function.ToLongFunction;
import java.util.stream.Stream;


public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable {
    private static final long serialVersionUID = 7249069246763182397L;


    // 最大容量是2^30
    private static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认初始容量是16
    private static final int DEFAULT_CAPACITY = 16;
    // 最大容量是2^31-1-8
    static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    // 默认并行级别是16
    private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
    // 负载因子16
    private static final float LOAD_FACTOR = 0.75f;

    // 转换成红黑树的阈值是链表长度到8
    static final int TREEIFY_THRESHOLD = 8;
    // 由红黑树转换成链表的阈值是6
    static final int UNTREEIFY_THRESHOLD = 6;
    // 转换成红黑树的数组长度阈值,大于这个值才会转换成树,否则只扩容不转换
    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.
     */
    // 数据转移时的步长（每一次转移的桶的数量）
    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.
     */
    private static int RESIZE_STAMP_BITS = 16;

    /**
     * The maximum number of threads that can help resize.
     * Must fit in 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.
     */
    private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;

    /*
     * Encodings for Node hash fields. See above for explanation.
     */
    // ForwardingNode初始化时会设置这个值
    // 当数据迁移时，会设置这个值
    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

    // 获取CPU的数量
    /** Number of CPUS, to place bounds on some sizings */
    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.
     */
    // 数组每个元素的结构
    static class Node<K,V> implements Map.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; Map.Entry<?,?> e;
            return ((o instanceof Map.Entry) &&
                    (k = (e = (Map.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.
         */
        // 在当前节点所连接的节点中查找Object元素
        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.
     */
    // 通过与高16位相异或使hash值分布的更加均匀
    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.
     */
    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.
     */

    @SuppressWarnings("unchecked")
    static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
        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) {
        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) {
        U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
    }

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

    // map的数组
    transient volatile Node<K,V>[] table;
    // 下一个使用的数组，仅在扩容更新的时候不为空,扩容时会慢慢把数据移动到这个数组.
    private transient volatile Node<K,V>[] nextTable;
    // 在没有发生争用时的元素统计
    private transient volatile long baseCount;

// 一个标志是否扩容的标志位
   private transient volatile int sizeCtl;
   // 扩容索引值,表示已经分配给扩容线程的table数组索引位置,主要用来协调多个线程间迁移任务的并发安全.
   private transient volatile int transferIndex;
   // 自旋锁
   private transient volatile int cellsBusy;

   /**
    * Table of counter cells. When non-null, size is a power of 2.
    */
   private transient volatile CounterCell[] counterCells;

   // map的视图
   private transient KeySetView<K,V> keySet;
   private transient ValuesView<K,V> values;
   private transient EntrySetView<K,V> entrySet;

public ConcurrentHashMap() {
}

public ConcurrentHashMap(int initialCapacity) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException();
    int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
               MAXIMUM_CAPACITY :
               tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
    this.sizeCtl = cap;
}

public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
    this.sizeCtl = DEFAULT_CAPACITY;
    putAll(m);
}

public ConcurrentHashMap(int initialCapacity, float loadFactor) {
    this(initialCapacity, loadFactor, 1);
}

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);
    int cap = (size >= (long)MAXIMUM_CAPACITY) ?
        MAXIMUM_CAPACITY : tableSizeFor((int)size);
    this.sizeCtl = cap;
}

public int size() {
    long n = sumCount();
    return ((n < 0L) ? 0 :
            (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
            (int)n);
}
public boolean isEmpty() {
    return sumCount() <= 0L; // ignore transient negative values
}

// 判断是键是否存在
public boolean containsKey(Object key) {
    return get(key) != 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;
            if ((v = p.val) == value || (v != null && value.equals(v)))
                return true;
        }
    }
    return false;
}

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; )
            h += p.key.hashCode() ^ p.val.hashCode();
    }
    return h;
}

public String toString() {
    Node<K,V>[] t;
    int f = (t = table) == null ? 0 : t.length;
    Traverser<K,V> it = new Traverser<K,V>(t, f, 0, f);
    StringBuilder sb = new StringBuilder();
    sb.append('{');
    Node<K,V> p;
    if ((p = it.advance()) != null) {
        for (;;) {
            K k = p.key;
            V v = p.val;
            sb.append(k == this ? "(this Map)" : k);
            sb.append('=');
            sb.append(v == this ? "(this Map)" : v);
            if ((p = it.advance()) == null)
                break;
            sb.append(',').append(' ');
        }
    }
    return sb.append('}').toString();
}

public boolean equals(Object o) {
    if (o != this) {
        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);
        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 (Map.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;
}
public void putAll(Map<? extends K, ? extends V> m) {
    tryPresize(m.size());
    for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
        putVal(e.getKey(), e.getValue(), false);
}

public V remove(Object key) {
    return replaceNode(key, null, null);
}

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    // 计算当前传入key的哈希值
    int h = spread(key.hashCode());
    // 如果表不为空,表的长度大于0,key的hash处不为空,那么继续检查哈希值是否相同
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        // 如果哈希值相同
        if ((eh = e.hash) == h) {
            // 并且键值相同,那么返回要get的元素
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        // 如果eh小于0，那么说明元素正在迁移》》》》》》》》》》》》》》》》当元素正在迁移的时候，设置第一个元素的哈希值为-1
        else if (eh < 0)
            // 那么从这个桶的第一个元素开始查找在该链上的所有元素
            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;
}

public V put(K key, V value) {
    return putVal(key, value, false);
}

/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    // 过滤无效值,键值不允许为空?????
    // 这里表明键和值都不允许为空
    if (key == null || value == null) throw new NullPointerException();
    // 计算key的hash值
    int hash = spread(key.hashCode());
    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();
        // 如果表中key计算出的hash对应的位置为空,那么这是第一个,直接使用CAS添加Node<key,value>
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                // 如果添加成功结束自旋
                break;                   // no lock when adding to empty bin
        }
        // 如果正在resize()做迁移,那么需要helpTransfer来做
        // 如果当前的表在转移元素,那么桶中的第一个元素的哈希值为-1也就是MOVED常量
        else if ((fh = f.hash) == MOVED)
            // 这个时候本线程先去帮助迁移表格
            tab = helpTransfer(tab, f);
        else {
            // 如果迁移完毕后
            V oldVal = null;
            // 对当前的桶加锁,其中的锁对象是当前桶内的第一个元素对象，也就是仅仅对当前的对象加了锁
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    // 重新检查是不是有线程在扩容,fh>0说明没有线程在扩容
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            // 如果已经存在这个元素,那么就替换
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                // 如果当前的元素就是要put的那个key,那么就替换当前的值
                                oldVal = e.val;
                                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;
                            }
                        }
                    }
                    // 如果f节点是红黑树的节点
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        // 使用红黑树的插入逻辑
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            // 如果当前的桶中的节点的数量大于要转换成树的阈值,那么将其转换成红黑树
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}



final V replaceNode(Object key, V value, Object cv) {
    // 计算传入的键的哈希值
    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;
        // 如果桶的第一个元素的哈希值是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) {
                    // 没有在迁移元素
                    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;
                        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.
 */
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);
}

public KeySetView<K,V> keySet() {
    KeySetView<K,V> ks;
    return (ks = keySet) != null ? ks : (keySet = new KeySetView<K,V>(this, null));
}

public Collection<V> values() {
    ValuesView<K,V> vs;
    return (vs = values) != null ? vs : (values = new ValuesView<K,V>(this));
}


public Set<Map.Entry<K,V>> entrySet() {
    EntrySetView<K,V> es;
    return (es = entrySet) != null ? es : (entrySet = new EntrySetView<K,V>(this));
}

// 这个内部类目前只是在序列化的时候使用
static class Segment<K,V> extends ReentrantLock implements Serializable {
    private static final long serialVersionUID = 2249069246763182397L;
    final float loadFactor;
    Segment(float lf) { this.loadFactor = lf; }
}

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    // For serialization compatibility
    // Emulate segment calculation from previous version of this class
    int sshift = 0;
    int ssize = 1;
    while (ssize < DEFAULT_CONCURRENCY_LEVEL) {
        ++sshift;
        ssize <<= 1;
    }
    int segmentShift = 32 - sshift;
    int segmentMask = ssize - 1;
    @SuppressWarnings("unchecked")
    Segment<K,V>[] segments = (Segment<K,V>[])
        new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
    for (int i = 0; i < segments.length; ++i)
        segments[i] = new Segment<K,V>(LOAD_FACTOR);
    s.putFields().put("segments", segments);
    s.putFields().put("segmentShift", segmentShift);
    s.putFields().put("segmentMask", segmentMask);
    s.writeFields();

    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; ) {
            s.writeObject(p.key);
            s.writeObject(p.val);
        }
    }
    s.writeObject(null);
    s.writeObject(null);
    segments = null; // throw away
}

private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    /*
     * To improve performance in typical cases, we create nodes
     * while reading, then place in table once size is known.
     * However, we must also validate uniqueness and deal with
     * overpopulated bins while doing so, which requires
     * specialized versions of putVal mechanics.
     */
    sizeCtl = -1; // force exclusion for table construction
    s.defaultReadObject();
    long size = 0L;
    Node<K,V> p = null;
    for (;;) {
        @SuppressWarnings("unchecked")
        K k = (K) s.readObject();
        @SuppressWarnings("unchecked")
        V v = (V) s.readObject();
        if (k != null && v != null) {
            p = new Node<K,V>(spread(k.hashCode()), k, v, p);
            ++size;
        }
        else
            break;
    }
    if (size == 0L)
        sizeCtl = 0;
    else {
        int n;
        if (size >= (long)(MAXIMUM_CAPACITY >>> 1))
            n = MAXIMUM_CAPACITY;
        else {
            int sz = (int)size;
            n = tableSizeFor(sz + (sz >>> 1) + 1);
        }
        @SuppressWarnings("unchecked")
        Node<K,V>[] tab = (Node<K,V>[])new Node<?,?>[n];
        int mask = n - 1;
        long added = 0L;
        while (p != null) {
            boolean insertAtFront;
            Node<K,V> next = p.next, first;
            int h = p.hash, j = h & mask;
            if ((first = tabAt(tab, j)) == null)
                insertAtFront = true;
            else {
                K k = p.key;
                if (first.hash < 0) {
                    TreeBin<K,V> t = (TreeBin<K,V>)first;
                    if (t.putTreeVal(h, k, p.val) == null)
                        ++added;
                    insertAtFront = false;
                }
                else {
                    int binCount = 0;
                    insertAtFront = true;
                    Node<K,V> q; K qk;
                    for (q = first; q != null; q = q.next) {
                        if (q.hash == h &&
                            ((qk = q.key) == k ||
                             (qk != null && k.equals(qk)))) {
                            insertAtFront = false;
                            break;
                        }
                        ++binCount;
                    }
                    if (insertAtFront && binCount >= TREEIFY_THRESHOLD) {
                        insertAtFront = false;
                        ++added;
                        p.next = first;
                        TreeNode<K,V> hd = null, tl = null;
                        for (q = p; q != null; q = q.next) {
                            TreeNode<K,V> t = new TreeNode<K,V>
                                (q.hash, q.key, q.val, null, null);
                            if ((t.prev = tl) == null)
                                hd = t;
                            else
                                tl.next = t;
                            tl = t;
                        }
                        setTabAt(tab, j, new TreeBin<K,V>(hd));
                    }
                }
            }
            if (insertAtFront) {
                ++added;
                p.next = first;
                setTabAt(tab, j, p);
            }
            p = next;
        }
        table = tab;
        sizeCtl = n - (n >>> 2);
        baseCount = added;
    }
}

// ConcurrentMap methods

public V putIfAbsent(K key, V value) {
    return putVal(key, value, true);
}

public boolean remove(Object key, Object value) {
    if (key == null)
        throw new NullPointerException();
    return value != null && replaceNode(key, null, value) != null;
}

public boolean replace(K key, V oldValue, V newValue) {
    if (key == null || oldValue == null || newValue == null)
        throw new NullPointerException();
    return replaceNode(key, newValue, oldValue) != null;
}

public V replace(K key, V value) {
    if (key == null || value == null)
        throw new NullPointerException();
    return replaceNode(key, value, null);
}

// Overrides of JDK8+ Map extension method defaults

public V getOrDefault(Object key, V defaultValue) {
    V v;
    return (v = get(key)) == null ? defaultValue : v;
}

public void forEach(BiConsumer<? super K, ? super V> action) {
    if (action == 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; ) {
            action.accept(p.key, p.val);
        }
    }
}

public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
    if (function == 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 oldValue = p.val;
            for (K key = p.key;;) {
                V newValue = function.apply(key, oldValue);
                if (newValue == null)
                    throw new NullPointerException();
                if (replaceNode(key, newValue, oldValue) != null ||
                    (oldValue = get(key)) == null)
                    break;
            }
        }
    }
}

/**
 * If the specified key is not already associated with a value,
 * attempts to compute its value using the given mapping function
 * and enters it into this map unless {@code null}.  The entire
 * method invocation is performed atomically, so the function is
 * applied at most once per key.  Some attempted update operations
 * on this map by other threads may be blocked while computation
 * is in progress, so the computation should be short and simple,
 * and must not attempt to update any other mappings of this map.
 *
 * @param key key with which the specified value is to be associated
 * @param mappingFunction the function to compute a value
 * @return the current (existing or computed) value associated with
 *         the specified key, or null if the computed value is null
 * @throws NullPointerException if the specified key or mappingFunction
 *         is null
 * @throws IllegalStateException if the computation detectably
 *         attempts a recursive update to this map that would
 *         otherwise never complete
 * @throws RuntimeException or Error if the mappingFunction does so,
 *         in which case the mapping is left unestablished
 */
public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
    if (key == null || mappingFunction == null)
        throw new NullPointerException();
    int h = spread(key.hashCode());
    V val = null;
    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) & h)) == null) {
            Node<K,V> r = new ReservationNode<K,V>();
            synchronized (r) {
                if (casTabAt(tab, i, null, r)) {
                    binCount = 1;
                    Node<K,V> node = null;
                    try {
                        if ((val = mappingFunction.apply(key)) != null)
                            node = new Node<K,V>(h, key, val, null);
                    } finally {
                        setTabAt(tab, i, node);
                    }
                }
            }
            if (binCount != 0)
                break;
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            boolean added = false;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek; V ev;
                            if (e.hash == h &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                val = e.val;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                if ((val = mappingFunction.apply(key)) != null) {
                                    added = true;
                                    pred.next = new Node<K,V>(h, key, val, null);
                                }
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        binCount = 2;
                        TreeBin<K,V> t = (TreeBin<K,V>)f;
                        TreeNode<K,V> r, p;
                        if ((r = t.root) != null &&
                            (p = r.findTreeNode(h, key, null)) != null)
                            val = p.val;
                        else if ((val = mappingFunction.apply(key)) != null) {
                            added = true;
                            t.putTreeVal(h, key, val);
                        }
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (!added)
                    return val;
                break;
            }
        }
    }
    if (val != null)
        addCount(1L, binCount);
    return val;
}

/**
 * If the value for the specified key is present, attempts to
 * compute a new mapping given the key and its current mapped
 * value.  The entire method invocation is performed atomically.
 * Some attempted update operations on this map by other threads
 * may be blocked while computation is in progress, so the
 * computation should be short and simple, and must not attempt to
 * update any other mappings of this map.
 *
 * @param key key with which a value may be associated
 * @param remappingFunction the function to compute a value
 * @return the new value associated with the specified key, or null if none
 * @throws NullPointerException if the specified key or remappingFunction
 *         is null
 * @throws IllegalStateException if the computation detectably
 *         attempts a recursive update to this map that would
 *         otherwise never complete
 * @throws RuntimeException or Error if the remappingFunction does so,
 *         in which case the mapping is unchanged
 */
public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
    if (key == null || remappingFunction == null)
        throw new NullPointerException();
    int h = spread(key.hashCode());
    V val = null;
    int delta = 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) & h)) == null)
            break;
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f, pred = null;; ++binCount) {
                            K ek;
                            if (e.hash == h &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                val = remappingFunction.apply(key, e.val);
                                if (val != null)
                                    e.val = val;
                                else {
                                    delta = -1;
                                    Node<K,V> en = e.next;
                                    if (pred != null)
                                        pred.next = en;
                                    else
                                        setTabAt(tab, i, en);
                                }
                                break;
                            }
                            pred = e;
                            if ((e = e.next) == null)
                                break;
                        }
                    }
                    else if (f instanceof TreeBin) {
                        binCount = 2;
                        TreeBin<K,V> t = (TreeBin<K,V>)f;
                        TreeNode<K,V> r, p;
                        if ((r = t.root) != null &&
                            (p = r.findTreeNode(h, key, null)) != null) {
                            val = remappingFunction.apply(key, p.val);
                            if (val != null)
                                p.val = val;
                            else {
                                delta = -1;
                                if (t.removeTreeNode(p))
                                    setTabAt(tab, i, untreeify(t.first));
                            }
                        }
                    }
                }
            }
            if (binCount != 0)
                break;
        }
    }
    if (delta != 0)
        addCount((long)delta, binCount);
    return val;
}

/**
 * Attempts to compute a mapping for the specified key and its
 * current mapped value (or {@code null} if there is no current
 * mapping). The entire method invocation is performed atomically.
 * Some attempted update operations on this map by other threads
 * may be blocked while computation is in progress, so the
 * computation should be short and simple, and must not attempt to
 * update any other mappings of this Map.
 *
 * @param key key with which the specified value is to be associated
 * @param remappingFunction the function to compute a value
 * @return the new value associated with the specified key, or null if none
 * @throws NullPointerException if the specified key or remappingFunction
 *         is null
 * @throws IllegalStateException if the computation detectably
 *         attempts a recursive update to this map that would
 *         otherwise never complete
 * @throws RuntimeException or Error if the remappingFunction does so,
 *         in which case the mapping is unchanged
 */
public V compute(K key,
                 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
    if (key == null || remappingFunction == null)
        throw new NullPointerException();
    int h = spread(key.hashCode());
    V val = null;
    int delta = 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) & h)) == null) {
            Node<K,V> r = new ReservationNode<K,V>();
            synchronized (r) {
                if (casTabAt(tab, i, null, r)) {
                    binCount = 1;
                    Node<K,V> node = null;
                    try {
                        if ((val = remappingFunction.apply(key, null)) != null) {
                            delta = 1;
                            node = new Node<K,V>(h, key, val, null);
                        }
                    } finally {
                        setTabAt(tab, i, node);
                    }
                }
            }
            if (binCount != 0)
                break;
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f, pred = null;; ++binCount) {
                            K ek;
                            if (e.hash == h &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                val = remappingFunction.apply(key, e.val);
                                if (val != null)
                                    e.val = val;
                                else {
                                    delta = -1;
                                    Node<K,V> en = e.next;
                                    if (pred != null)
                                        pred.next = en;
                                    else
                                        setTabAt(tab, i, en);
                                }
                                break;
                            }
                            pred = e;
                            if ((e = e.next) == null) {
                                val = remappingFunction.apply(key, null);
                                if (val != null) {
                                    delta = 1;
                                    pred.next =
                                        new Node<K,V>(h, key, val, null);
                                }
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        binCount = 1;
                        TreeBin<K,V> t = (TreeBin<K,V>)f;
                        TreeNode<K,V> r, p;
                        if ((r = t.root) != null)
                            p = r.findTreeNode(h, key, null);
                        else
                            p = null;
                        V pv = (p == null) ? null : p.val;
                        val = remappingFunction.apply(key, pv);
                        if (val != null) {
                            if (p != null)
                                p.val = val;
                            else {
                                delta = 1;
                                t.putTreeVal(h, key, val);
                            }
                        }
                        else if (p != null) {
                            delta = -1;
                            if (t.removeTreeNode(p))
                                setTabAt(tab, i, untreeify(t.first));
                        }
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                break;
            }
        }
    }
    if (delta != 0)
        addCount((long)delta, binCount);
    return val;
}

/**
 * If the specified key is not already associated with a
 * (non-null) value, associates it with the given value.
 * Otherwise, replaces the value with the results of the given
 * remapping function, or removes if {@code null}. The entire
 * method invocation is performed atomically.  Some attempted
 * update operations on this map by other threads may be blocked
 * while computation is in progress, so the computation should be
 * short and simple, and must not attempt to update any other
 * mappings of this Map.
 *
 * @param key key with which the specified value is to be associated
 * @param value the value to use if absent
 * @param remappingFunction the function to recompute a value if present
 * @return the new value associated with the specified key, or null if none
 * @throws NullPointerException if the specified key or the
 *         remappingFunction is null
 * @throws RuntimeException or Error if the remappingFunction does so,
 *         in which case the mapping is unchanged
 */
public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
    if (key == null || value == null || remappingFunction == null)
        throw new NullPointerException();
    int h = spread(key.hashCode());
    V val = null;
    int delta = 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) & h)) == null) {
            if (casTabAt(tab, i, null, new Node<K,V>(h, key, value, null))) {
                delta = 1;
                val = value;
                break;
            }
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f, pred = null;; ++binCount) {
                            K ek;
                            if (e.hash == h &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                val = remappingFunction.apply(e.val, value);
                                if (val != null)
                                    e.val = val;
                                else {
                                    delta = -1;
                                    Node<K,V> en = e.next;
                                    if (pred != null)
                                        pred.next = en;
                                    else
                                        setTabAt(tab, i, en);
                                }
                                break;
                            }
                            pred = e;
                            if ((e = e.next) == null) {
                                delta = 1;
                                val = value;
                                pred.next =
                                    new Node<K,V>(h, key, val, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        binCount = 2;
                        TreeBin<K,V> t = (TreeBin<K,V>)f;
                        TreeNode<K,V> r = t.root;
                        TreeNode<K,V> p = (r == null) ? null :
                            r.findTreeNode(h, key, null);
                        val = (p == null) ? value :
                            remappingFunction.apply(p.val, value);
                        if (val != null) {
                            if (p != null)
                                p.val = val;
                            else {
                                delta = 1;
                                t.putTreeVal(h, key, val);
                            }
                        }
                        else if (p != null) {
                            delta = -1;
                            if (t.removeTreeNode(p))
                                setTabAt(tab, i, untreeify(t.first));
                        }
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                break;
            }
        }
    }
    if (delta != 0)
        addCount((long)delta, binCount);
    return val;
}

// Hashtable legacy methods

/**
 * Legacy method testing if some key maps into the specified value
 * in this table.  This method is identical in functionality to
 * {@link #containsValue(Object)}, and exists solely to ensure
 * full compatibility with class {@link java.util.Hashtable},
 * which supported this method prior to introduction of the
 * Java Collections framework.
 *
 * @param  value a value to search for
 * @return {@code true} if and only if some key maps to the
 *         {@code value} argument in this table as
 *         determined by the {@code equals} method;
 *         {@code false} otherwise
 * @throws NullPointerException if the specified value is null
 */
public boolean contains(Object value) {
    return containsValue(value);
}

/**
 * Returns an enumeration of the keys in this table.
 *
 * @return an enumeration of the keys in this table
 * @see #keySet()
 */
public Enumeration<K> keys() {
    Node<K,V>[] t;
    int f = (t = table) == null ? 0 : t.length;
    return new KeyIterator<K,V>(t, f, 0, f, this);
}

/**
 * Returns an enumeration of the values in this table.
 *
 * @return an enumeration of the values in this table
 * @see #values()
 */
public Enumeration<V> elements() {
    Node<K,V>[] t;
    int f = (t = table) == null ? 0 : t.length;
    return new ValueIterator<K,V>(t, f, 0, f, this);
}

// ConcurrentHashMap-only methods

/**
 * Returns the number of mappings. This method should be used
 * instead of {@link #size} because a ConcurrentHashMap may
 * contain more mappings than can be represented as an int. The
 * value returned is an estimate; the actual count may differ if
 * there are concurrent insertions or removals.
 *
 * @return the number of mappings
 * @since 1.8
 */
public long mappingCount() {
    long n = sumCount();
    return (n < 0L) ? 0L : n; // ignore transient negative values
}

/**
 * Creates a new {@link Set} backed by a ConcurrentHashMap
 * from the given type to {@code Boolean.TRUE}.
 *
 * @param <K> the element type of the returned set
 * @return the new set
 * @since 1.8
 */
public static <K> KeySetView<K,Boolean> newKeySet() {
    return new KeySetView<K,Boolean>
        (new ConcurrentHashMap<K,Boolean>(), Boolean.TRUE);
}

/**
 * Creates a new {@link Set} backed by a ConcurrentHashMap
 * from the given type to {@code Boolean.TRUE}.
 *
 * @param initialCapacity The implementation performs internal
 * sizing to accommodate this many elements.
 * @param <K> the element type of the returned set
 * @return the new set
 * @throws IllegalArgumentException if the initial capacity of
 * elements is negative
 * @since 1.8
 */
public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
    return new KeySetView<K,Boolean>
        (new ConcurrentHashMap<K,Boolean>(initialCapacity), Boolean.TRUE);
}

/**
 * Returns a {@link Set} view of the keys in this map, using the
 * given common mapped value for any additions (i.e., {@link
 * Collection#add} and {@link Collection#addAll(Collection)}).
 * This is of course only appropriate if it is acceptable to use
 * the same value for all additions from this view.
 *
 * @param mappedValue the mapped value to use for any additions
 * @return the set view
 * @throws NullPointerException if the mappedValue is null
 */
public KeySetView<K,V> keySet(V mappedValue) {
    if (mappedValue == null)
        throw new NullPointerException();
    return new KeySetView<K,V>(this, mappedValue);
}

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