hashMap源码--JDK1.8

重要的属性

• 默认容量为16

  /**
   * The default initial capacity - MUST be a power of two.
   * 建议容量为 2的n次幂
   */
  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

• 默认负载因子

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

• 最大容量 2^30

  /**
   * 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;

• 数据bin转换成红黑树的阈值

  /**
   * hash桶的存储方式由list转为tree的转换阈值(插入第9个元素时，list转为tree)
   * 该阈值必须大于2，并且至少应为8才能与树删除中的假设（收缩时转换回普通箱）相啮合
   */
  static final int TREEIFY_THRESHOLD = 8;
  
  /**
   * 在调整hash桶大小的操作中，取消hash桶的树化存储的计数阈值
   * (当一个hash桶中的元素小于该值时，转换成链表存储)
   * 应该小于TREEIFY_THRESHOLD，且最大为6，用于删除操作后的收缩检查
   */
  static final int UNTREEIFY_THRESHOLD = 6;
  
  /**
   * hash桶树化存储的table的最小容量。（否则，如果hash桶中的节点过多，将调整table的大小。）
   * 应至少为 4 * TREEIFY_THRESHOLD，以避免调整大小和树化阈值之间的冲突。
   * 因为一个比较小，比较满的散列表的性能不如一个比较大，比较空的散列表，
   * 这种请款先考虑变大，而不是树化存储
   */
  static final int MIN_TREEIFY_CAPACITY = 64;

• 数据table

  /**
   * 第一次使用时初始化，根据需要调整大小(始终为2的n次幂)
   * 在某些操作中，我们还允许长度为零，以允许使用当前不需要的引导机制。
   */
  transient Node<K,V>[] table;
  
  //键值对的数量
  transient int size;
  
  //结构修改的次数
  transient int modCount;  
  
  //下一个要调整大小的大小值 （容量*负载系数）
  //如果hash桶数组没有初始化，则该字段持有出事容量，或者是0(表示使用 DEFAULT_INITIAL_CAPACITY)
  int threshold;
  
  //负载因子
  final float loadFactor;

• 数据节点类型

  static class Node<K,V> implements Map.Entry<K,V> {
          final int hash;    //用来定位数组索引位置
          final K key;
          V value;
          Node<K,V> next;   //链表的下一个node
  
          Node(int hash,K key,V value,Node<K,V> next) { ... }
          public final K getKey(){ ... }
          public final V getValue() { ... }
          public final String toString() { ... }
          public final int hashCode() { ... }
          public final V setValue(V newValue) { ... }
          public final boolean equals(Object o) { ... }
  }
  
  
  static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
          TreeNode<K,V> parent;  // 父
          TreeNode<K,V> left;    // 左
          TreeNode<K,V> right;   // 右
          TreeNode<K,V> prev;    // needed to unlink next upon deletion
          boolean red;           // 判断颜色
          TreeNode(int hash,V val,V> next) {
              super(hash,key,val,next);
          }
          // 返回根节点
          final TreeNode<K,V> root() {
              for (TreeNode<K,V> r = this,p;;) {
                  if ((p = r.parent) == null)
                      return r;
                  r = p;
              }

从构造方法-到扩容

• 构造方法

  public HashMap(int initialCapacity,float loadFactor) {
          if (initialCapacity < 0)
              throw new IllegalArgumentException("Illegal initial capacity: " +
                                                 initialCapacity);
          if (initialCapacity > MAXIMUM_CAPACITY)
              initialCapacity = MAXIMUM_CAPACITY;
          if (loadFactor <= 0 || Float.isNaN(loadFactor))
              throw new IllegalArgumentException("Illegal load factor: " +
                                                 loadFactor);
          // 获得对应容量的 2的n次幂
          this.loadFactor = loadFactor;
          this.threshold = tableSizeFor(initialCapacity);
      }
  
      // 构造新的HashMap 使用Map接口的集合: 使用默认loadFactor(0.75) 足以(最小可用)将映射保存在指定Map中的初始容量
      public HashMap(Map<? extends K,? extends V> m) {
          this.loadFactor = DEFAULT_LOAD_FACTOR;
          putMapEntries(m,false);
      }

• putAll()方法

  // 实现 Map.putAll and Map constructor 这俩方法
      final void putMapEntries(Map<? extends K,? extends V> m,boolean evict) {
          int s = m.size();
          if (s > 0) {
              // 判断table是否已经初始化
              if (table == null) { // pre-size
                  // capacity * loadFactor = threshold（最小可用 入参map的size=threshold）
                  float ft = ((float)s / loadFactor) + 1.0F;
                  // 得到保存入参map(size)需要的最小 capacity
                  int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                           (int)ft : MAXIMUM_CAPACITY);
                  //根据容量 刷新阈值
                  if (t > threshold)
                      threshold = tableSizeFor(t);
              }
              // 已初始化，并且m元素个数大于阈值，进行扩容处理
              else if (s > threshold)
                  resize();
  
              for (Map.Entry<? extends K,? extends V> e : m.entrySet()) {
                  K key = e.getKey();
                  V value = e.getValue();
                  // constructor-evict:false 
                  // putAll-evict:true
                  putVal(hash(key),value,false,evict);
              }
          }
      }

• 核心put方法

  /**
           * 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,boolean onlyIfAbsent,boolean evict) {
              Node<K,V>[] tab;
              Node<K,V> p;
              int n,i;
              // table未初始化或者长度为0，进行扩容
              if ((tab = table) == null || (n = tab.length) == 0)
                  n = (tab = resize()).length;
              // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
              if ((p = tab[i = (n - 1) & hash]) == null)
                  tab[i] = newNode(hash,null);
               // 桶中已经存在元素
              else {
                  Node<K,V> e; K k;
                  // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
                  if (p.hash == hash &&
                      ((k = p.key) == key || (key != null && key.equals(k))))
                      // 将第一个元素赋值给e，用e来记录
                      e = p;
                  else if (p instanceof TreeNode)
                      e = ((TreeNode<K,V>)p).putTreeVal(this,tab,hash,value);
                  else {
                      for (int binCount = 0; ; ++binCount) {
                          if ((e = p.next) == null) {
                              p.next = newNode(hash,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;
          }

• 扩容方法，消耗很大

  /**
           * 初始化或加倍数组的大小。如果为空，则根据属性阈值中保持的初始容量目标进行分配。
           * 否则，因为我们使用的是2的幂，所以每个bin中的元素必须保持相同的索引，或者在新表中以2的幂偏移。
           *
           * @return the table
           */
          final Node<K,V>[] resize() {
              Node<K,V>[] 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;
                  }
                  // 没超过最大值，就扩充为原来的2倍(翻倍后不能大于最大容量)
                  else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                           oldCap >= DEFAULT_INITIAL_CAPACITY)
                      newThr = oldThr << 1; // double threshold
              }
              // 初始化 初始化容量=阈值(2参数构造中赋值的)
              else if (oldThr > 0) // initial capacity was placed in threshold
                  newCap = oldThr;
              // 初始化方式--threshold=0（表示使用默认值 DEFAULT_INITIAL_CAPACITY）
              else {               // zero initial threshold signifies using defaults
                  newCap = DEFAULT_INITIAL_CAPACITY;
                  newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
              }
  
              // 计算新的resize上限
              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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
              table = newTab;
              if (oldTab != null) {
                  // 把每个bucket都移动到新的buckets中
                  for (int j = 0; j < oldCap; ++j) {
                      Node<K,V> e;
                      if ((e = oldTab[j]) != null) {
                          oldTab[j] = null;
                          if (e.next == null)
                              newTab[e.hash & (newCap - 1)] = e;
                          else if (e instanceof TreeNode)
                              ((TreeNode<K,V>)e).split(this,newTab,j,oldCap);
                          else { // preserve order
                              // 链表优化重hash的代码块
                              Node<K,V> loHead = null,loTail = null;
                              Node<K,V> hiHead = null,hiTail = null;
                              Node<K,V> next;
                              do {
                                  next = e.next;
                                  // 原index
                                  if ((e.hash & oldCap) == 0) {
                                      if (loTail == null)
                                          loHead = e;
                                      else
                                          loTail.next = e;
                                      loTail = e;
                                  }
                                  // 原index + oldCap
                                  else {
                                      if (hiTail == null)
                                          hiHead = e;
                                      else
                                          hiTail.next = e;
                                      hiTail = e;
                                  }
                              } while ((e = next) != null);
                              // 原index放到bucket里
                              if (loTail != null) {
                                  loTail.next = null;
                                  newTab[j] = loHead;
                              }
                              // 原index + oldCap放到bucket里
                              if (hiTail != null) {
                                  hiTail.next = null;
                                  newTab[j + oldCap] = hiHead;
                              }
                          }
                      }
                  }
              }
              return newTab;
          }