java HashMap学习

简单讲解下HashMap的原理：HashMap基于Hash算法，我们通过put(key,value)存储，get(key)来获取。当传入key时，HashMap会根据key.hashCode()计算出hash值，根据hash值将value保存在bucket里。当计算出的hash值相同时怎么办呢，我们称之为Hash冲突，HashMap的做法是用链表和红黑树存储相同hash值的value。当Hash冲突的个数比较少时，使用链表，否则使用红黑树。

数据结构

属性分析

/**
 * 初始化容量16
    * The default initial capacity - MUST be a power of two.
    */
   static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * 最大容量
    * The maximum capacity, used if a higher value is implicitly specified
    * by either of the constructors with arguments.
    * MUST be a power of two <= 1<<30.
    */
   static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 负载因子	
 * 
    * The load factor used when none specified in constructor.
    */
   static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 当桶上结点大于这个值时链表会转成红黑树
 * 
    * The bin count threshold for using a tree rather than list for a
    * bin.  Bins are converted to trees when adding an element to a
    * bin with at least this many nodes. The value must be greater
    * than 2 and should be at least 8 to mesh with assumptions in
    * tree removal about conversion back to plain bins upon
    * shrinkage.
    */
   static final int TREEIFY_THRESHOLD = 8;

/**
 * 当桶（bucket）上值小于这个值时转成链表
 * 
    * The bin count threshold for untreeifying a (split) bin during a
    * resize operation. Should be less than TREEIFY_THRESHOLD, and at
    * most 6 to mesh with shrinkage detection under removal.
    */
   static final int UNTREEIFY_THRESHOLD = 6;

/**
 * 桶转换成红黑树对应table最小的值（table是前面的数组）
 * 
    * The smallest table capacity for which bins may be treeified.
    * (Otherwise the table is resized if too many nodes in a bin.)
    * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
    * between resizing and treeification thresholds.
    */
   static final int MIN_TREEIFY_CAPACITY = 64;

/**
 * 前面的数组存的总是2的倍数
    * The table, initialized on first use, and resized as
    * necessary. When allocated, length is always a power of two.
    * (We also tolerate length zero in some operations to allow
    * bootstrapping mechanics that are currently not needed.)
    */
   transient Node<K,V>[] table;

 /**
 * 这个是用来存储数据的
    * Holds cached entrySet(). Note that AbstractMap fields are used
    * for keySet() and values().
    */
   transient Set<Map.Entry<K,V>> entrySet;

/**
 * 当容量*负载因子超过临界值时，会进行重置
    * The next size value at which to resize (capacity * load factor).
    *
    * @serial
    */
   int threshold;


/**
 * 得到当前容量最接近的2的倍数
    * Returns a power of two size for the given target capacity.
    */
   static final int tableSizeFor(int cap) {
       int n = cap - 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;
   }

重要内部类Node

/**
    * Basic hash bin node, used for most entries.  (See below for
    * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
    */
   static class Node<K,V> implements Map.Entry<K,V> {
       final int hash;
       final K key;
       V value;
       Node<K,V> next;

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

       public final K getKey()        { return key; }
       public final V getValue()      { return value; }
       public final String toString() { return key + "=" + value; }

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

       public final V setValue(V newValue) {
           V oldValue = value;
           value = newValue;
           return oldValue;
       }

       public final boolean equals(Object o) {
           if (o == this)
               return true;
           if (o instanceof Map.Entry) {
               Map.Entry<?,?> e = (Map.Entry<?,?>)o;
               if (Objects.equals(key, e.getKey()) &&
                   Objects.equals(value, e.getValue()))
                   return true;
           }
           return false;
       }
   }

重要内部类TreeNode

 static final class TreeNode<K,V> extends LinkedHashMap.Entry<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) {
           super(hash, key, val, next);
       }

       /**
        * Returns root of tree containing this node.
        */
       final TreeNode<K,V> root() {
           for (TreeNode<K,V> r = this, p;;) {
               if ((p = r.parent) == null)
                   return r;
               r = p;
           }
       }

       /**
        * Ensures that the given root is the first node of its bin.
        */
       static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
           int n;
           if (root != null && tab != null && (n = tab.length) > 0) {
               int index = (n - 1) & root.hash;
               TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
               if (root != first) {
                   Node<K,V> rn;
                   tab[index] = root;
                   TreeNode<K,V> rp = root.prev;
                   if ((rn = root.next) != null)
                       ((TreeNode<K,V>)rn).prev = rp;
                   if (rp != null)
                       rp.next = rn;
                   if (first != null)
                       first.prev = root;
                   root.next = first;
                   root.prev = null;
               }
               assert checkInvariants(root);
           }
       }

       /**
        * Finds the node starting at root p with the given hash and key.
        * The kc argument caches comparableClassFor(key) upon first use
        * comparing keys.
        */
       final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
           TreeNode<K,V> p = this;
           do {
               int ph, dir; K pk;
               TreeNode<K,V> pl = p.left, pr = p.right, q;
               if ((ph = p.hash) > h)
                   p = pl;
               else if (ph < h)
                   p = pr;
               else if ((pk = p.key) == k || (k != 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.find(h, k, kc)) != null)
                   return q;
               else
                   p = pl;
           } while (p != null);
           return null;
       }

       /**
        * Calls find for root node.
        */
       final TreeNode<K,V> getTreeNode(int h, Object k) {
           return ((parent != null) ? root() : this).find(h, k, null);
       }

       /**
        * Tie-breaking utility for ordering insertions when equal
        * hashCodes and non-comparable. We don't require a total
        * order, just a consistent insertion rule to maintain
        * equivalence across rebalancings. Tie-breaking further than
        * necessary simplifies testing a bit.
        */
       static int tieBreakOrder(Object a, Object b) {
           int d;
           if (a == null || b == null ||
               (d = a.getClass().getName().
                compareTo(b.getClass().getName())) == 0)
               d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
                    -1 : 1);
           return d;
       }

       /**
        * Forms tree of the nodes linked from this node.
        * @return root of tree
        */
       final void treeify(Node<K,V>[] tab) {
           TreeNode<K,V> root = null;
           for (TreeNode<K,V> x = this, next; x != null; x = next) {
               next = (TreeNode<K,V>)x.next;
               x.left = x.right = null;
               if (root == null) {
                   x.parent = null;
                   x.red = false;
                   root = x;
               }
               else {
                   K k = x.key;
                   int h = x.hash;
                   Class<?> kc = null;
                   for (TreeNode<K,V> p = root;;) {
                       int dir, ph;
                       K pk = p.key;
                       if ((ph = p.hash) > h)
                           dir = -1;
                       else if (ph < h)
                           dir = 1;
                       else if ((kc == null &&
                                 (kc = comparableClassFor(k)) == null) ||
                                (dir = compareComparables(kc, k, pk)) == 0)
                           dir = tieBreakOrder(k, pk);

                       TreeNode<K,V> xp = p;
                       if ((p = (dir <= 0) ? p.left : p.right) == null) {
                           x.parent = xp;
                           if (dir <= 0)
                               xp.left = x;
                           else
                               xp.right = x;
                           root = balanceInsertion(root, x);
                           break;
                       }
                   }
               }
           }
           moveRootToFront(tab, root);
       }

       /**
        * Returns a list of non-TreeNodes replacing those linked from
        * this node.
        */
       final Node<K,V> untreeify(HashMap<K,V> map) {
           Node<K,V> hd = null, tl = null;
           for (Node<K,V> q = this; q != null; q = q.next) {
               Node<K,V> p = map.replacementNode(q, null);
               if (tl == null)
                   hd = p;
               else
                   tl.next = p;
               tl = p;
           }
           return hd;
       }

       /**
        * Tree version of putVal.
        */
       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;
               }
           }
       }

       /**
        * Removes the given node, that must be present before this call.
        * This is messier than typical red-black deletion code because we
        * cannot swap the contents of an interior node with a leaf
        * successor that is pinned by "next" pointers that are accessible
        * independently during traversal. So instead we swap the tree
        * linkages. If the current tree appears to have too few nodes,
        * the bin is converted back to a plain bin. (The test triggers
        * somewhere between 2 and 6 nodes, depending on tree structure).
        */
       final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                                 boolean movable) {
           int n;
           if (tab == null || (n = tab.length) == 0)
               return;
           int index = (n - 1) & hash;
           TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
           TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
           if (pred == null)
               tab[index] = first = succ;
           else
               pred.next = succ;
           if (succ != null)
               succ.prev = pred;
           if (first == null)
               return;
           if (root.parent != null)
               root = root.root();
           if (root == null || root.right == null ||
               (rl = root.left) == null || rl.left == null) {
               tab[index] = first.untreeify(map);  // too small
               return;
           }
           TreeNode<K,V> p = this, pl = left, pr = right, replacement;
           if (pl != null && pr != null) {
               TreeNode<K,V> s = pr, sl;
               while ((sl = s.left) != null) // find successor
                   s = sl;
               boolean c = s.red; s.red = p.red; p.red = c; // swap colors
               TreeNode<K,V> sr = s.right;
               TreeNode<K,V> pp = p.parent;
               if (s == pr) { // p was s's direct parent
                   p.parent = s;
                   s.right = p;
               }
               else {
                   TreeNode<K,V> sp = s.parent;
                   if ((p.parent = sp) != null) {
                       if (s == sp.left)
                           sp.left = p;
                       else
                           sp.right = p;
                   }
                   if ((s.right = pr) != null)
                       pr.parent = s;
               }
               p.left = null;
               if ((p.right = sr) != null)
                   sr.parent = p;
               if ((s.left = pl) != null)
                   pl.parent = s;
               if ((s.parent = pp) == null)
                   root = s;
               else if (p == pp.left)
                   pp.left = s;
               else
                   pp.right = s;
               if (sr != null)
                   replacement = sr;
               else
                   replacement = p;
           }
           else if (pl != null)
               replacement = pl;
           else if (pr != null)
               replacement = pr;
           else
               replacement = p;
           if (replacement != p) {
               TreeNode<K,V> pp = replacement.parent = p.parent;
               if (pp == null)
                   root = replacement;
               else if (p == pp.left)
                   pp.left = replacement;
               else
                   pp.right = replacement;
               p.left = p.right = p.parent = null;
           }

           TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);

           if (replacement == p) {  // detach
               TreeNode<K,V> pp = p.parent;
               p.parent = null;
               if (pp != null) {
                   if (p == pp.left)
                       pp.left = null;
                   else if (p == pp.right)
                       pp.right = null;
               }
           }
           if (movable)
               moveRootToFront(tab, r);
       }

       /**
        * Splits nodes in a tree bin into lower and upper tree bins,
        * or untreeifies if now too small. Called only from resize;
        * see above discussion about split bits and indices.
        *
        * @param map the map
        * @param tab the table for recording bin heads
        * @param index the index of the table being split
        * @param bit the bit of hash to split on
        */
       final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
           TreeNode<K,V> b = this;
           // Relink into lo and hi lists, preserving order
           TreeNode<K,V> loHead = null, loTail = null;
           TreeNode<K,V> hiHead = null, hiTail = null;
           int lc = 0, hc = 0;
           for (TreeNode<K,V> e = b, next; e != null; e = next) {
               next = (TreeNode<K,V>)e.next;
               e.next = null;
               if ((e.hash & bit) == 0) {
                   if ((e.prev = loTail) == null)
                       loHead = e;
                   else
                       loTail.next = e;
                   loTail = e;
                   ++lc;
               }
               else {
                   if ((e.prev = hiTail) == null)
                       hiHead = e;
                   else
                       hiTail.next = e;
                   hiTail = e;
                   ++hc;
               }
           }

           if (loHead != null) {
               if (lc <= UNTREEIFY_THRESHOLD)
                   tab[index] = loHead.untreeify(map);
               else {
                   tab[index] = loHead;
                   if (hiHead != null) // (else is already treeified)
                       loHead.treeify(tab);
               }
           }
           if (hiHead != null) {
               if (hc <= UNTREEIFY_THRESHOLD)
                   tab[index + bit] = hiHead.untreeify(map);
               else {
                   tab[index + bit] = hiHead;
                   if (loHead != null)
                       hiHead.treeify(tab);
               }
           }
       }

       /* ------------------------------------------------------------ */
       // Red-black tree methods, all adapted from CLR

       static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                             TreeNode<K,V> p) {
           TreeNode<K,V> r, pp, rl;
           if (p != null && (r = p.right) != null) {
               if ((rl = p.right = r.left) != null)
                   rl.parent = p;
               if ((pp = r.parent = p.parent) == null)
                   (root = r).red = false;
               else if (pp.left == p)
                   pp.left = r;
               else
                   pp.right = r;
               r.left = p;
               p.parent = r;
           }
           return root;
       }

       static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                              TreeNode<K,V> p) {
           TreeNode<K,V> l, pp, lr;
           if (p != null && (l = p.left) != null) {
               if ((lr = p.left = l.right) != null)
                   lr.parent = p;
               if ((pp = l.parent = p.parent) == null)
                   (root = l).red = false;
               else if (pp.right == p)
                   pp.right = l;
               else
                   pp.left = l;
               l.right = p;
               p.parent = l;
           }
           return root;
       }

       static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                   TreeNode<K,V> x) {
           x.red = true;
           for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
               if ((xp = x.parent) == null) {
                   x.red = false;
                   return x;
               }
               else if (!xp.red || (xpp = xp.parent) == null)
                   return root;
               if (xp == (xppl = xpp.left)) {
                   if ((xppr = xpp.right) != null && xppr.red) {
                       xppr.red = false;
                       xp.red = false;
                       xpp.red = true;
                       x = xpp;
                   }
                   else {
                       if (x == xp.right) {
                           root = rotateLeft(root, x = xp);
                           xpp = (xp = x.parent) == null ? null : xp.parent;
                       }
                       if (xp != null) {
                           xp.red = false;
                           if (xpp != null) {
                               xpp.red = true;
                               root = rotateRight(root, xpp);
                           }
                       }
                   }
               }
               else {
                   if (xppl != null && xppl.red) {
                       xppl.red = false;
                       xp.red = false;
                       xpp.red = true;
                       x = xpp;
                   }
                   else {
                       if (x == xp.left) {
                           root = rotateRight(root, x = xp);
                           xpp = (xp = x.parent) == null ? null : xp.parent;
                       }
                       if (xp != null) {
                           xp.red = false;
                           if (xpp != null) {
                               xpp.red = true;
                               root = rotateLeft(root, xpp);
                           }
                       }
                   }
               }
           }
       }

       static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
                                                  TreeNode<K,V> x) {
           for (TreeNode<K,V> xp, xpl, xpr;;)  {
               if (x == null || x == root)
                   return root;
               else if ((xp = x.parent) == null) {
                   x.red = false;
                   return x;
               }
               else if (x.red) {
                   x.red = false;
                   return root;
               }
               else if ((xpl = xp.left) == x) {
                   if ((xpr = xp.right) != null && xpr.red) {
                       xpr.red = false;
                       xp.red = true;
                       root = rotateLeft(root, xp);
                       xpr = (xp = x.parent) == null ? null : xp.right;
                   }
                   if (xpr == null)
                       x = xp;
                   else {
                       TreeNode<K,V> sl = xpr.left, sr = xpr.right;
                       if ((sr == null || !sr.red) &&
                           (sl == null || !sl.red)) {
                           xpr.red = true;
                           x = xp;
                       }
                       else {
                           if (sr == null || !sr.red) {
                               if (sl != null)
                                   sl.red = false;
                               xpr.red = true;
                               root = rotateRight(root, xpr);
                               xpr = (xp = x.parent) == null ?
                                   null : xp.right;
                           }
                           if (xpr != null) {
                               xpr.red = (xp == null) ? false : xp.red;
                               if ((sr = xpr.right) != null)
                                   sr.red = false;
                           }
                           if (xp != null) {
                               xp.red = false;
                               root = rotateLeft(root, xp);
                           }
                           x = root;
                       }
                   }
               }
               else { // symmetric
                   if (xpl != null && xpl.red) {
                       xpl.red = false;
                       xp.red = true;
                       root = rotateRight(root, xp);
                       xpl = (xp = x.parent) == null ? null : xp.left;
                   }
                   if (xpl == null)
                       x = xp;
                   else {
                       TreeNode<K,V> sl = xpl.left, sr = xpl.right;
                       if ((sl == null || !sl.red) &&
                           (sr == null || !sr.red)) {
                           xpl.red = true;
                           x = xp;
                       }
                       else {
                           if (sl == null || !sl.red) {
                               if (sr != null)
                                   sr.red = false;
                               xpl.red = true;
                               root = rotateLeft(root, xpl);
                               xpl = (xp = x.parent) == null ?
                                   null : xp.left;
                           }
                           if (xpl != null) {
                               xpl.red = (xp == null) ? false : xp.red;
                               if ((sl = xpl.left) != null)
                                   sl.red = false;
                           }
                           if (xp != null) {
                               xp.red = false;
                               root = rotateRight(root, xp);
                           }
                           x = root;
                       }
                   }
               }
           }
       }

       /**
        * Recursive invariant check
        */
       static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
           TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
               tb = t.prev, tn = (TreeNode<K,V>)t.next;
           if (tb != null && tb.next != t)
               return false;
           if (tn != null && tn.prev != t)
               return false;
           if (tp != null && t != tp.left && t != tp.right)
               return false;
           if (tl != null && (tl.parent != t || tl.hash > t.hash))
               return false;
           if (tr != null && (tr.parent != t || tr.hash < t.hash))
               return false;
           if (t.red && tl != null && tl.red && tr != null && tr.red)
               return false;
           if (tl != null && !checkInvariants(tl))
               return false;
           if (tr != null && !checkInvariants(tr))
               return false;
           return true;
       }
   
}

基本操作

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
       Node<K,V>[] tab; 
	Node<K,V> p; 
	int n, i;

	判断前面的数组如果为0就进行扩容
       if ((tab = table) == null || (n = tab.length) == 0)
           n = (tab = resize()).length;

	//确定当前元素放在哪个数组中
       if ((p = tab[i = (n - 1) & hash]) == null)
           tab[i] = newNode(hash, key, value, null);
       else {
           Node<K,V> e; 
		K k;
           if (p.hash == hash &&
               ((k = p.key) == key || (key != null && key.equals(k))))
               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;
               }
           }
           if (e != null) { // existing mapping for key
               V oldValue = e.value;
               if (!onlyIfAbsent || oldValue == null)
                   e.value = value;
               afterNodeAccess(e);
               return oldValue;
           }
       }
       ++modCount;
       if (++size > threshold)
           resize();
       afterNodeInsertion(evict);
       return null;
   }