1.8的hashMap底层采用数组、链表、红黑树来实现的。

红黑树定义：

  • 每个结点是红或是黑的
  • 根节点是黑的
  • 每个叶结点是黑的
  • 如果一个结点是红的，则它的两个儿子都是黑的
  • 对每个结点，从该结点到其子孙节点的所有路径上包含相同数目的黑结点

哈希算法

哈希算法（也叫散列），就是把任意长度值(Key)通过散列算法变换成固定长度的key（地址）通过这个地址进行访问的数据结构它通过把关键码值映射到表中一个。位置来访问记录，以加快查找的速度。

为什么HashMap在1.7用数组+链表，在1.8后用数组+链表+红黑树？

因为链表过长了查询效率非常低，所以需要用红黑树

  1.     //链表长度大于8，链表转红黑树
  2.     static final int TREEIFY_THRESHOLD = 8;
  3.     //红黑树退化成链表的阀值是6
  4.     static final int UNTREEIFY_THRESHOLD = 6;
  5.     //树化的最小容量，也就是hashMap的容量大于64，而且链表长度大于8，才会去树化
  6.     static final int MIN_TREEIFY_CAPACITY = 64;

PUT方法

  1. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  2.                    boolean evict) {
  3.         Node<K,V>[] tab; Node<K,V> p; int n, i;
  4.         //table为空，去初始数组，默认长度是16
  5.         if ((tab = table) == null || (n = tab.length) == 0)
  6.             n = (tab = resize()).length;
  7.         //计算的索引i位置为null，直接插入
  8.         if ((p = tab[i = (n - 1) & hash]) == null)
  9.             tab[i] = newNode(hash, key, value, null);
  10.         else {
  11.             Node<K,V> e; K k;
  12.             //hash一致，而且key相同，把value替换
  13.             if (p.hash == hash &&
  14.                 ((k = p.key) == key || (key != null && key.equals(k))))
  15.                 e = p;
  16.             else if (p instanceof TreeNode)//判断tab是否为树，直接在红黑树中插入
  17.                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  18.             else {
  19.                 for (int binCount = 0; ; ++binCount) {
  20.                     if ((e = p.next) == null) {
  21.                         //这里才是插入将键值对
  22.                         p.next = newNode(hash, key, value, null);
  23.                         //大于等于TREEIFY_THRESHOLD - 1，转红黑树
  24.                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  25.                             treeifyBin(tab, hash);
  26.                         break;
  27.                     }
  28.                     if (e.hash == hash &&
  29.                         ((k = e.key) == key || (key != null && key.equals(k))))
  30.                         break;
  31.                     p = e;
  32.                 }
  33.             }
  34.             if (e != null) { // existing mapping for key
  35.                 V oldValue = e.value;
  36.                 if (!onlyIfAbsent || oldValue == null)
  37.                     e.value = value;
  38.                 afterNodeAccess(e);
  39.                 return oldValue;
  40.             }
  41.         }
  42.         ++modCount;
  43.         if (++size > threshold)
  44.             resize();//扩容
  45.         afterNodeInsertion(evict);
  46.         return null;
  47.     }

红黑树的插入

  1. static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
  2.                                                     TreeNode<K,V> x) {
  3.            //新节点默认为红色
  4.             x.red = true;
  5.             //xp表示x的父结点，xpp表示x的祖父结点（父结点的父节点）
  6.             //xppl表示xpp的左孩子结点，xppr表示xpp的右孩子结点
  7.             for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
  8.                 // 如果x没有父结点，则表示x是第一个结点，自动为根节点，根节点为黑色
  9.                 if ((xp = x.parent) == null) {
  10.                     x.red = false;
  11.                     return x;
  12.                 }
  13.                 //如果父结点不是红色，就是黑色，表可以直接插入
  14.                 //或者祖父节点为null，表示现在是第2层，也可以直接插入
  15.                 else if (!xp.red || (xpp = xp.parent) == null)
  16.                     return root;
  18.                 // 进入到这里，表示x的父节点为红色
  19.                 // 如果x的父节点是祖父结点的左孩子
  20.                 if (xp == (xppl = xpp.left)) {
  21.                     //祖父结点的右孩子，也就是xp的叔叔节点(xp邻居节点)不为空，且为红色
  22.                     //也就是x的夫节点和叔叔节点都是红色
  23.                     //父节点和叔叔节点都要变成黑色，而且祖父变成红色
  24.                     if ((xppr = xpp.right) != null && xppr.red) {
  25.                         xppr.red = false;
  26.                         xp.red = false;
  27.                         xpp.red = true;
  28.                         x = xpp;
  29.                     }
  30.                     else {// 如果叔叔节点为空，或者为黑色
  31.                         if (x == xp.right) {// 如果x节点为xp的右孩子
  32.                             //把xp进行左旋，产生了新的root节点
  33.                             root = rotateLeft(root, x = xp);
  34.                             xpp = (xp = x.parent) == null ? null : xp.parent;
  35.                         }
  36.                         // 如果x本来是左孩子，或者已经经过了上面的左旋之后，进行变色加右旋
  37.                         if (xp != null) {
  38.                             xp.red = false;
  39.                             if (xpp != null) {
  40.                                 xpp.red = true;
  41.                                 root = rotateRight(root, xpp);
  42.                             }
  43.                         }
  44.                     }
  45.                 }
  46.                 else {// 如果x的父节点是祖父结点的右孩子
  47.                     if (xppl != null && xppl.red) {
  48.                         xppl.red = false;
  49.                         xp.red = false;
  50.                         xpp.red = true;
  51.                         x = xpp;
  52.                     }
  53.                     else {
  54.                         if (x == xp.left) {
  55.                             //把xp进行右旋
  56.                             root = rotateRight(root, x = xp);
  57.                             xpp = (xp = x.parent) == null ? null : xp.parent;
  58.                         }
  59.                         if (xp != null) {
  60.                             xp.red = false;
  61.                             if (xpp != null) {
  62.                                 xpp.red = true;
  63.                                 root = rotateLeft(root, xpp);
  64.                             }
  65.                         }
  66.                     }
  67.                 }
  68.             }
  69.         }