Java——HashMap源码学习

作者: 英勇青铜5 | 来源:发表于2017-08-24 15:17 被阅读1330次

    学习资料;

    这篇笔记是第二次整理,第一次是16年11月份,只是之前能写出来的太少,中途而废。最近又来看HashMap的东西,比上次看时理解的东西多了些,就重新整理下

    目前,HashMap内,还是有很多问题,不明白,以后会再做补充

    重点学习HashMap,本篇学习笔记,会有很多错误,请指出


    1. Map接口

    实现map接口的主要有四个HashTable,HashMap,LinkedHashMap,TreeMap

    HashTable,HashMap区别:

    1. HashTable的大部分方法都做了同步,而HashMap没有。HashMap不是线程安全的
    2. HashTable不允许key,valuenull,而HashMap可以为null
    3. 两者对keyhash算法和hash值到内存索引的映射算法不同

    HashMap优点特性就是高性能,存放和查询是很高效的,缺点就是无序性,存入的元素,在遍历时是无序的

    LinkedHashMap继承自HashMap,除了具备HashMap高性能优点外,还具有有序性。LinkedHashMapHashMap的基础上,增加了一个链表来存放元素的顺序

    LinkedHashMap可以简单理解为一个维护了元素次序表的HashMap


    LinkedHashMap提供了两种类型的顺序:存放(插入)元素时的顺序,最近访问顺序

    可以使用3个参数的构造方法来指定排序行为

    public LinkedHashMap(int initialCapacity,
                             float loadFactor,
                             boolean accessOrder)
    

    accessOrdertrue时,按照元素最后访问时间来排序,默认情况下为false

    当为true时,使用get()执行来一次获取操作时,当前元素会被挪到整个LinkedHashMap最末尾位置

    需要注意的是,当设置accessOrdertrue时,不能用于Iterator遍历

    不要在迭代器模式中修改被迭代的集合


    TreeMap实现了SortMap接口,可以对元素进行排序

    TreeMap排序是指根据条件对存入的key进行按照规则进行了排序,是基于元素本身的固有顺序。而LinkedHashMap只是基于元素进入集合的顺序或者访问的先后顺序进行排序

    TreeMap为了确定key的排序,可以通过两种方式来指定

    1. 通过TreeMap的构造方法,public TreeMap(Comparator<? super K> comparator),指定一个Comparator
    2. 使用一个自身实现了Comparable接口的key

    TreeMap内部实现是基于红黑树红黑树是一种平衡查找树,统计性能要优于平衡二叉树。具有良好的最坏情况运行时间,可以在O(log n)时间内做查找、插入和删除,其中n代表树中元素的数目

    详细可以看HashMap、Hashtable、HashSet 和 ConcurrentHashMap 的比较


    2. JDK1.8中的HashMap

    在之前学习时,写过一个Java基础学习——HashMap原理学习,可以帮助理解原理学习


    个人理解,举例:

    一家超大型购物商场,拥有一百万种不同品牌的商品

    假如,当世界上第一家这样规模的大型商场开业时,由于没啥经验,商场的工作人员从仓库取出商品摆放时,从商场门口开始,在仓库拿到啥就开始摆放啥,也不管物品是啥,只要能放得下,就依次摆放。而等到顾客来买东西时,全靠随缘。除非打5折,否则一年也卖不出多少东西

    现实这种情况根本不会发生,为了方便顾客快速定位商品的相对准确位置,会 根据商品的固有属性来分区

    例如,我最爱的农夫山泉,就会放在一个饮品区,和各种纯净水以及其他的喝的,摆在一个相对集中的区域。我到了一家从来没有去过的大型商场去买农夫山泉, 购买效率很大程度取决于我用了多久找到农夫山泉所在的饮品区,到了饮品区,再快速定位到纯净水货架。实际生活中,一般情况下,即使很大型的商场,也可以比较快速的买到一瓶

    确定饮水区的过程可以看作为HashMap中涉及hash操作的整个过程


    hashMap内存结构图

    图来自美团技术点评 Java 8系列之重新认识HashMap

    简单说来,HashMap就是将keyhash算法,然后将hash值映射到内存地址,之后可以直接获取key所对应的数据

    HashMap就可以简单看作这样一家超大型超市,根据不同商品固有属性key,做hash算法后,得到一个index,便得知该商品所处区域,也就是快速计算得到链表数组索引。而一个品牌的商品肯定不止一个,这样做hash算法后,结果index肯定会有冲突,这时就要用到货架链表,将同一个品牌的商品依次摆放在货架上,最终,一个key就和value建立的映射


    JDK1.8中,HashMap内部结构是数组(哈希桶)+链表+红黑树

    HashMap的高性能需要下面3点:

    1. hash() 算法必须是高效的
    2. hash值映射内存地址,也就是计算数组索引,映射算法必须是高效的
    3. 根据内存地址,数组索引,可以直接获取得对应的值

    最常用到的就是put(),get()方法

     Map<String, String> map = new HashMap<>();
     map.put("1", "a");
     map.put("2", "b");
     for (String key : map.keySet()) {
        System.out.println("key = " + key + " ;;; value = " + map.get(key));
     }
    
    if (map.containsKey("1")) {
        map.remove("1");
    }
    
    System.out.println("size = " + map.size());
    

    本次重点学习存放put()扩容resize()


    2.1 构造方法

    有 4 个 构造方法,最经常使用的是空参的

    • public HashMap()
    • public HashMap(int initialCapacity),指定容量
    • public HashMap(int initialCapacity, float loadFactor),指定容量、负载因子
    • public HashMap(Map<? extends K, ? extends V> m),存放另一个HashMap
    /**
     * The default initial capacity - MUST be a power of two.
     * 默认大小
     * 
     * 使用空参构造方法时,默认初始化大小 16
     */
    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;
    
    /**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     * 链表数组
     * 
     * 这个table会在 HashMap 第一次使用时被创建,一般会在 put()方法时
     * 
     * table.length 一直都会是 2 的 n 次方,这样设计的目的在于
     * 扩容时,更加高效的统计数组的index,用位运算替代取余操作
     */
    transient Node<K,V>[] table;
    
    
    /**
     * Constructs an empty HashMap with the default initialcapacity
     * (16) and the default load factor (0.75).
     * 
     * 空构造方法:初始化 负载因子(loadFactor)为 0.75
     * 此时,默认容量大小为 16,阈值就是 12
     */
     public HashMap() {
         this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
     }
    

    使用空参构造方法时,指定loadFactor为默认值0.75

    负载因子是0 ~ 1之间的浮点数,决定了在扩容之前,HashMap的内部数组链表的填充度

    阈值(threshold) = 容量(capacity) * 负载因子(load factor)

    HashMap的实际容量超过阈值时,HashMap便会扩容。因此,实际上HashMap的实际填充率不会超过负载因子

    负载因子也可以设置为1或者大于1,但此时会导致大量的hash冲突

    负载因子越大,使用越少的内存空间,而一个数组索引位置上的链表长度就越大,一个链表中存放的元素越多,越容易引起hash值冲突。使用get()方法进行获取元素操作,进行遍历链表时的效率也就越低

    相反,负载因子越小,一个数组索引位置上的链表,长度越小,一个链表中存放的元素越少,虽然遍历的效率高了,但也就浪费了较多空间

    transient,不需要被序列化的属性可以使用。目前不理解,先不管


    2.2 Node,键值对单向链表

    Node[]table数组中的元素,Node就是存放key,value的对象,结构是单向链表,每个Node都会指向下一个,若没有next就指向null

     /**
      * Basic hash bin node, used for most entries.  (See below for
      * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
      */
     static class Node<K,V> implements Map.Entry<K,V> {
         final int hash; // hash 值
         final K key;
         V value;
         Node<K,V> next; // 下一个键值对
    
         Node(int hash, K key, V value, Node<K,V> next) {
             this.hash = hash;
             this.key = key;
             this.value = value;
           this.next = next;
          }
    
          public final K getKey()        { return key; }
          public final V getValue()      { return value; }
          public final String toString() { return key + "=" + value; }
    
          public final int hashCode() {
                // 将key 和 value的hash值,异或
              return Objects.hashCode(key) ^ Objects.hashCode(value);
          }
    
          // 设置 Value,并将覆盖的旧value返回
          public final V setValue(V newValue) {
              V oldValue = value;
              value = newValue;
              return oldValue;
          }
    
          // 比较两个Node对象是否相等
          // 比较key value是否完全相等
          public final boolean equals(Object o) {
              if (o == this)
                  return true;
              if (o instanceof Map.Entry) {
                  Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                  if (Objects.equals(key, e.getKey()) &&
                      Objects.equals(value, e.getValue()))
                      return true;
              }
              return false;
          }
     }
    

    2.3 数组索引计算

    1.7中,HashMap内部是数组 + 链表

    1.8中,链表的长度一旦超过8时,就会转为红黑树

    // 1.8 增加的变量
    
    static final int TREEIFY_THRESHOLD = 8;
    

    高效确定一个元素key所在链表的索引,需要两步:

    1. 计算元素健keyhash值,hash(Object key)方法
    2. 利用计算得到的hash,获取数组索引,indexFor(hash(key),table.length)

    HashMap的高效性,很关键一部分就在于hash()算法以及indexFor()

    当使用put()方法存放一个元素时,首先会根据key计算hash值,之后利用hash值,确定该元素所属链表的索引index。也就说这个两步走,在put()中是必须要走的

    JDK1.8中对计算索引两步走又进行了优化,先了解1.7的实现


    2.3.1 在JDK1.7中的实现

    目前不懂为啥1.7中,这样来设计计算hash值,在知乎看到了也有人问这个问题:

    JDK 源码中 HashMap 的 hash 方法原理是什么?

    最高票的回答很赞,而且在回答中答主给了自己的学习笔记How is hashCode() calculated in Java?,很有深度

    两步走,第一步,计算hash值

     final int hash(Object k) {
        int h = 0;
        //这个特殊选项先不去管它
        if (useAltHashing) {
            if (k instanceof String) {
                return sun.misc.Hashing.stringHash32((String) k);
            }
            h = hashSeed;
        }
        //第一件事:调用Key自带的hashCode()函数获得初始哈希值
        h ^= k.hashCode();
    
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        //初始哈希值做进一步优化(注:^为“异或”操作)
        //异或:每一位上的值相同返回0,不同返回1。
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
     }
    

    调用key类型自带的hashCode()函数,计算原始哈希值

    以上摘抄自How is hashCode() calculated in Java?

    在最后计算hash值时,用了4^运算,1.8中做的优化便是由4次变做了1

    又看到了这篇:HashMap hash方法分析

    看懂似懂非懂的

    这里原理为啥这么写的,先不管了,先记结论

    结论:

    无论1.X的JDK,这个hash()方法的优化目的都是为了防止Object key自身的hashCode()方法实现比较差,为了使hash值更加均衡,减少hash冲突


    两步走,第二步,计算索引值

    indexFor()的目的是为计算index,在买农夫山泉的例子中,就是快速定位饮品区,然后可以快速找到农夫山泉货架这个步骤

    实际生活中,超市不会一个货架只摆放一瓶农夫山泉。在元素多时,HashMap也不会一个链表只存放一个元素

    HashMap的最大容量是Integer.MAX_VALUE,但table.length一定不会是这么大。若一个元素占用一个链表,那需要一个容量为2 ^ 31 - 1的数组,这样虽然index不会存在冲突,但空间上是不允许的

    计算这样一个index首先想到的便是除法散列法

    // 求模数实际是通过一个除法运算得到
    h % length
    

    JDK1.7中,计算链表所处的数组索引index用的是h & (length-1)

    用的是&而不是%

    这便是代码设计者牛B的地方

    // 1.8 中已删除,
    
    /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 :
    // "length must be a non-zero power of 2";
         return h & (length-1);
    }
    

    HashMap中链表的length总是2的n次方length总是2的n次方时,h & (length-1)运算等价于对length取模,也就是h%length,但&具有更高的效率

    这也是为啥要将table.lenth设计为总是2的n次方原因

    2的n次方,必然是偶数,length -1 为奇数,转换成二进制之后,最后一位为1

    h & (length-1)时,最后一位的是0还是1,就取决于h的值,也就是说index的奇偶性取决于h

    假如length不一定是2的n次方,当length为奇数时,length-1转换成二进制后,最后一位是0,这样无论h为多少,h & (length-1)时,最后一位的都是0,这样index都是偶数,数组只有偶数索引处有值,也就造成了空间浪费

    结论:

    h & (length-1)既高效又能使index分布均匀


    2.3.2 1.8中的实现

    1.8代码中,indexFor(int h, int length)删除了,在确定index值时,简化成了tab[i = (n - 1) & hash],其中hash便是hash(Object key)方法计算的值,使用的原理和indexFor()还是一样的,只是减少了一次方法调用

    1.8中获取索引index

     /**
      * Computes key.hashCode() and spreads (XORs) higher bits of hash
      * to lower.  Because the table uses power-of-two masking, sets of
      * hashes that vary only in bits above the current mask will
      * always collide. (Among known examples are sets of Float keys
      * holding consecutive whole numbers in small tables.)  So we
      * apply a transform that spreads the impact of higher bits
      * downward. There is a tradeoff between speed, utility, and
      * quality of bit-spreading. Because many common sets of hashes
      * are already reasonably distributed (so don't benefit from
      * spreading), and because we use trees to handle large sets of
      * collisions in bins, we just XOR some shifted bits in the
      * cheapest possible way to reduce systematic lossage, as well as
      * to incorporate impact of the highest bits that would otherwise
      * never be used in index calculations because of table bounds.
      */
     static final int hash(Object key) {
         int h;
         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
     }
    

    只进行了一次^运算,h值自身的高16位 和 低16位进行^运算

    混合原始哈希码的高位和低位,以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征,这样高位的信息也被变相保留下来

    这也弥补了取余时只有低位参与运算,而导致hash冲突变多的情况

    这么做可以在数组tablelength比较小的时候,也能保证考虑到高低Bit都参与到Hash的计算中,同时不会有太大的开销

    HashMap哈希算法例图.png

    图来自美团技术点评 Java 8系列之重新认识HashMap

    看到有人说(h = key.hashCode()) ^ (h >>> 16)这一步处理,是扰动函数,目的就是为了是使hash值分布更均匀,之后再计算index也能减少冲突


    2.4 put放入

    put()

    put()方法内,调用了putVal()方法

    public V put(K key, V value) {
         return putVal(hash(key), key, value, false, true);
    }
    

    key已经存在的情况下,会将旧的value替换,并返回旧的value


    putVal()

    1. 判断HashMap内的链表数组table是否已经创建过,也就是判断是否为初始化状态
    2. 确定index,判断数组index位置上是否有链表,没有就创建,有就准备遍历
    3. 判断链表上第一元素键值对是否和要存入的目标键值对相等;相等就直接进行覆盖操作
    4. 判断链表是否已转为红黑树
    5. 遍历链表,过程中确定是否进行转换红黑树操作,以及根据目标键值对确定是加到链表尾部还是覆盖操作
    6. put目标键值对成功,++size,判断是否需要扩容,并返回null
    /**
     * onlyIfAbsent,为true时,不改变已经存在的value
     * evict,为false时,说明是在初始化状态中调用
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        // tab,临时链表数组 ; p ,节点,临时键值对 
        // n,临时数组长度; i, index       
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        
        // 步骤1: table为null或者 lenght等于 0 ,说明需要初始化,先扩容
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
            
        // 步骤2: 确定index,index上链表为null,就创建链表
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        
        // index上链表不为 null,就说明index冲突,链表已存在 
        // 之后开始准备遍历链表,此时的p,是链表的头,链表上的第一个元素
        else {
            Node<K,V> e; K k;
            
            // 步骤3:将要存入的对象键值对,与p进行比较
            // 若相等,就说明需要将value进行覆盖,直接进行覆盖操作
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            
            // 步骤4: p是否已转为红黑树
            else if (p instanceof TreeNode)
               e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            
            // 此时,还为链表
            else {
                // 步骤5: 遍历链表
                for (int binCount = 0; ; ++binCount) {
                    // 在尾部节点添加要存入的目标键值对
                    // 当链表内元素个数为8时,就将链表转换为红黑树,并结束
                    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.next 不为 null,没有到链表尾部,并且覆盖节点不存在
                    // 将e赋给p,进行下一轮
                    p = e;
                }
            }
            
            // 覆盖操作
            // e不 null, 说明上面有覆盖节点,进行了 e = p 操作
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                
                // HashMap子类LinkedHashMap需要重写的方法
                afterNodeAccess(e);
                return oldValue;
            }
        }
        
        // 步骤6
        // 此时,已经成功存入目标键值对,之后主要就是判断是否需要扩容
            
        // 记录HashMap结构被改变次数
        ++modCount;
        
        // 判断是非需要进行扩容
        // size 先加 1
        if (++size > threshold)
            resize();
            
        // HashMap子类LinkedHashMap需要重写的方法
        afterNodeInsertion(evict);
        
        // 返回 null
        return null;
    }
    

    afterNodeAccess(e)afterNodeInsertion(evict)这两个方法先不用管,是为LinkedHashMap准备的

    modCount这个值是用来记录HashMap内结构被改变的次数

    HashMap不是线程安全的,在使用iterator进行迭代时,通过这个值来判断,如果修改了HashMap结构,便会抛出异常

    整个put()方法流程:

    hashMap put方法执行流程图

    图来美团点评技术团队 Java 8系列之重新认识HashMap


    2.5 扩容

    HashMap容量到达阈值时,再进行put操作就会进行扩容操作

    扩容是1.8代码改动比较大的地方,但原理是不变的。1.7更好理解,先看1.7中的实现

    2.5.1 1.7版本

    每次扩容操作都是2

    resize()

    void resize(int newCapacity) {
       // 将table赋给临时的oldTable
        Entry[] oldTable = table;
       
       // 判断当前oldTable.length是否为 1 >> 30
       // 是,就直接将阈值设置为最大容量
       // 之后便不会再进行扩容
       int oldCapacity = oldTable.length;
       if (oldCapacity == MAXIMUM_CAPACITY) {
           threshold = Integer.MAX_VALUE;
           return;
       }
    
       // 创建一个大小为newCapacity 的 Entry数组
       Entry[] newTable = new Entry[newCapacity];
       
       // 将 oldTable 数据装进 newTable
       transfer(newTable);
       
       // 将新的数组赋给table
       table = newTable;
     
       // 修改为新的阈值
       threshold = (int)(newCapacity * loadFactor);
    }
    

    transfer()

    将数组链表中的元素装进新的扩容后的链表数组

    需要考虑的是,容量变大后,如何进行稀释元素

    void transfer(Entry[] newTable) {
        // 临时 Entry 数组
        Entry[] src = table;   
        
        // 新的容量                
        int newCapacity = newTable.length;
        
        // 遍历数组
        for (int j = 0; j < src.length; j++) { 
            // 当前index上的链表
            Entry<K,V> e = src[j]; 
            
            // 当前index上有元素           
            if (e != null) {
            
                // 释放旧Entry数组的对象引用
                src[j] = null;
                
                // 遍历链表
                do {
                    // 临时 next 键值对
                    Entry<K,V> next = e.next;
                    
                    // 计算 e 新的index
                    int i = indexFor(e.hash, newCapacity);
                    
                    // 进行标记,将e.next指向链表头
                    // 这里是单链表的头插法
                    // 新元素放在链表头,旧元素放链表尾部
                    e.next = newTable[i]; 
                    
                    // 将键值对e 放在链表数组 i 位置上的链表头位置
                    newTable[i] = e;  
                    
                    // 进行下一轮    
                    e = next;            
                } while (e != null);
             }
        }
    }
    

    1.7的版本,遍历链表,根据链表元素的key重新计算index,之后采用单链表的头插法进行扩容后的链表填充操作

    在进行transfer操作时,对于一个e键值对对象来说,e.next指向的是newTable[i]i位置上链表的头

    此时分2种情况,其实是一回事,感觉说2种情况更容易理解

    newTable[i] == null时,也就是此index上的链表第一次放入键值对元素,此时,e.next就是为null了,e就作为此链表的尾部了,在单链表中,尾部节点的next为null

    newTable[i] != null,说明index发生了冲突,也就是此index上的链表已经存在元素了,e.next指向了newTable[i],也就是指向了上次放入的键值对元素,之后newTable[i] = e


    下面举个例子说明下扩容过程。假设了我们的hash算法就是简单的用key进行mod 一下表的大小,也就是数组的长度。其中哈希桶数组table[]size=2, 所以key = 3、7、5put顺序依次为 5、7、3。在mod 2以后都冲突在table[1]这里了。这里假设负载因子loadFactor=1,即当键值对的实际大小size 大于table的实际大小时进行扩容。接下来的三个步骤是哈希桶数组 resize成4,然后所有的Node重新rehash的过程

    jdk1.7扩容例图

    例子来美团点评技术团队 Java 8系列之重新认识HashMap


    2.5.2 1.8版本

    1.8的版本在稀释操作时,做了优化

    HashMap的初始化容量为16,扩容是在之前的容量基础上的2倍,最终一定还是2的n次方

    扩容后,元素的位置有两种情况:原来的位置;原位置2次幂的位置

    HashMap 1.8 哈希算法例图1

    ntable.length图a表示扩容前的key1key2两种key确定索引位置的示例,图b表示扩容后key1key2两种key确定索引位置的示例

    其中hash1key1对应的哈希与高位运算结果

    元素在重新计算hash之后,因为n变为2倍,那么n-1mask范围在高位多1bit(红色),因此新的index就会发生这样的变化:

    HashMap 1.8 哈希算法例图2

    1.8中,并不需要重新计算hash,只需要看看原来的hash值新增的那个bit1还是0就好了,是0的话索引没变,是1的话索引变成原索引+oldCap

    jdk1.8 HashMap扩容例图

    这样既省去了重新计算hash值的时间,而且同时,由于新增的1bit0还是1可以认为是随机的,因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket

    1.7中,扩容时,往新链表插入数据时,使用的是头插法,在产生hash冲突时,同一个index的元素,在新链表中会倒置。而1.8中,不会

    摘抄自美团点评技术团队 Java 8系列之重新认识HashMap


    1. 初始化newCap,newThr,并确定resize()是初始化还是元素存放数到达了阈值
    2. 开始遍历链表数组,判断index处是否有链表
    3. 遍历每个链表
    4. 判断链表内是不是只有一个键值对
    5. 判断链表是否转位了红黑树
    6. 进行键值对稀释操作,根据e.hash & oldCap,确定下标是低位还是高位
    final Node<K,V>[] resize() {
         // 临时oldTab数组
        Node<K,V>[] oldTab = table;
        
        // 旧的容量,初始化阶段,在HashMap没有放入键值对时为0
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        
        // 旧的阈值
        int oldThr = threshold;
        
        // 初始化新的容量,新的阈值
        int newCap, newThr = 0;
        
        // 步骤1 
        // 旧的容量大于0
        if (oldCap > 0) {
            // 判断是否已经到了上限,无需再扩容的容量
            // 若到了,就将阈值直接设置为最大容量
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            
            // 新的容量大于默认大小16,乘2后小于容量上限
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 阈值 2 倍
                newThr = oldThr << 1; 
        }
        
        // 此时容量oldCap = 0,链表数组table为null, 阈值大于0
        // 说明,是使用了`new HashMap(cap,thr)`,指定了容量和阈值
        else if (oldThr > 0) 
            // 将阈值设置为旧的阈值
            newCap = oldThr;
        
        // oldCap  == 0 , oldThr == 0,table为null,阈值也为0
        // 说明是使用了`new HashMap()`
        else {   
            // 将新的容量设置为默认大小16          
            newCap = DEFAULT_INITIAL_CAPACITY;
            
            // 默认阈值
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        
        // 此时对应的是`new HashMap(cap,thr)`,指定了容量和阈值这种情况
        if (newThr == 0) {
            // 计算阈值
            float ft = (float)newCap * loadFactor;
            
            // 设置新的阈值
            newThr = (newCap < MAXIMUM_CAPACITY 
            && 
            ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);
        }
        
        // 将获取的newThr赋给threshold,也就是更新HashMap的阈值
        threshold = newThr;
        
        // 建立临时链表数组
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        
        // 将新的链表数组引用指向table
        table = newTab;
        
        // 当oldTab不为null时,之前有存放过键值对
        // 遍历
        if (oldTab != null) {
            // 步骤2
            // 先遍历链表数组   
            for (int j = 0; j < oldCap; ++j) {
            
                // 临时键值对
                Node<K,V> e;
                
                // 步骤3
                // 若在 j 位置上,有链表
                if ((e = oldTab[j]) != null) {
                    // 将 j 位置的链表引用释放
                    oldTab[j] = null;
                    
                    // 步骤4
                    // e.next 为 null
                    // 链表内只有一个键值对
                    if (e.next == null)
                        // 根据新的容量进行 & 运算来计算 index
                        // 将 e 放在新计算的index位置
                        newTab[e.hash & (newCap - 1)] = e;
                    
                    // 步骤5
                    //  e 是否为 红黑树 
                    // 此时,说明hash冲突,链表上有超过个键值对,转换成了红黑树
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    
                    // 链表上有键值对,但还没超过8个
                    // 利用hash值来计算扩容后键值对所出链表的位置
                    // 1.8 的优化点:省去了一次重新计算index的过程
                    else { 
                    
                        // 步骤6
                        // 对于此时的 e 来说,扩容后,有两种情况:
                        // 放在原链表的原下标处,也就是低位,low位
                        // 放在扩容后的新下标处,也就是高位,high位
                        // high 位=  low位 + 原哈希桶容量
                         
                        // 低位链表的头结点、尾节点
                        Node<K,V> loHead = null, loTail = null;
                        
                        // 高位链表的头结点、尾节点
                        Node<K,V> hiHead = null, hiTail = null;
                        
                        // e.next 临时节点
                        Node<K,V> next;
                        do {
                            // 临时节点赋值
                            next = e.next;
                            
                            // e.hash & oldCap 计算 mask 范围
                            // 结果可以分为: 等于0 大于0
                            // 等于0,位于原链表原下标位置
                            // 大于0,位于扩容后新链表high位
                            if ((e.hash & oldCap) == 0) {
                                // 尾节点为 null ,说明链表之前没有存放过键值对
                                if (loTail == null)
                                    // 赋值头节点
                                    loHead = e;
                                else
                                    // 尾节点next 指为 e
                                    // 尾节点的next 暂时为自身
                                    loTail.next = e;
                                    
                                // 将e引用赋给尾节点
                                // 第一个元素插入时,由于只有一个节点
                                // 既是头节点又是尾节点
                                loTail = e;
                            }
                            
                            // 高位同上
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                       
                        // 低位节点存在
                        if (loTail != null) {
                             // 将尾节点 next 置 null
                            loTail.next = null;
                            
                            // 低位放在原index处
                            newTab[j] = loHead;
                        }
                        
                        // 高位同上
                        if (hiTail != null) {
                            hiTail.next = null;
                            
                            // 高位放在原 index+oldCap 处
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
    
    

    关于e.hash & oldCap

    在知乎看到了解释:

    jdk1.8 HashMap put时确定元素位置的方法与扩容拷贝元素确定位置的方式冲突?

    e.hash & oldCap

    摘自上面的知乎链接


    2.6 get()获取

    get()方法也是高频使用的方法

    public V get(Object key) {
        Node<K,V> e;
        
        // 先根据 key 计算 hash 值
        // 若不存在,就返回 null
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    

    getNode()

    1. 根据hashkey快速定位目标所在链表
    2. 判断头节点是否为获取目标。是,直接返回目标
    3. 查看链表中是否还有其他节点;没有直接返回 null
    4. 判断链表是否转为红黑树;是,就进行遍历红黑树查找操作
    5. 遍历链表,查找目标;找打就返回目标,否则直接返回 null
    6. 此时,说明HashMap 内没有查找的目标,返回 null
    final Node<K,V> getNode(int hash, Object key) {
        // 链表数组
        Node<K,V>[] tab; 
        
        // 头节点
        Node<K,V> first, e; 
        
        // table.length
        int n;
        
        // 临时健key
        K k;
        
        // 步骤1: 链表数组不为 null 并且能找打目标链表
        // 关键点在于 tab[(n - 1) & hash]),找到链表,确定头节点
        if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
                
            // 步骤2 :判断头节点是否就是查找的目标
            if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            
            // 步骤3: 链表中还有其他节点
            // 说明此时头节点不是获取目标
            if ((e = first.next) != null) {
                
                // 步骤4 : 是否为红黑树
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                
                // 步骤5 : 链表没有被转为红黑树
                // 遍历链表
                do {
                    // 判断是否为目标
                    if (e.hash == hash &&((k = e.key) == key 
                    || (key != null && key.equals(k))))
                    return e;
                } while ((e = e.next) != null);
            }
        }
        
        // 步骤6 : 返回 null
        return null;
    }
    

    获取方法的流程倒是比put()简单,关键点在于确定有效的头节点


    3. 最后

    红黑树不会,以后单独进行学习,不过目前不影响HashMap整体的流程学习

    引用较多,侵删

    有错误,请指出

    共勉 : )

    相关文章

      网友评论

      本文标题:Java——HashMap源码学习

      本文链接:https://www.haomeiwen.com/subject/sbredxtx.html