hashMap源码解析

　　问题
　　此次主要分析1.8的版本， 并对1.8之前的结构做对比 hashMap结构 hashMap put的过程 hashMap 扩容的方式 hashMap的并发问题 1.8版本以及1.7版本的差异 hashMap的实现原理
　　链表转成红黑树
　　HashMap是一张哈希表（即数组），表中的每个元素都是键值对（Map.Entry类）。 当hash碰撞时。使用单向链表存储，新元素放在队尾 当单个链表大于8个时，转为红黑树进行存储，当链表长度小于6时，红黑树会重新变回链表 当链表数组的容量超过初始容量的0.75时，再散列将链表数组扩大2倍，把每一个链表分成奇偶两个子链表分别挂在新链表数组的散列位置，这样就减少了每个链表的长度，增加查找效率 HashMap数据结构
　　node结构 // Node是单向链表，它实现了Map.Entry接口     static class Node implements Map.Entry {         final int hash;         final K key;         V value;         Node next;          Node(int hash, K key, V value, Node next) {             this.hash = hash;             this.key = key;             this.value = value;             this.next = next;         }         // 略     }
　　红黑树结构 static final class TreeNode extends LinkedHashMap.Entry {         TreeNode parent;  // red-black tree links         TreeNode left;         TreeNode right;         TreeNode prev;    // needed to unlink next upon deletion         boolean red;         TreeNode(int hash, K key, V val, Node next) {             super(hash, key, val, next);         }         // 略 什么是红黑树
　　是一种平衡二叉树 节点是红色或者黑色 根节点是黑色 每个叶子的节点都是黑色的空节点 每个红色节点的两个子节点都是黑色的 从任意节点到其每个叶子的所有路径都包含相同的黑色节点
　　通过左旋转或右旋转满足以上规则，保证深度相同 读写过程写入过程public V put(K key, V value) {           return putVal(hash(key), key, value, false, true);       }        /**       * Implements Map.put and related methods       *       * @param hash hash for key       * @param key the key       * @param value the value to put       * @param onlyIfAbsent if true, don＂t change existing value       * @param evict if false, the table is in creation mode.       * @return previous value, or null if none       */   final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                      boolean evict) {           Node[] tab;        Node p;        int n, i;           if ((tab = table) == null || (n = tab.length) == 0)               n = (tab = resize()).length;       /*如果table的在（n-1）&hash的值是空，就新建一个节点插入在该位置*/           if ((p = tab[i = (n - 1) & hash]) == null)               tab[i] = newNode(hash, key, value, null);       /*表示有冲突,开始处理冲突*/           else {               Node e;            K k;       /*检查第一个Node，p是不是要找的值*/               if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))                   e = p;               else if (p instanceof TreeNode)                   e = ((TreeNode)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);                  //如果冲突的节点数已经达到8个，看是否需要改变冲突节点的存储结构，　　　　　　　　　　　　　   　　　　　　　　　　　　//treeifyBin首先判断当前hashMap的长度，如果不足64，只进行                           //resize，扩容table，如果达到64，那么将冲突的存储结构为红黑树                           if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                               treeifyBin(tab, hash);                           break;                       }           /*如果有相同的key值就结束遍历*/                       if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))                           break;                       p = e;                   }               }       /*就是链表上有相同的key值*/               if (e != null) { // existing mapping for key，就是key的Value存在                   V oldValue = e.value;                   if (!onlyIfAbsent || oldValue == null)                       e.value = value;                   afterNodeAccess(e);                   return oldValue;//返回存在的Value值               }           }           ++modCount;        /*如果当前大小大于门限，门限原本是初始容量*0.75*/           if (++size > threshold)               resize();//扩容两倍           afterNodeInsertion(evict);           return null;       } HashMap的键值存储
　　我们给 put() 方法传递键和值时，我们先对键调用 hashCode() 方法，计算并返回 hashCode，然后使用HashMap内部的hash算法，将hashCode计算为表中的具体位置，找到 Map 数组的 bucket 位置来储存 Node 对象。 解决Hash碰撞
　　如果hash到的数组位置已存在对象，即为Hash碰撞。JDK使用拉链法解决Hash碰撞问题。
　　即以原有的Node节点为基础，构造链表。将新的Node节点挂在后面。 链表过长导致的复杂度问题
　　HashMap的查询操作最佳时间复杂度是O(1)，但是当表中的某个链表过长时，查询该链表上的元素时间复杂度为O(n)。JDK1.8中解决了该问题，当HashMap中某链表长度大于8时，链表会重构为红黑树，这样，HashMap的最坏时间复杂度为O(n)。同理，为了不必要的消耗，当链表长度小于6时，红黑树会重新变回链表 读取过程public V get(Object key) {           Node e;           return (e = getNode(hash(key), key)) == null ? null : e.value;       }         /**       * Implements Map.get and related methods       *       * @param hash hash for key       * @param key the key       * @return the node, or null if none       */       final Node getNode(int hash, Object key) {           Node[] tab;//Entry对象数组       Node first,e; //在tab数组中经过散列的第一个位置       int n;       K k;       /*找到插入的第一个Node，方法是hash值和n-1相与，tab[(n - 1) & hash]*/       //也就是说在一条链上的hash值相同的           if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {       /*检查第一个Node是不是要找的Node*/               if (first.hash == hash && // always check first node                   ((k = first.key) == key || (key != null && key.equals(k))))//判断条件是hash值要相同，key值要相同                   return first;         /*检查first后面的node*/               if ((e = first.next) != null) {                   if (first instanceof TreeNode)                       return ((TreeNode)first).getTreeNode(hash, key);                   /*遍历后面的链表，找到key值和hash值都相同的Node*/                   do {                       if (e.hash == hash &&                           ((k = e.key) == key || (key != null && key.equals(k))))                           return e;                   } while ((e = e.next) != null);               }           }           return null;       }
　　get(key)方法时获取key的hash值，计算hash&(n-1)得到在链表数组中的位置first=tab[hash&(n-1)],先判断first的key是否与参数key相等，不等就遍历后面的链表找到相同的key值返回对应的Value值即可 HashMap的扩容 final Node[] resize() {          Node[] oldTab = table;          int oldCap = (oldTab == null) ? 0 : oldTab.length;          int oldThr = threshold;          int newCap, newThr = 0;          /*如果旧表的长度不是空*/          if (oldCap > 0) {              if (oldCap >= MAXIMUM_CAPACITY) {                  threshold = Integer.MAX_VALUE;                  return oldTab;              }   /*把新表的长度设置为旧表长度的两倍，newCap=2*oldCap*/              else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                       oldCap >= DEFAULT_INITIAL_CAPACITY)         /*把新表的门限设置为旧表门限的两倍，newThr=oldThr*2*/                  newThr = oldThr << 1; // double threshold          }       /*如果旧表的长度的是0，就是说第一次初始化表*/          else if (oldThr > 0) // initial capacity was placed in threshold              newCap = oldThr;          else {               // zero initial threshold signifies using defaults              newCap = DEFAULT_INITIAL_CAPACITY;              newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);          }                               if (newThr == 0) {              float ft = (float)newCap * loadFactor;//新表长度乘以加载因子              newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                        (int)ft : Integer.MAX_VALUE);          }          threshold = newThr;          @SuppressWarnings({＂rawtypes＂,＂unchecked＂})   /*下面开始构造新表，初始化表中的数据*/          Node[] newTab = (Node[])new Node[newCap];          table = newTab;//把新表赋值给table          if (oldTab != null) {//原表不是空要把原表中数据移动到新表中                  /*遍历原来的旧表*/                    for (int j = 0; j < oldCap; ++j) {                  Node e;                  if ((e = oldTab[j]) != null) {                      oldTab[j] = null;                      if (e.next == null)//说明这个node没有链表直接放在新表的e.hash & (newCap - 1)位置                          newTab[e.hash & (newCap - 1)] = e;                      else if (e instanceof TreeNode)                          ((TreeNode)e).split(this, newTab, j, oldCap);   /*如果e后边有链表,到这里表示e后面带着个单链表，需要遍历单链表，将每个结点重*/                      else { // preserve order保证顺序                   ////新计算在新表的位置，并进行搬运                          Node loHead = null, loTail = null;                          Node hiHead = null, hiTail = null;                          Node next;                                                 do {                              next = e.next;//记录下一个结点             //新表是旧表的两倍容量，实例上就把单链表拆分为两队，   　　　　　　　　　　　　　//e.hash&oldCap为偶数一队，e.hash&oldCap为奇数一对                              if ((e.hash & oldCap) == 0) {                                  if (loTail == null)                                      loHead = e;                                  else                                      loTail.next = e;                                  loTail = e;                              }                              else {                                  if (hiTail == null)                                      hiHead = e;                                  else                                      hiTail.next = e;                                  hiTail = e;                              }                          } while ((e = next) != null);                                                 if (loTail != null) {//lo队不为null，放在新表原位置                              loTail.next = null;                              newTab[j] = loHead;                          }                          if (hiTail != null) {//hi队不为null，放在新表j+oldCap位置                              hiTail.next = null;                              newTab[j + oldCap] = hiHead;                          }                      }                  }              }          }          return newTab;      } 扩容时机
　　当size超过阈值（数组长度负载因子*）时，即开始扩容，HashMap的负载因子为0.75。 为何要数组未满就扩容
　　避免频繁出现Hash碰撞，造成拉链过长（红黑树过长）。这样会导致查询复杂度频繁出现最坏情况 扩容过程
　　创建原本数组容量*2的新数组，将节点从原本的数组中迁移过去。 jdk1.7的问题put()时，HashMap会先遍历table数组，用hash值和equals()判断数组中是否存在完全相同的key对象， 如果这个key对象在table数组中已经存在，就用新的value代替老的value。如果不存在，就创建一个新的Entry对象添加到table[ i ]处。如果该table[ i ]已经存在其他元素，那么新Entry对象将会储存在bucket链表的表头，通过next指向原有的Entry对象，形成链表结构（hash碰撞解决方案） 扩容时，将原先table的元素全部移到newTable里面，重新计算hash，然后再重新根据hash分配位置。
　　问题点：两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了 为什么线程不安全
　　HashMap 在并发时可能出现的问题主要是两方面：
　　如果多个线程同时使用 put 方法添加元素，而且假设正好存在两个 put 的 key 发生了碰撞（根据 hash 值计算的 bucket 一样），那么根据 HashMap 的实现，这两个 key 会添加到数组的同一个位置，这样最终就会发生其中一个线程 put 的数据被覆盖
　　如果多个线程同时检测到元素个数超过数组大小 * loadFactor，这样就会发生多个线程同时对 Node 数组进行扩容，都在重新计算元素位置以及复制数据，但是最终只有一个线程扩容后的数组会赋给 table，也就是说其他线程的都会丢失，并且各自线程 put 的数据也丢失