concurrenthashmap和hashtable的区别(concurrenthashmap使用)

    // 最大容量
    private static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认初始化容量
    private static final int DEFAULT_CAPACITY = 16;
    // 负载因子
    private static final float LOAD_FACTOR = 0.75f;
    // 树化阈值
    static final int TREEIFY_THRESHOLD = 8;
    // 树化容量，元素为链表且长度达到8：table元素超过64则树化，低于64直接扩容
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 红黑树扩容是，高低位解除树化阈值
    static final int UNTREEIFY_THRESHOLD = 6;

    // 初始化 sizeCtl既是容量又是扩容阈值，等于initialCapacity的最近的2的次方数翻倍
    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;
    }

    private final void addCount(long x, int check) {
        CounterCell[] as; long b, s;
        if ((as = counterCells) != null ||
            !U.compareAndSwapLong(this, baseCOUNT, b = baseCount, s = b + x)) {
            CounterCell a; long v; int m;
            boolean uncontended = true;
            // cells为null，或者对应的index的cell为null，直接对baseCount累加
            // cells不为null，获取cell为null则初始化cells并初始化cell
            // cells不为null，cell不为null,该位置进行累加，如果累加时发生竞争，则进入fullAddCount
            if (as == null || (m = as.length - 1) < 0 ||
                (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
                !(uncontended =
                  U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
                fullAddCount(x, uncontended);
                return;
            }
            if (check <= 1)
                return;
            // baseCount和cells里面的值进行累加
            s = sumCount();
        }
        if (check >= 0) {
            Node[] tab, nt; int n, sc;
            // 如果添加元素后，元素的个数大于等于扩容阈值，则进行扩容
            while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
                   (n = tab.length) < MAXIMUM_CAPACITY) {
                int rs = resizeStamp(n);
                if (sc < 0) {
                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                        transferIndex <= 0)
                        break;
                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                        // 哈希表的扩容
                        transfer(tab, nt);
                }
                else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                             (rs << RESIZE_STAMP_SHIFT) + 2))
                    // 哈希表的扩容
                    transfer(tab, null);
                s = sumCount();
            }
        }
    }

   private final void transfer(Node[] tab, Node[] nextTab) {
        // 分段扩容，元素个数小于16，则单线程扩容
        int n = tab.length, stride;
        if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
            stride = MIN_TRANSFER_STRIDE; // subdivide range
        if (nextTab == null) {            // initiating
            try {
                @SuppressWarnings("unchecked")
                Node[] nt = (Node[])new Node[n << 1];
                nextTab = nt;
            } catch (Throwable ex) {      // try to cope with OOME
                sizeCtl = Integer.MAX_VALUE;
                return;
            }
            nextTable = nextTab;
            transferIndex = n;
        }
        int nextn = nextTab.length;
        // 比如某个元素扩容完成，设置成forward节点，因为其它元素可能处于扩容中
        ForwardingNode fwd = new ForwardingNode(nextTab);
        boolean advance = true;
        boolean finishing = false; // to ensure sweep before committing nextTab
        for (int i = 0, bound = 0;;) {
            Node f; int fh;
            // 每次计算扩容的元素下表 --i，i初始值为n - 1(transferIndex - 1)
            // 比如分段，每段处理2个元素 元素位 0 1 2 3， 则 i=3， --1，计算第二段然后 i=1， --i
            // 这里分段处理，依然是单线程循环处理
            while (advance) {
                int nextIndex, nextBound;
                if (--i >= bound || finishing)
                    advance = false;
                else if ((nextIndex = transferIndex) <= 0) {
                    i = -1;
                    advance = false;
                }
                else if (U.compareAndSwapInt
                         (this, TRANSFERINDEX, nextIndex,
                          nextBound = (nextIndex > stride ?
                                       nextIndex - stride : 0))) {
                    bound = nextBound;
                    i = nextIndex - 1;
                    advance = false;
                }
            }
            if (i < 0 || i >= n || i + n >= nextn) {
                int sc;
                if (finishing) {
                    nextTable = null;
                    table = nextTab;
                    sizeCtl = (n << 1) - (n >>> 1);
                    return;
                }
                if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                    if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                        return;
                    finishing = advance = true;
                    i = n; // recheck before commit
                }
            }
            // 1、元素为null，直接设置forword节点，接着扩容后面的元素
            else if ((f = tabAt(tab, i)) == null)
                advance = casTabAt(tab, i, null, fwd);
            // 2、如果处于扩容中则跳过
            else if ((fh = f.hash) == MOVED)
                advance = true; // already processed
            else {
                // 2、扩容，链表扩容则分成高低位两条链表并赋值给哈希表指定位置
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        Node ln, hn;
                        if (fh >= 0) {
                            int runBit = fh & n;
                            Node lastRun = f;
                            for (Node p = f.next; p != null; p = p.next) {
                                int b = p.hash & n;
                                if (b != runBit) {
                                    runBit = b;
                                    lastRun = p;
                                }
                            }
                            if (runBit == 0) {
                                ln = lastRun;
                                hn = null;
                            }
                            else {
                                hn = lastRun;
                                ln = null;
                            }
                            for (Node p = f; p != lastRun; p = p.next) {
                                int ph = p.hash; K pk = p.key; V pv = p.val;
                                if ((ph & n) == 0)
                                    ln = new Node(ph, pk, pv, ln);
                                else
                                    hn = new Node(ph, pk, pv, hn);
                            }
                            setTabAt(nextTab, i, ln);
                            setTabAt(nextTab, i + n, hn);
                            setTabAt(tab, i, fwd);
                            advance = true;
                        }
                        // 3、如果是红黑树扩容，则转换成高低位两条链的同时
                        // 需要计算高低链元素数目，小于非树化阈值6则变成普通节点
                        else if (f instanceof TreeBin) {
                            TreeBin t = (TreeBin)f;
                            TreeNode lo = null, loTail = null;
                            TreeNode hi = null, hiTail = null;
                            int lc = 0, hc = 0;
                            for (Node e = t.first; e != null; e = e.next) {
                                int h = e.hash;
                                TreeNode p = new TreeNode
                                    (h, e.key, e.val, null, null);
                                if ((h & n) == 0) {
                                    if ((p.prev = loTail) == null)
                                        lo = p;
                                    else
                                        loTail.next = p;
                                    loTail = p;
                                    ++lc;
                                }
                                else {
                                    if ((p.prev = hiTail) == null)
                                        hi = p;
                                    else
                                        hiTail.next = p;
                                    hiTail = p;
                                    ++hc;
                                }
                            }
                            ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
                                (hc != 0) ? new TreeBin(lo) : t;
                            hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                                (lc != 0) ? new TreeBin(hi) : t;
                            setTabAt(nextTab, i, ln);
                            setTabAt(nextTab, i + n, hn);
                            setTabAt(tab, i, fwd);
                            advance = true;
                        }
                    }
                }
            }
        }
    }

    private final void fullAddCount(long x, boolean wasUncontended) {
        int h;
        if ((h = ThreadLocalRandom.getProbe()) == 0) {
            ThreadLocalRandom.localInit();      // force initialization
            h = ThreadLocalRandom.getProbe();
            wasUncontended = true;
        }
        boolean collide = false;                // True if last slot nonempty
        for (;;) {
            CounterCell[] as; CounterCell a; int n; long v;
            // 2、cells不为null的时候，这里分两种情况
            // 2.1 cell为null，进行初始化并赋值
            // 2.2 cell不为null，前面发生竞争，上面代码获取了新的哈希值
            // 2.2.1 新的哈希值，还是这个index的cell，那么cell已经不为null了，如果不满足counterCells != as || n >= NCPU则进行扩容
            // 2.2.2 如果新哈希算出来新的index的cell，cell初始化或者重新因竞争导致扩容
            if ((as = counterCells) != null && (n = as.length) > 0) {
                if ((a = as[(n - 1) & h]) == null) {
                    if (cellsBusy == 0) {            // Try to attach new Cell
                        CounterCell r = new CounterCell(x); // Optimistic create
                        if (cellsBusy == 0 &&
                            U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
                            boolean created = false;
                            try {               // Recheck under lock
                                CounterCell[] rs; int m, j;
                                if ((rs = counterCells) != null &&
                                    (m = rs.length) > 0 &&
                                    rs[j = (m - 1) & h] == null) {
                                    rs[j] = r;
                                    created = true;
                                }
                            } finally {
                                cellsBusy = 0;
                            }
                            if (created)
                                break;
                            continue;           // Slot is now non-empty
                        }
                    }
                    collide = false;
                }
                else if (!wasUncontended)       // CAS already known to fail
                    wasUncontended = true;      // Continue after rehash
                else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
                    break;
                // 大于等于cpu总的线程数，则扩容
                else if (counterCells != as || n >= NCPU)
                    collide = false;            // At max size or stale
                else if (!collide)
                    collide = true;
                else if (cellsBusy == 0 &&
                         U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
                    try {
                        if (counterCells == as) {// Expand table unless stale
                            CounterCell[] rs = new CounterCell[n << 1];
                            for (int i = 0; i < n; ++i)
                                rs[i] = as[i];
                            counterCells = rs;
                        }
                    } finally {
                        cellsBusy = 0;
                    }
                    collide = false;
                    continue;                   // Retry with expanded table
                }
                // 发生竞争重新计算哈希值，里面用的threadLocal，因此计算和获取的新的哈希值在线程本地局部变量里面
                h = ThreadLocalRandom.advanceProbe(h);
            }
            // 1、如果cells为null，则进行初始化cells
            else if (cellsBusy == 0 && counterCells == as &&
                     U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
                boolean init = false;
                try {    
                    // double check，防止重复初始化
                    if (counterCells == as) {
                        // 初始化Cell
                        CounterCell[] rs = new CounterCell[2];
                        rs[h & 1] = new CounterCell(x);
                        counterCells = rs;
                        init = true;
                    }
                } finally {
                    cellsBusy = 0;
                }
                if (init)
                    break;
            }
            else if (U.compareAndSwapLong(this, baseCOUNT, v = baseCount, v + x))
                break;                          // Fall back on using base
        }
    }

    final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        int hash = spread(key.hashCode());
        int binCount = 0;
        for (Node[] tab = table;;) {
            Node f; int n, i, fh;
            // 1、胃初始化，则出初始化table，进行下一次循环
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            // 2、元素位置为Null，则直接赋值、若cas并发赋值成功则结束循环
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null,
                             new Node(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node e = f;; ++binCount) {
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        else if (f instanceof TreeBin) {
                            Node p;
                            binCount = 2;
                            if ((p = ((TreeBin)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;
                }
            }
        }
        // 并发cell base 加，同LongAdder
        addCount(1L, binCount);
        return null;
    }

    private final Node[] initTable() {
        Node[] tab; int sc;
        while ((tab = table) == null || tab.length == 0) {
            if ((sc = sizeCtl) < 0)
                // 多线程并发让出cpu时间片
                Thread.yield(); // lost initialization race; just spin
            // sizeCtl = -1 表示哈希表初始化状态，大于0表示初始化完毕
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    // double check，return前防止其它线程重复初始化
                    if ((tab = table) == null || tab.length == 0) {
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                        @SuppressWarnings("unchecked")
                        Node[] nt = (Node[])new Node[n];
                        table = tab = nt;
                        // 0.75n 容量和扩容阈值为默认值或者指定值的0.75倍
                        sc = n - (n >>> 2);
                    }
                } finally {
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
    }

看HashMap、ConcurrentHashMap源码，基本的数据结构功底还是要有的。看之前最好自己实现个红黑树。个人认为红黑树相比较平衡二叉树最大的优势在于，树高度矫正的时候不用再次计算节点的高度，可以通过树的红黑特性直接旋转。

红黑树JAVA版本，凭感觉写了并未测试过。

package _01_basic_structure._05tree;

public class _04_RBTree {
    public static void main(String[] args) {

    }

    class RBTree> {
        private RBTreeNode root;
        private static final boolean RED = true;
        private static final boolean BLACK = false;

        public RBTreeNode getRoot() {
            return root;
        }

        // 查找树中key的节点
        public RBTreeNode searchNode(K key) {
            RBTreeNode tmp = root;
            while (tmp != null) {
                int compareTo = key.compareTo((K) tmp.key);
                if (compareTo < 0) {
                    tmp = tmp.left;
                } else if (compareTo > 0) {
                    tmp = tmp.right;
                } else {
                    break;
                }
            }
            return tmp;
        }

        public void insert(K key) {
            RBTreeNode node = new RBTreeNode(key);
            node.setColor(RED);
            insert(node);
        }

        private void insert(RBTreeNode node) {
            RBTreeNode parent = null;
            RBTreeNode tmp = root;
            // 查找父节点
            while (tmp != null) {
                parent = tmp;
                int compareTo = node.key.compareTo(tmp.key);
                if (compareTo < 0) {
                    tmp = tmp.left;
                } else if (compareTo > 0) {
                    tmp = tmp.right;
                } else {
                    // 如果找到同key的节点，把value进行更换
                    tmp.setValue(node.value);
                    return;
                }
            }

            // 找到父节点后，插入node节点
            node.parent = parent;
            if (parent != null) {
                int compareTo = node.key.compareTo(parent.key);
                if (compareTo < 0) {
                    parent.left = node;
                } else {
                    parent.right = node;
                }
            } else {
                this.root = node;
                node.setColor(BLACK);
                return;
            }

            // 红黑树进行校正
            insertFixUp(node);
        }

        // 红黑树平衡修复
        public void insertFixUp(RBTreeNode node) {
            while (parentOf(node) != null && isRed(parentOf(node))) {
                RBTreeNode parent = parentOf(node);
                RBTreeNode gparent = parentOf(parent);
                if (gparent != null) {
                    if (parent == gparent.left) {
                        RBTreeNode uncle = gparent.right;
                        if (isRed(uncle)) {
                            setBlack(uncle);
                            setBlack(parent);
                            setRed(gparent);
                            node = gparent;
                            continue;
                        }

                        if (parent.right == node) {
                            // 左旋转, 旋转时node和parent交换了位置
                            leftRotate(parent);
                            RBTreeNode tmp = parent;
                            parent = node;
                            node = tmp;
                        }

                        setBlack(parent);
                        setRed(gparent);
                        rightRotate(gparent);
                    } else {
                        RBTreeNode uncle = gparent.left;
                        if (uncle != null && isRed(uncle)) {
                            setBlack(parent);
                            setBlack(uncle);
                            setRed(gparent);
                            node = gparent;
                            continue;
                        }

                        if (parent.left == node) {
                            rightRotate(parent);
                            RBTreeNode tmp = parent;
                            parent = node;
                            node = parent;
                        }

                        setBlack(parent);
                        setRed(gparent);
                        leftRotate(gparent);
                    }
                }
            }
        }

        
        public void leftRotate(RBTreeNode node) {
            RBTreeNode right = node.right;
            node.right = right.left;
            if (right.left != null) {
                right.left.parent = node;
            }

            right.left = node;
            right.parent = node.parent;
            if (node.parent == null) {
                root = right;
            } else {
                if (node.parent.left == node) {
                    node.parent.left = right;
                } else {
                    node.parent.right = right;
                }
            }
            node.parent = right;
        }

        
        public void rightRotate(RBTreeNode node) {
            RBTreeNode left = node.left;
            node.left = left.right;
            if (left.right != null) {
                left.right.parent = node;
            }

            left.right = node;
            left.parent = node.parent;
            if (node.parent != null) {
                if (node.parent.left == node) {
                    node.parent.left = left;
                } else {
                    node.parent.right = left;
                }
            } else {
                this.root = left;
            }
            node.parent = left;
        }

        public RBTreeNode parentOf(RBTreeNode node) {
            return node == null ? null: node.parent;
        }

        public boolean isRed(RBTreeNode node) {
            return node.color == RED? true: false;
        }

        public boolean isBlack(RBTreeNode node) {
            return node.color == BLACK? true: false;
        }

        public void setRed(RBTreeNode node) {
            if (node != null) node.setColor(RED);
        }

        public void setBlack(RBTreeNode node) {
            if (node != null) node.setColor(BLACK);
        }

        class RBTreeNode, V> {
            private RBTreeNode left;
            private RBTreeNode right;
            private RBTreeNode parent;
            private K key;
            private V value;
            private boolean color;

            public RBTreeNode() {
            }

            public RBTreeNode(K key) {
                this.key = key;
            }

            public RBTreeNode getLeft() {
                return left;
            }

            public void setLeft(RBTreeNode left) {
                this.left = left;
            }

            public RBTreeNode getRight() {
                return right;
            }

            public void setRight(RBTreeNode right) {
                this.right = right;
            }

            public RBTreeNode getParent() {
                return parent;
            }

            public void setParent(RBTreeNode parent) {
                this.parent = parent;
            }

            public K getKey() {
                return key;
            }

            public void setKey(K key) {
                this.key = key;
            }

            public V getValue() {
                return value;
            }

            public void setValue(V value) {
                this.value = value;
            }

            public boolean isColor() {
                return color;
            }

            public void setColor(boolean color) {
                this.color = color;
            }

            @Override
            public String toString() {
                return "RBTreeNode{" +
                        "key=" + key +
                        ", value=" + value +
                        '}';
            }
        }
    }
}