ConcurrentHashMap内部类 Node、TreeNode、ForwardingNode

4_分解内部类 Node、TreeNode、ForwardingNode

Node

    static class Node<K,V> implements Map.Entry<K,V> {
        //这个hash的K的hash经过一次扰动运算得出来的
        final int hash;
        final K key; //线程安全不能修改
        volatile V val;  //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.
         * 链表情况下用不到，当前桶位变成 treebin  fwd节点会用到
         */
        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;
        }
    }
 

TreeNode

    /**
     * Nodes for use in TreeBins
     */
    static final class TreeNode<K,V> extends Node<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;

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

        Node<K,V> find(int h, Object k) {
            return findTreeNode(h, k, null);
        }

        /**
         * Returns the TreeNode (or null if not found) for the given key
         * starting at given root.
         */
        final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
            if (k != null) {
                TreeNode<K,V> p = this;
                do  {
                    int ph, dir; K pk; TreeNode<K,V> q;
                    TreeNode<K,V> pl = p.left, pr = p.right;
                    if ((ph = p.hash) > h)
                        p = pl;
                    else if (ph < h)
                        p = pr;
                    else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
                        return p;
                    else if (pl == null)
                        p = pr;
                    else if (pr == null)
                        p = pl;
                    else if ((kc != null ||
                              (kc = comparableClassFor(k)) != null) &&
                             (dir = compareComparables(kc, k, pk)) != 0)
                        p = (dir < 0) ? pl : pr;
                    else if ((q = pr.findTreeNode(h, k, kc)) != null)
                        return q;
                    else
                        p = pl;
                } while (p != null);
            }
            return null;
        }
    }

ForWaidingNode

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

    /**
     * A node inserted at head of bins during transfer operations.
     */
    static final class ForwardingNode<K,V> extends Node<K,V> {
        //拿到fwd节点 代表现在再扩容数据正在迁移 写线程：需要参与并发扩容  读线程：调用find方法到新表继续查询
        final Node<K,V>[] nextTable;
        //hash固定
        ForwardingNode(Node<K,V>[] tab) {
            super(MOVED, null, null, null);
            this.nextTable = tab;
        }

        Node<K,V> find(int h, Object k) {
            // loop to avoid arbitrarily deep recursion on forwarding nodes
            //tab 一定不为空
            Node<K,V>[] tab = nextTable;
            outer: for (;;) {
                //n 表示为扩容而创建的 新表的长度
                //e 表示在扩容而创建新表使用 寻址算法 得到的 桶位头结点
                Node<K,V> e; int n;

                //条件一：永远不成立
                //条件二：永远不成立
                //条件三：永远不成立
                //条件四：在新扩容表中 重新定位 hash 对应的头结点
                //true -> 1.在oldTable中 对应的桶位在迁移之前就是null
                //        2.扩容完成后，有其它写线程，将此桶位设置为了null
                if (k == null || tab == null || (n = tab.length) == 0 ||
                    (e = tabAt(tab, (n - 1) & h)) == null)
                    return null;

                //前置条件：扩容后的表 对应hash的桶位一定不是null，e为此桶位的头结点
                //e可能为哪些node类型？
                //1.node 类型
                //2.TreeBin 类型
                //3.FWD 类型

                for (;;) {
                    //eh 新扩容后表指定桶位的当前节点的hash
                    //ek 新扩容后表指定桶位的当前节点的key
                    int eh; K ek;
                    //条件成立：说明新扩容 后的表，当前命中桶位中的数据，即为 查询想要数据。
                    if ((eh = e.hash) == h &&
                        ((ek = e.key) == k || (ek != null && k.equals(ek))))
                        return e;

                    //eh<0
                    //hash值为负值表示正在扩容，这个时候查的是ForwardingNode的find方法来定位到nextTable来
                   //eh=-1，说明该节点是一个ForwardingNode，正在迁移，此时调用ForwardingNode的find方法去nextTable里找。
                   //eh=-2，说明该节点是一个TreeBin，此时调用TreeBin的find方法遍历红黑树，由于红黑树有可能正在旋转变色，所以find里会有读写锁。
                   
                    if (eh < 0) {
                        if (e instanceof ForwardingNode) {
                            tab = ((ForwardingNode<K,V>)e).nextTable;
                            continue outer;
                        }
                        else
                            //说明此桶位 为 TreeBin 节点，使用TreeBin.find 查找红黑树中相应节点。
                            return e.find(h, k);
                    }

                    //前置条件：当前桶位头结点 并没有命中查询，说明此桶位是 链表
                    //1.将当前元素 指向链表的下一个元素
                    //2.判断当前元素的下一个位置 是否为空
                    //   true->说明迭代到链表末尾，未找到对应的数据，返回Null
                    if ((e = e.next) == null)
                        return null;
                }
            }
        }
    }