HashMap：如何存取一个元素

hashMap的存储结构？

数组+链表（红黑树）
数组：Node<K,V>[] table  
链表（红黑树）：Node是个链表,当链表长度达到阀值的时候会转换成红黑树

如何存储一个元素

1.如何确定存储一个元素的时候所在位置？

1.确定数组位置

//(数组的长度-1)&key的hash值
(n - 1) & hash

2.确定在链表的位置
新添加的元素一般都是放在链表的末尾（未转换成红黑树的前提）， 如果链表的长度 >TREEIFY_THRESHOLD - 1 ， 则会把链表转换成红黑树

          // p是元素所在数组位置的链表的第一个值
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                //如果p的hash值和key的hash值相等并且p的key等于要存入的key
                e = p;
            else if (p instanceof TreeNode)
                // 如果要存入的元素是红黑树的节点，则存入红黑树
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                   // 将要存入的元素放到链表的末尾
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //将链表转换成红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))  //已经存入
                        break;
                    p = e;
                }
            }
     

2.如何将链表转换为红黑树

    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            //如果table为null或者数组的容量<转换为树的上线阀值
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            //e为要转换元素所在链表的第一个元素
            TreeNode<K,V> hd = null, tl = null;
           //循环将每个链表节点转换成树节点
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

2.1 如何将链表节点转换成树节点？

TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
        return new TreeNode<>(p.hash, p.key, p.value, next);
    }

3.红黑树如何插入数据

     final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                       int h, K k, V v) {
            Class<?> kc = null;
            boolean searched = false;
            TreeNode<K,V> root = (parent != null) ? root() : this;
            for (TreeNode<K,V> p = root;;) {
                int dir, ph; K pk;
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    return p;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0) {
                    if (!searched) {
                        TreeNode<K,V> q, ch;
                        searched = true;
                        if (((ch = p.left) != null &&
                             (q = ch.find(h, k, kc)) != null) ||
                            ((ch = p.right) != null &&
                             (q = ch.find(h, k, kc)) != null))
                            return q;
                    }
                    dir = tieBreakOrder(k, pk);
                }

                TreeNode<K,V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    Node<K,V> xpn = xp.next;
                    TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    xp.next = x;
                    x.parent = x.prev = xp;
                    if (xpn != null)
                        ((TreeNode<K,V>)xpn).prev = x;
                    moveRootToFront(tab, balanceInsertion(root, x));
                    return null;
                }
            }
        }

如何读取一个元素

   final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // tab是map的数组， first是要查找元素所在链表的第一个元素，e是要查找的元素，n是数组的长度
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            //根据(n - 1) & hash来计算要查找元素所在链表
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                //如果第一个元素的key的hash值和要查找的key的hash值相等，第一个元素就是要找的元素
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    //如果first是树节点，则通过红黑树查找
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                //遍历链表 找到该元素
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }