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, k key, v val, node<k,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), 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, k key, v value, 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, key, value, 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, 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;
          }

• 扩容方法，消耗很大

          /**
           * 初始化或加倍数组的大小。如果为空，则根据属性阈值中保持的初始容量目标进行分配。
           * 否则，因为我们使用的是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;
          }