概述

HashMap是非线程安全的集合类,存储的是key/value的键值对

在java8之前,底层数据结构采用的是哈希表+链表的形式,如果hash冲突,那么就使用链地址法解决冲突

在java8之后,底层数据结构采用了哈希表+链表+红黑树的形式,当链表长度大于8时,将会转换成红黑树,以解决链表过长时导致的时间复杂度过大的问题


下面会对HashMap中重要的方法进行概述,并在源码当中也会进行详细的注解

Capacity概述

在java8之后,HashMap中的默认初始容量为16,并且规定了HashMap中的容量大小是始终是2的次幂,而且每次扩容也是扩容到原来的两倍(左移1位)

这样规定的原因有两点:

  • 第一: 能够保证在计算hashcode落在哪个node数组下标时的取模位运算更加的高效 直接通过(n-1) & hashcode即可直接算出下标值

    n是node数据的长度

  • 第二: 在resize()扩容方法中,在将旧node数组中的链表复制到新node数组中时,直接通过( hash & oldCap ) == 0 来判断是否需要将链表中的node进行偏移旧数组长度的值

hash()概述

hash()方法只要是为了扰乱传入的key对象的hashcode,从而使得key在哈希数组中分布的更加均匀

其底层通过以下代码来实现:

(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

将key的hashcode右移16位,然后在于原来的hashcode进行异或,这样使得最终得到的hash值结合了原始hashcode的高16位和低16位,使得分布更加均匀

get()概述

  • 先判断node数组不为空 && 长度大于0
    • 根据取模位运算得到数组下标
      • 判断是否存在node节点,如果存在
        • 如果相等,则直接返回
        • 如果不相等
          • 判断是否为树节点,如果是,则通过getTreeNode()来获取到对应的值
          • 如果不为树节点,那么就是链表节点,则遍历node的后继节点,判断是否相等,如果相等,则返回相等的后继节点

resize()概述

第一步,先根据旧数组的情况,计算出新数据的容量和扩容阈值:

  • 如果旧node数组长度大于0
    • 如果旧长度大于等于最大容量,则让其等于最大容量,防止溢出
    • 如果 旧长度*2 < 最大容量 && 旧长度 >= 默认初始容量,则扩容阈值变为原来的两倍
  • 如果旧扩容阈值大于0
    • 则将旧扩容阈值赋值给新数组长度
  • 否则默认为初始化node数组

第二步,再创建设置好新容量的node数组,然后将旧数组中的节点复制过去:

  • 遍历旧node数组,如果node不为空
    • 如果node的后继节点为空
      • 则直接将node节点放到新node数组中
    • 如果node为树节点(说明节点数大于8)
      • 通过split()方法分割红黑树中的节点,并添加到新node数组中
    • 如果都不是,则为链表节点
      • 遍历node的后继节点,将node的hashcode按位与上旧数组长度
        • 如果结果为0,则不需要移动偏移下标位置
        • 如果结果不为0,则需要往后偏移旧数组容量这么多个下标位置

put()概述

  • 如果node数组为空 || node数组长度等于0
    • 则进行resize(),创建node数组,并获取到数组长度n
  • 如果通过取模位运算得到数组下标对应的node为空
    • 以传入的key/value创建一个node节点,并设置到node数组中
  • 如果node节点不为空
    • 如果 node节点的hashcode==传入key的hashcode && ( node节点的key与传入key的引用相等 || (传入key不为空 && 调用equals()方法返回true ) )

      简单来说: 比较node中的key是否与传入的key相等

    • 如果不相等,但是属于树节点
      • 通过putTreeVal()把当前传入的key/value添加到红黑树中
    • 如果不相等,也不属于树节点,那么则为链表节点
      • 遍历node节点的后继节点
        • 如果遍历过程中找到相等的node节点,则退出遍历
        • 如果遍历到最后一个节点,也没找到,则通过传入的key/value创建新node节点,并添加
          • 添加后如果链表达到阈值,则将链表转化为红黑树

最后,当节点添加完成之后,再判断当前的节点数量是否已经超过扩容阈值,如果超过了,则再次调用 resize()方法进行扩容

HashMap重要源代码

public class HashMap<K,V> extends AbstractMap<K,V>
  implements Map<K,V>, Cloneable, Serializable {

  //-------------------常量------------------------
  //默认的初始容量: 16
  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

  //最大容量: 大约10亿
  static final int MAXIMUM_CAPACITY = 1 << 30;

  //默认负载因子: 0.75
  static final float DEFAULT_LOAD_FACTOR = 0.75f;

  //由链表转化为红黑树的阈值: 8
  static final int TREEIFY_THRESHOLD = 8;

  //由红黑树转化为链表的阈值: 6
  static final int UNTREEIFY_THRESHOLD = 6;

  //-------------------字段------------------------
  //存储Node节点的hash表
  //使用transient声明的变量不需要进行序列化
  transient Node<K,V>[] table;

  transient Set<Map.Entry<K,V>> entrySet;

  //记录map中的键值对个数
  transient int size;

  //扩容阈值,该值为: 当前容量*负载因子,当map拥有node节点个数大于扩容阈值时,就扩容
  int threshold;

  //-------------------构造方法------------------------
  //无参构造方法
  public HashMap() {
    //其他所有字段默认,负载因子为0.75
    this.loadFactor = DEFAULT_LOAD_FACTOR; 
  }

  //可指定 初始容量和负载因子
  public HashMap(int initialCapacity, float loadFactor) {
    ...
      this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
  }

  //可指定 初始容量,负载因子默认为0.75
  public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
  }

  //-------------------实现的重要内部类------------------------
  //Node节点(链表)
  static class Node<K,V> implements Map.Entry<K,V>{
    ...
  }

  //树节点(红黑树)
  static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    ...
  }

  //-------------------重要方法------------------------
  //计算key的hash值
  static final int hash(Object key) {
    int h;
    //将key的原始hash值与右移16位后(即获取到高16位)进行异或
    //这样能够让高16位和低16位都能参与运算,能保证hash更加均匀
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

  //-------------------get()方法------------------------
  //通过key获取元素
  public V get(Object key) {
    Node<K,V> e;
    //通过key的hashcode进行获取
    return (e = getNode(hash(key), key)) == null ? null : e.value;
  }

  //具体的获取节点方法
  final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //如果node数组不为空 && 数组长度大于0
    //&& 通过按位与(即取模运算)计算出来的node节点不为空
    //(n - 1) & hash : (数组长度-1) & hashcode ,就可以计算出落在哪个数组下标
    if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
      // 总是先检查第一个Node节点
      //如果node节点的hash=hash && ( node节点的key和传入的key引用相等 || 传入的key.equlas(node节点的key)为ture )
      //默认key是Object,那么equlas判断的就是引用,如果重写了equals方法,那么就调用重写的进行判断,默认是比较值是否相等
      if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
        //如果就是node节点,则直接返回
        return first;

      //如果node首节点不是要找的节点
      //如果node的下一个节点不为空
      if ((e = first.next) != null) {
        //如果node首节点是树节点,则调用getTreeNode进行获取
        if (first instanceof TreeNode)
          return ((TreeNode<K,V>)first).getTreeNode(hash, key);
        //如果是普通链表节点,则依次遍历node的后继节点,先比较hashcode,再比较equlas方法
        do {
          if (e.hash == hash &&
              ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
        } while ((e = e.next) != null);
      }
    }
    return null;
  }

  //-------------------put()方法------------------------
  //将键值对放入map中
  public V put(K key, V value) {
    //先通过hash()计算key的hashcode,再调用putVal()方法存放键值对
    return putVal(hash(key), key, value, false, true);
  }

  //正真存放键值对的方法
  //int hash: key的hashcode
  //K key: 要保存的key
  //V value: key对应的value值
  //boolean onlyIfAbsent: 如果为true,则不改变现有值
  //boolean evict: 如果为false,则该表处于创建模式
  final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                 boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //如果node数组为空 || node数组长度等于0
    if ((tab = table) == null || (n = tab.length) == 0)
      //则进行resize(),创建node数组,并获取到数组长度n
      n = (tab = resize()).length;

    //如果通过取模位运算得到数组下标对应的node为空
    if ((p = tab[i = (n - 1) & hash]) == null)
      //以传入的key/value创建一个node节点
      tab[i] = newNode(hash, key, value, null);
    //如果node节点不为空
    else {
      Node<K,V> e; K k;
      //如果 node节点的hashcode==传入key的hashcode && ( node节点的key与传入key的引用相等 || (传入key不为空 && 调用equals()方法返回true ) )
      if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
        //则将当前node节点缓存
        e = p;
      //如果都不满足(即不相等)
      //如果属于树节点
      else if (p instanceof TreeNode)
        //就通过putTreeVal()把当前传入的key/value添加到红黑树中
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
      //如果都不满足(即不相等)
      //也不属于树节点(即属于链表)
      else {
        //遍历node节点的后继节点,并添加传入的key/value
        for (int binCount = 0; ; ++binCount) {
          //如果到了最后一个节点
          if ((e = p.next) == null) {
            //则创建新node节点,并添加
            p.next = newNode(hash, key, value, null);
            //如果链表达到阈值,则将链表转化为红黑树
            if (binCount >= TREEIFY_THRESHOLD - 1)
              treeifyBin(tab, hash);
            break;
          }
          //如果在遍历中找到了相等的节点,则退出循环,但是此时,已经当相等的节点的引用保存到了临时变量e中
          if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
            break;
          p = e;
        }
      }

      //如果临时node不为空
      if (e != null) {
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
          e.value = value;
        afterNodeAccess(e);
        return oldValue;
      }
    }
    //将修改的总数+1
    ++modCount;
    //如果当前节点总数量大于阈值,则进行resize()调整map的大小
    if (++size > threshold)
      resize();
    afterNodeInsertion(evict);
    return null;
  }

  //-------------------resize()方法,即扩容------------------------
  final Node<K,V>[] resize() {
    //保存node数组引用
    Node<K,V>[] oldTab = table;
    //保存node数组长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //保存旧扩容阈值
    int oldThr = threshold;
    int newCap, newThr = 0;
    //如果旧node数组长度大于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;
    }
    //如果旧扩容阈值大于0
    else if (oldThr > 0)
      //将旧扩容阈值赋值给新数组长度(即扩容为原来的两倍,因为扩容阈值每次都是原来的两倍)
      newCap = oldThr;
    //否则(初始扩容阈值容量为0,则表示使用默认值,即第一次创建node数组)
    else {
      //将新容量设置为默认初始容量:8
      newCap = DEFAULT_INITIAL_CAPACITY;
      //将扩容阈值设置为默认初始容量*默认负载因子(8*0.75再取整为6)
      //扩容阈值表示的如果map中的node节点个数超过了扩容阈值,则扩容
      newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    //如果新的扩容阈值为0,则重新计算扩容阈值
    if (newThr == 0) {
      float ft = (float)newCap * loadFactor;
      newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;

    //使用新数组容量创建一个新node数组,让后将旧node数组中的值复制到新node数组中
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
      //遍历旧node数组
      for (int j = 0; j < oldCap; ++j) {
        Node<K,V> e;
        //如果node不为空
        if ((e = oldTab[j]) != null) {
          oldTab[j] = null;
          //如果node的后继节点为空(说明只有一个节点)
          if (e.next == null)
            //直接将node节点放到新node数组中
            newTab[e.hash & (newCap - 1)] = e;
          //如果node为树节点(说明节点数大于8)
          else if (e instanceof TreeNode)
            //通过split()方法分割红黑树中的节点,并添加到新node数组中
            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
          //如果都不是,则为链表节点(在转移时需维持秩序)
          else {
            Node<K,V> loHead = null, loTail = null;
            Node<K,V> hiHead = null, hiTail = null;
            Node<K,V> next;
            //遍历node的后继节点
            do {
              next = e.next;
              //将node的hashcode按位与上旧数组长度
              //因为oldCap是2的次幂,比如oldCap为16,则换算2进制为0001 0000,因为0&任何数都为0,1&任何数还是任何数本身,所以,如果hashcode在从右数第5位上为0,则结果就为0,否则就不为0
              //如果为0,则缓存在低位上
              if ((e.hash & oldCap) == 0) {
                if (loTail == null)
                  loHead = e;
                else
                  loTail.next = e;
                loTail = e;
              }
              //如果不为0,则缓存在高位上
              else {
                if (hiTail == null)
                  hiHead = e;
                else
                  hiTail.next = e;
                hiTail = e;
              }
            } while ((e = next) != null);

            //如果为0,则不需要移动偏移下标位置
            if (loTail != null) {
              loTail.next = null;
              newTab[j] = loHead;
            }

            //如果不为0,则需要往后偏移旧数组容量这么多个下标位置
            if (hiTail != null) {
              hiTail.next = null;
              newTab[j + oldCap] = hiHead;
            }
          }
        }
      }
    }
    return newTab;
  }

}
0条评论
头像
ICP证 : 浙ICP备18021271号