亲宝软件园·资讯

展开

Java中的数据结构-HashMap

吉良吉影为你点赞 人气:0

Java数据结构-HashMap

目录
  • Java数据结构-HashMap
    • 1. HashMap
      • 1.1 HashMap介绍
        • 1.1.1 HashMap介绍
        • 1.1.2 HashMap继承图
      • 1.2 HashMap 组成结构
        • 1.2.1 Hashmap底层数据结构
    • 2.HashMap源码解析
      • 2.1 HashMap属性源码解析
        • 2.1.1 HashMap中的静态常量
        • 2.1.2 HashMap中的属性
        • 2.1.3 HashMap中的存储结点
        • 2.1.4 Hash表
      • 2.2 HashMap数据的改变
        • 2.2.1 构造方法分析
        • 2.2.2 键值对的添加 put方法分析
        • 2.2.3 hash表table扩容 resize方法分析
        • 2.2.4 删除键值对 remove方法分析
        • 2.2.5 替换结点值 replace方法分析
        • 2.2.6 K 映射 compute方法
        • 2.2.7 K-V 映射 merge方法
        • 2.2.8 遍历消费 forEach方法
        • 2.2.9 清空 clear方法
      • 2.3 获取HashMap中的信息
        • 2.3.1 获取值 get方法分析
        • 2.3.2 检查是否包含key,value containsXX方法
        • 2.3.3 检查大小
      • 2.4 其它方法
        • 2.4.1 序列化与反序列化
    • 3. 总结
      • 3.1.1 HashMap中的其他类与方法

1. HashMap

1.1 HashMap介绍

1.1.1 HashMap介绍

  • HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry，有着key与value两个基本属性以及有其他的包含其他结点位置信息的属性
  • 通过HashMap我们可以存储键值对，并且可以在较短的时间复杂度内，

1.1.2 HashMap继承图

  • HashMap通过继承AbstractMap实现了Map接口,且本身也实现了Map接口

    • 在接口实现关系上来看为多余操作

    • 但有一点要注意，在使用反射获取实现接口时，如果不是显示实现某接口而是通过继承来实现该接口，则不会获取该接口类型，这一点在使用动态代理时要注意

      HashMap.class.getInterfaces()//[interface java.util.Map, interface java.lang.Cloneable, interface java.io.Serializable]
      • HashMap 通过显示实现Map接口，从而在通过反射时能够获取到Map接口

  • HashMap实现了Serializable接口，可以通过java.io.ObjectStream进行序列化

  • HashMap实现了Cloneable接口，实现了浅拷贝，通过以下代码可以证实：

    • HashMap map = new HashMap();
map.put(1, "first");
HashMap copiedMap = (HashMap) map.clone();
System.out.println(copiedMap.get(1)==map.get(1));//true
copiedMap.put(2, "second");
System.out.println(map);//{1=first}

1.2 HashMap 组成结构

1.2.1 Hashmap底层数据结构

  • HashMap底层采用数组+链表/红黑树的数据结构

（1）哈希表

  • 哈希表也成为散列表，它是根据关键字经过hash()函数处理，将值映射到哈希表上的某一个位置，以该位置作为关键字的存储位置，无论存在哪，只需要进行一次hash计算，便可以找到该位置，整个查找过程时间复杂度为\(O(1)\)

  • HashMap 使用数组作为哈希表，来存储Key的hash()信息

（2）链表

  • 因为hash()函数是将key值映射到有限的空间中，如果hash()函数碰撞性设计的不完善，或者哈希表存储的元素过多，必然会导致不同元素的hash值相同,即位置冲突，此时我们采用的方式一般有：

    • 使用链表，存储不同元素但hash()函数处理值相同的元素，哈希表对应位置存储该链表的头结点
    • 扩大哈希表数组的大小，重新设计hash()函数映射关系使元素分布地更加均匀，降低碰撞几率

（3）红黑树

  • 红黑树为一颗平衡二叉树

  • 当元素越来越多时，hash碰撞也会越来越严重，链表的长度会变得很大，此时如果我们想要查找该链表的的某一个元素，其时间复杂度为\(O(n)\)，必须采用一个阈值，当链表的长度达到该阈值时，便应该将链表转化为一颗红黑树，从而将时间复杂度从\(O(n)\)降低为\(O(logn)\),从而改善Hash表的查找性能

2.HashMap源码解析

2.1 HashMap属性源码解析

2.1.1 HashMap中的静态常量

（1）缺省table长度

  • static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;//为16

（2）table长度的最大值

  • static final int MAXIMUM_CAPACITY = 1 << 30;

（3）缺省负载因子

  • static final float DEFAULT_LOAD_FACTOR = 0.75f;
    • 负载因子 = 含有元素的桶个数/ 桶的总个数
    • 实际上在HashMap中是传入负载因子，来确定含有元素的桶个数，而这个数值为扩容阈值
      • 可以这样理解，负载因子的作用就是为了让空桶保持不少于一个比例，降低hash碰撞几率

（4）树化阈值-链表长度

  • static final int TREEIFY_THRESHOLD = 8;
    • 链表转换为红黑树的条件之一为桶的链表长度达到8及以上

（5）树化阈值-HashMap元素个数

  • static final int MIN_TREEIFY_CAPACITY = 64;
    • 链表转换为红黑树的条件之二为HashMap中的元素达到64及以上

（6）树降为链表的阈值

  • static final int UNTREEIFY_THRESHOLD = 6;
    • 当该桶的链表树的结点数目低于该值时便会转化为链表,以便避免不必要的平衡修复运算

2.1.2 HashMap中的属性

（1）HashMap元素个数

  • transient int size;

（2）Hash表结构修改次数

  • transient int modCount;
    • 结构修改：插入或删除元素等操作，改变了HashMap的结构（插入相同元素替换掉原来元素因为并没有改变结构，所以不算修改）

（3）扩容阈值

  • int threshold;
    • 扩容阈值，当table中的元素达到阈值时，触发扩容
    • threshold = loadFactor * capacity

（4）负载因子

  • final float loadFactor;

2.1.3 HashMap中的存储结点

（1）静态结点类源码

  • static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    . . . 构造方法
        . . . getter&&setter

    //重写的hash()方法    
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
    
    //重写的equals方法
    public final boolean equals(Object o) {
        	//如果为该对象
            if (o == this)
              return true;
        	//如果是Map.Entry类型
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                //如键，值equals方法都为真
                if (Objects.equals(key, e.getKey()) &&
                        Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
    }
    
    ...toString(){...}
}

  • 结点Node类为实现了Map.Entry接口的一个静态内部类，主要包含：

    • hash计算值：后面构造时用以保存hashcode,避免每次重新计算
    • key：键
    • value：值
    • next:指向下一个结点的引用：如果发生哈希碰撞，使用链式结构存储hash值相同的键值对

  • 重写的hash()方法将key和value经Objects.hashCode(Object o)处理后进行与操作，使得hash()函数映射更加随机均匀

  • 重写的equals方法中只有传入结点为自身结点或者key与value调用equals方法比较都为真时，结果才为真（主要用于后面查找元素时的比较）

2.1.4 Hash表

（1）Hash表源码

  • Hash表定义源码:

    transient Node<K,V>[] table;

  • 为了能够通过确定计算的hashcod找到桶的位置，HashMap中底层采用Node<K,V>结点类型数组作为桶

  • transient修饰在序列化时会被跳过

（2）确定桶的位置

  • 当put一个结点时，通过以下算法来确定结点应该位于哪个桶
    • index = (table.length - 1) & node.hash，也就是说位置完全取决于node.hash的后几位(table.length-1的二进制位数)

（3）长度的确定

  • hash表长度计算方法源码:

    static final int tableSizeFor(int cap) {
    int n = cap;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

    • 该方法的作用是，当初始化时，通过传入capacity返回一个大于等于当前值cap的一个数字，并且这个数字一定是2的次方数

    • 该方法不断通过右移然后进行‘或’操作，可以将传入的cap中的首非0位之后的0位填满，变为0..11...1的形式，即\(2^{n的二进制位数+1}-1\)

      • 例：

        cap = 10
n = 10 - 1 => 9
0b1001 | 0b0100 => 0b1101
0b1101 | 0b0011 => 0b1111
0b1111 | 0b0000 => 0b1111 = 15 
return 15 + 1 = 16

        cap = 16
n = 16;
0b10000 | 0b01000 =>0b11000
0b11000 | 0b00110 =>0b11110
0b11110 | 0b00001 =>0b11111
return 31 + 1 = 32;

  • Hash表的长度必须为2的整数次幂

    • 因为当数组的长度为2的整数次幂时，table.length-1的二进制位(11...1)（例如15:1111,7:111）
    • 假设当前长度为16，其table.length-1 = 1111b,如果进来两个元素的hash分别是(。。。0111 b)与(。。。0001 b)分别进行与操作，其位置结果不同；
    • 如果当前长度为10，其table.length-1 = 1001b，上面两个元素分别进行与操作结果相同（即该长度只需要传入元素的hashcode的最低字节的最高位与最低位相同即可（只比较了两位））必然导致分配不均匀，而使用2的整数次幂-1可以保证进行与操作时，只有hashcode的位比较全部相同才会相同，提高了分散程度

（4）hash值的计算：hash(K key)

  • hash扰动函数源码:(实际上产生的就是Node.hash，用于后面Node对象的构造)

    static final int hash(Object key) {
    int h;//h=0
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

    • 如果key为null则hash值为0，位置计算结果也为0（从putVal方法的第一种情况可以看出），会替换掉table[0]桶位的key为null的元素

      • 注意：table[0]可能存储着其他计算出的hash值为0的元素，并不是只有一个(null:value)结点

    • 当table长度比较小时，从前面位置算法index = (table.length-1)|node.hash()可以看出，如果不经处理，计算的index只取决于结点的hash的后几位(table.length-1的二进制长度)，这样会使不同元素的位置结果相同概率大大增加

    • h>>16的结果的高16位全为0，(h = key.hashCode()) ^ (h >>> 16)就可以让结果hash的高16位为key.hashCode()的高16位，使得高16位也参与hash值的计算，增加低16位的随机性

      • 例：

        h = key.hashCode() =  0b 0010 0101 1010 1100 0011 1111 0010 1110
0b 0010 0101 1010 1100 _ 0011 1111 0010 1110
^
0b 0000 0000 0000 0000 _ 0010 0101 1010 1100 (h>>>16)
=> 0010 0101 1010 1100 _ 0001 1010 1000 0010

    hash扰动原理参考

2.2 HashMap数据的改变

2.2.1 构造方法分析

（1）HashMap(int initialCapacity, float loadFactor)

  • public HashMap(int initialCapacity, float loadFactor) {
    //前面都是校验传入参数是否合法，不合法抛出 IllegalArgumentException
    //initialCapacity必须是大于0 ，最大值为 MAX_CAPACITY
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " 
														+initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;

    //loadFactor必须大于0且不是NaN
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " 																		+loadFactor);
    this.loadFactor = loadFactor;
    //HashMap的扩容阈值通过以下方法取得
    this.threshold = tableSizeFor(initialCapacity);
}

（2）其它构造方法

  • 其它构造方法源码

    public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // 0.75
    //现在的扩容阈值thershold = 0
}

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    //现在的扩容阈值thershold = 0
    //调用putMapEntries，添加键值对s
    putMapEntries(m, false);
}
    • 其它构造方法的属性处了传入参数属性其它皆为默认属性

  • putMapEntries方法源码：

    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    //获取键值对map长度
    int s = m.size();
    if (s > 0) {
        //如果table没有初始化，先计算一系列属性再初始化
        if (table == null) { // pre-size
            //计算初始的table长度
            float ft = ((float)s / loadFactor) + 1.0F;
            //选取table长度与最大长度的最小值
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        //如果map的长度大于扩容阈值，扩容table
        else if (s > threshold)
            resize();
        
       	//遍历调用put方法添加键值对
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}
    • 该方法实际上包含了HashMap属性值的初始化操作与可能的扩容操作，当操作完成后，遍历传入的m.entrySet(),依次插入键值对

2.2.2 键值对的添加 put方法分析

（1）put(K key, V value)

  • 源码:

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

    套娃方法，该方法首先计算调用hash()方法计算hash值(并不是key.hashCode()),调用putVal以替换的方式进行结点插入操作,返回之前结点的value

（2）putIfAbsent

  • 源码：

    @Override
public V putIfAbsent(K key, V value) {
    return putVal(hash(key), key, value, true, true);
}

    套娃方法，计算hash值，调用putVal以非替换的方式进行结点插入操作，返回之前结点的value

（3）putAll

  • 源码：

    public void putAll(Map<? extends K, ? extends V> m) {
    putMapEntries(m, true);
}

    套娃方法，调用putMapEntries(m, true)实现添加传入的map的所有的键值对

（3）putVal

  • putVal源码

    /**
* Implements Map.put and related methods.
*
* @param hash hash for key -key的hash值
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value -true:如果该元素已经存在与HashMap中就不操作了
* @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) {
    //tab：引用当前hashMap的散列表
    //p：表示当前散列表的元素
    //n：表示散列表数组的长度
    //i：表示路由寻址结果
    Node<K,V>[] tab; Node<K,V> p; int n, i;

    //延迟初始化逻辑，第一次调用putVal时会初始化hashMap对象中的最耗费内存的散列表
    //这样会防止new出来HashMap对象之后却不存数据，导致空间浪费的情况
    if ((tab = table) == null || (n = tab.length) == 0)//此处进行tab与n的赋值
        n = (tab = resize()).length;

    //情形1：寻址找到的桶位，赋值给p,如果p刚好是 null，这个时候，直接将当前k-v=>node 扔进去就可以了
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);

    else {
        //e：临时的Node元素，不为null的话，找到了一个与当前要插入的key-value一致的key的元素
        //k：表示临时的一个key
        Node<K,V> e; K k;

        //情形2：表示桶位中的该元素，与你当前插入的元素的key完全一致，表示后续需要进行替换操作
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
		
        //情形3：如果改桶为存储的结点与插入结点的hash不同或者key不一致吗，且为红黑树的树根结点，在需要插入结点到红黑树中
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        
        //情形4：链表的情况，而且链表的头元素与我们要插入的key不一致。
        else {
            for (int binCount = 0; ; ++binCount) {
                //条件成立的话，说明迭代到最后一个元素了，也没找到一个与你要插入的key一致的node,说明需要加入到当前链表的末尾
                if ((e = p.next) == null) {
                    //链表末尾添加新的结点
                    p.next = newNode(hash, key, value, null);
                    //条件成立的话，说明当前链表的长度，达到树化标准了，需要进行树化
                    //TREEIFY_THRESHOLD - 1 = 7
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        //树化操作
                        treeifyBin(tab, hash);
                    break;
                }
                //条件成立的话，说明找到了相同key的node元素，需要进行替换操作
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }

        //e不等于null，条件成立说明，找到了一个与你插入元素key完全一致的数据，需要进行替换
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            //返回旧元素
            return oldValue;
        }
    }

    //modCount：表示散列表结构被修改的次数，替换Node元素的value不计数
    ++modCount;
    //插入新元素，size自增，如果自增后的值大于扩容阈值，则触发扩容。
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

  • 整个方法的流程：

  • 传入的参数

    • int hash：上层调用者经过hash扰动后的hash值
    • K key,V vey：键，值
    • boolean onlyIfAbsent：如果为true,则对相同的元素不进行替换处理
    • boolean evict：没用，后面并没有做什么工作

  • 方法执行逻辑：

    1. 如果table为null或者table长度为0，则进行扩容方法，并取得表长
    2. 如果经过位置计算的到的table相应位置的元素p为null
      • new新的结点并赋值到table对应位置
    3. 否则：先创建临时Node e,K k
      1. 如果经过位置计算得到的元素p.hash值与传入的hash值相同，并且p.key==key或者说key通过equals方法比较为true
        • 保存p的引用(e=p)，下一步进行结点的值的替换
      2. 否则，如果：p为红黑树结点
        • 调用红黑树的结点插入操作
      3. 否则：该情形为链表,从头结点p开始遍历,binCount=0,之后每次循环+1
        1. 如果：已经到链表末尾((e=p.next)==null,e为当前结点p的下一个结点)，说明并没有找到该元素，new 新的结点插入到链表尾部(p.next = new Node(...))
          1. 遍历的长度(该链表长度与树化阈值比较(binCount >= TREEIFY_THRESHOLD - 1))，即当binCount到达7时，即插入操作后链表长度为8时（binCount从0开始计数，而p开始就对应第一个结点），调用树化方法
          2. break
        2. 否则：找到链表中的元素e.hash值与传入的hash值相同，并且e.key==key或者说equals方法比较为true
          1. break
        3. 保存结点p = e
    4. 如果：e不为null,说明找到了一个key一致的元素，需要将该结点e的value进行替换
      1. 保存旧的oldvalue = e.value
      2. 如果!onlyIfAbsent || oldValue == null
        • 将e.value = value进行替换
      3. afterNodeAccess(e);
      4. return oldvalue;(源码中并没有方法体{没有内容}，在这里没用)
    5. HashMap this.modCount++ 修改次数(执行到这一步说明没有找到对应key的元素，从而进行了插入操作)
    6. 如果++size>thershold,超过扩容阈值，则执行扩容方法
    7. afterNodeInsertion(evict);(源码中并没有方法体{没有内容}，在这里没用)
    8. return null

2.2.3 hash表table扩容 resize方法分析

（1）扩容原因

  • 由于在hash表位置的计算中index = (table.length-1)&node.hash，位置的计算永远不会超过hash表的长度，大量的元素会发生哈希碰撞，降低查找效率，所以当达到饱和条件，即到达含有元素的桶达到thorshold时，需要进行扩容操作

（2）核心resize方法

  • resize方法源码：

    /**
* @return the table
*/
final Node<K,V>[] resize() {
    
    //oldTab：引用扩容前的哈希表
    Node<K,V>[] oldTab = table;
    
    //oldCap：表示扩容之前table数组的长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    
    //oldThr：表示扩容之前的扩容阈值，触发本次扩容的阈值
    int oldThr = threshold;
    
    //newCap：扩容之后table数组的大小
    //newThr：扩容之后，下次再次触发扩容的条件
    int newCap, newThr = 0;

    //条件如果成立说明 hashMap中的散列表已经初始化过了，这是一次正常扩容
    if (oldCap > 0) {
        
        //扩容之前的table数组大小已经达到 最大阈值后，则不扩容，且设置扩容条件为 int 最大值，返回原hashtable
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }

        //oldCap左移一位实现数值翻倍，并且赋值给newCap， newCap 小于数组最大值限制 且 扩容之前的阈值 >= 16
        //这种情况下，则 下一次扩容的阈值 等于当前阈值翻倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY) \\
            newThr = oldThr << 1; // double threshold
    }

    //oldCap == 0,说明hashMap中的散列表是null
    //1.new HashMap(initCap, loadFactor);
    //2.new HashMap(initCap);
    //3.new HashMap(map); 并且这个map有数据
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;

    //oldCap == 0，oldThr == 0
    //new HashMap();
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;//16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//12
    }

    //newThr为零时，通过newCap和loadFactor计算出一个newThr
    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;

    //说明，hashMap本次扩容之前，table不为null
    if (oldTab != null) {

        for (int j = 0; j < oldCap; ++j) {
            //当前node节点
            Node<K,V> e;
            //说明当前桶位中有数据，但是数据具体是 单个数据，还是链表 还是 红黑树 并不知道
            if ((e = oldTab[j]) != null) {
                //方便JVM GC时回收内存
                oldTab[j] = null;

                //第一种情况：当前桶位只有一个元素，从未发生过碰撞，这情况 直接计算出当前元素应存放在 新数组中的位置，然后
                //扔进去就可以了
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;

                //第二种情况：当前节点已经树化，本期先不讲，下一期讲，红黑树。QQ群：865-373-238
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    //第三种情况：桶位已经形成链表

                    //低位链表：存放在扩容之后的数组的下标位置，与当前数组的下标位置一致。
                    Node<K,V> loHead = null, loTail = null;
                    //高位链表：存放在扩容之后的数组的下表位置为 当前数组下标位置 + 扩容之前数组的长度
                    Node<K,V> hiHead = null, hiTail = null;

                    Node<K,V> next;
                    do {
                        next = e.next;
                        //hash-> .... 1 1111
                        //hash-> .... 0 1111
                        // 0b 10000

                        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) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }

                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }

                }
            }
        }



    }
    return newTab;
}

  • 确定新的表容量以及新的扩容阈值逻辑：

    1. 创建引用变量
      • oldTab = this.table进行引用赋值
      • 旧的表容量oldCap = 表的长度，如果表为null的话,oldCap = 0
      • 旧的扩容阈值oldThr = this.thershold
      • 创建保存新的表容量与扩容阈值的变量newCap,newThr
    2. 如果：oldCap>0，说明HashMap之前已经初始化过了，这是正常扩容
      1. 如果：旧的表容量已经达到MAXIMUN_CAPCITY=1<<30，则将扩容阈值设为整数最大值，返回原table（已经无法扩容了）
      2. 否则，如果：让newCap = oldCap<<1，如果newCap小于MAXIMUN_CAPCITY并且旧的负载oldCap大于默认表容量16，则新的扩容阈值等于旧的扩容阈值翻倍
    3. 否则，说明oldCp=0如果：旧的扩容阈值oldThr>0(构造HashMap时除了无参默认方法其他都直接或间接设置了thorshold),让新的表容量等于旧的扩容阈值newCap=oldThr
    4. 否则，此时情况为oldCap == 0，oldThr == 0(使用无参构造方法)，让newCap = 默认表容量16，newThr = 默认负载因子*默认表容量
    5. 如果：newThr = 0,ft = newCap负载因子
      1. 如果newCap<小于整数最大值 并且 ft<最大表容量？ft取整：整数的最大值
    6. 以上代码已经计算出来本次数组应该改为多大，下次扩容阈值应设为多大，接下来就开始创建新的数组，并把旧元素赋给新数组

  • 开始将旧表元素分配到新的表上

    1. 使用newCap创建新的数组newTab

    2. 如果：oldTab!=null，说明扩容之前数组就已经被创建了，此时开始遍历oldTab.for(j = 0;j<oldCap;++j):

      1. 如果：(Node e = oldTab[j]) != null，即当前节点不为空：

      2. 令oldTab[j] = null 方便GC回收旧的数组

      3. 如果：e.next == null（即当前桶位只有一个元素），则让newTab[e.hash & (newCap - 1)] = e;（利用新的表容量的位置算法，让e赋值到新表的相应位置）

      4. 如果：e为树的根结点，调用((TreeNode<K,V>)e).split(this, newTab, j, oldCap);去进行树中结点在新表的分配

      5. 如果：e为链表的头结点，创建4个链表结点loHead,loTail,hiHead,hiTail

        • loxxx：低位链表：存放在扩容之后的数组的下标位置与当前数组的下标位置一致
        • hixxx：高位链表：存放在扩容之后的数组的下表位置为 (当前数组下标位置 + 扩容之前数组的长度)
        • 这里以原先表容量为16，扩容后容量为32为例
          • 由于16 = (10000)b ,32 = (100000)b
          • 有依据原先的路由算法：index = e.hash & (15=1111b),也就是说是因为该链表的hash后4位相同，所以才分配到该链表上
          • 然后当新的表容量为32时，index = hash&(31 = 11111b),也就是说现在在新表上的位置取决于e.hash的后5位
          • 此时需要计算每个链表的与oldCap的与操作结果，其结果取决于e.hash的倒数第5位(与newCap-1进行&操作时，newCap-1前面都为0，又因为该链表的后四位都相同，所以就分配而言只取决于第5位):
            • e.hash = ...1 xxxx ->分配到新的数组位置为：15+原先位置
            • e.hash = ...0 xxxx ->分配到新的数组位置为：原先位置
          • 该方法将原本的一条链表可以分配到两个桶中，以减小链表长度

      6. 开始循环：创建结点next = e.next

        1. 如果：(e.hash & oldCap) == 0
          • 将e添加到lo链表中
        2. 否则：
          • 将e添加到hi链表中

      7. 最后将两条链表的尾结点置null

        将newTab[j] = loHead，newTab[j+oldCap] = hiHead

        元素的分配，扩容完成！！！

2.2.4 删除键值对 remove方法分析

（1）remove(K)方法

  • 源码

    public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

    套娃方法，调用removeNode方法，获取其返回的被删除结点，返回该结点的value

（2）remove(K,V)方法

  • 源码

    public boolean remove(Object key, Object value) {
    return removeNode(hash(key), key, value, true, true) != null;
}

    套娃方法，调用removeNode方法，返回是否删除成功

（3）核心removeNode方法

  • 源码

     /**
     * Implements Map.remove and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to match if matchValue, else ignored
     * @param matchValue if true only remove if value is equal
     * @param movable if false do not move other nodes while removing
     * @return the node, or null if none
     */
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    //tab：引用当前hashMap中的散列表
    //p：当前node元素
    //n：表示散列表数组长度
    //index：表示寻址结果
    Node<K,V>[] tab; Node<K,V> p; int n, index;

    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        //说明路由的桶位是有数据的，需要进行查找操作，并且删除

        //node：查找到的结果
        //e：当前Node的下一个元素
        Node<K,V> node = null, e; K k; V v;

        //第一种情况：当前桶位中的元素 即为 你要删除的元素
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;


        else if ((e = p.next) != null) {
            //说明，当前桶位 要么是 链表 要么 是红黑树

            if (p instanceof TreeNode)//判断当前桶位是否升级为 红黑树了
                //第二种情况
                //红黑树查找操作，下一期再说
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                //第三种情况
                //链表的情况
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }


        //判断node不为空的话，说明按照key查找到需要删除的数据了
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {

            //第一种情况：node是树节点，说明需要进行树节点移除操作
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);

            //第二种情况：桶位元素即为查找结果，则将该元素的下一个元素放至桶位中
            else if (node == p)
                tab[index] = node.next;

            else
                //第三种情况：将当前元素p的下一个元素 设置成 要删除元素的 下一个元素。
                p.next = node.next;

            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

  • 方法逻辑：

    • 前面部分与getNode方法相似，目的是查找要删除的Node结点是否存在，如果不存在或者HashTable未被初始化，则直接返回null
    • 如果：查找到的node不为空，说明查找到了
      • 如果：该结点为树节点，调用removeTreeNode(this, tab, movable)方法，删除并保存树的结点
      • 否则，如果：该结点在桶中，直接让下一个结点放入桶中，保存之前结点
      • 否则：将链表的结点删除，即将前一结点的next指向node.next
    • 修改次数+1 ，size-1,返回删除结点
    • 返回保存的结点

2.2.5 替换结点值 replace方法分析

（1）replace(K,V)

  • 源码：

    @Override
public V replace(K key, V value) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) != null) {
        V oldValue = e.value;
        e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
    return null;
}

    调用getNode方法通过比较key来找到需要替换的结点，将value赋给该结点,返回旧value；如果没找到返回null

（2）replace(K key, V oldValue, V newValue)

  • 源码：

    @Override
public boolean replace(K key, V oldValue, V newValue) {
    Node<K,V> e; V v;
    if ((e = getNode(hash(key), key)) != null &&
        ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
        e.value = newValue;
        afterNodeAccess(e);
        return true;
    }
    return false;
}

    调用getNode方法通过比较key与value来找到需要替换的结点，将newValue赋给该结点,返回true,如果没找到返回false

2.2.6 K 映射 compute方法

（1）compute方法

  • 该方法实现了通过传入函数式接口，来对传入的key值对应的结点进行操作，如果找不到key对应的结点，会进行插入一个新的结点Node(key,mappingFunction.apply(key,value)),并可能会重新排列部分数据结构;如果映射value结果为null,则会删除该结点

  • 源码：

    @Override
public V compute(K key,
                 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
    if (remappingFunction == null)
        throw new NullPointerException();
    int hash = hash(key);
    Node<K,V>[] tab; Node<K,V> first; int n, i;
    int binCount = 0;
    TreeNode<K,V> t = null;
    Node<K,V> old = null;
    if (size > threshold || (tab = table) == null ||
        (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((first = tab[i = (n - 1) & hash]) != null) {
        if (first instanceof TreeNode)
            old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
        else {
            Node<K,V> e = first; K k;
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))) {
                    old = e;
                    break;
                }
                ++binCount;
            } while ((e = e.next) != null);
        }
    }
    V oldValue = (old == null) ? null : old.value;
    V v = remappingFunction.apply(key, oldValue);
    if (old != null) {
        if (v != null) {
            old.value = v;
            afterNodeAccess(old);
        }
        else
            removeNode(hash, key, null, false, true);
    }
    else if (v != null) {
        if (t != null)
            t.putTreeVal(this, tab, hash, key, v);
        else {
            tab[i] = newNode(hash, key, v, first);
            if (binCount >= TREEIFY_THRESHOLD - 1)
                treeifyBin(tab, hash);
        }
        ++modCount;
        ++size;
        afterNodeInsertion(true);
    }
    return v;
}

  • 方法逻辑

    • 前面部分与getNode方法相似，只不过在最前面加入了对传入的BiFunction实例的控制判断，如果为空，则抛出异常
    • 之后去寻找key值对应的结点old，如果找到了且value不为空,利用remappingFunction.apply(key, oldValue)进行映射操作，获得新的value v
    • 如果：old不为空且old结点的value值不为空，将新的v赋给old.value，实现value的映射操作
      • 如果：v不为null
        • 将old.value 替换为 v
      • 否则：v为null,调用removeNode(hash, key, null, false, true)方法删除key,value对应结点
    • 否则：old为null,证明没找到该结点，调用相关方法添加新的结点
      • 如果：该结点是一个树的根结点，则调用 t.putTreeVal(this, tab, hash, key, v)实现作为新结点的插入
      • 否则：将该桶位元素tab[i]设为新结点，插入完成之后在进行树化判断，并决定是否树化
      • 修改数据属性
    • 返回映射后的结果 v

  • 使用方法

    HashMap<Integer,String> hp = new HashMap<Integer,String>();
hp.put(1,"A");
hp.put(2,"B");
hp.put(3,"C")
hp.compute(2,(k,v)->v+"A")//将key为2的元素的value修改为value+"A"
hp ==> {1=A, 2=BA, 3=C}
hp.put(10,"A")
hp ==> {1=A, 2=BA, 3=C, 10=A}
hp.compute(10,(k,v)->null)//null
hp ==> {1=A, 2=BA, 3=C}

（2）computeIfAbsent方法

  • public V computeIfAbsent(K key,Function<? super K, ? extends V> mappingFunction) {...}

  • 该方法如果没有检测到该key所对应结点，会添加一个新的结点Node(key,mappingFunction.apply(key,value))到HashMap中,如果存在则不进行此操作,并返回null;如果映射value结果为null,则会删除该结点

  • 使用方法

    承接上处
hp.computeIfAbsent(2,(v)->"new value")//返回BA
hp ==> {1=A, 2=BA, 3=C}
jshell> hp.computeIfAbsent(4,(v)->"new value")//返回new value
hp ==> {1=A, 2=BA, 3=C, 4=new value}

（3）computeIfPresent方法

  • public V computeIfPresent(K key,BiFunction<? super K, ? super V, ? extends V> remappingFunction) {...}

  • 该方法如果检测到该key所对应结点，会添加一个新的结点Node(key,mappingFunction.apply(key,value))到HashMap中,如果不存在则不进行此操作，并返回null;如果映射value结果为null,则会删除该结点

  • 使用方法

    承接上处
hp.computeIfPresent(5,(k,v)->"new value ：5")//返回null
hp.computeIfPresent(4,(k,v)->"new value ：4")//返回"new value ：4"
hp ==> {1=A, 2=BA, 3=C, 4=new value ：4}

2.2.7 K-V 映射 merge方法

（1）merge方法

  • 该方法与compute类似，只不过以key与value来寻找相应结点,找到则覆盖，找不到则插入新的结点Node(key,value)

  • 如果oldValue为null或者节点不存在，则直接取value参数(不是映射后的value)作为节点的value值

  • 同样的，作为特殊情况，如果计算出来的value值为null，删除节点

    public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {...与compute类似...}

  • 使用方法

    HashMap<Integer,String> hp = new HashMap();
hp.put(1,"A");
hp.merge(1,"A",(k,v)->"new value");//new value     hp ==> {1=new value}

hp.merge(1,"B",(k,v)->"new value:1")//new value:1  hp ==> {1=new value:1}

hp.merge(2,"B",(k,v)->"new value:B")//B            hp ==> {1=new value:C, 2=B}

hp.put(null,"我是null")//映射后的默认值               hp ==> {null=映射后的默认值, 1=new value:C, 2=B} 

hp.merge(100,"100的默认值",(k,v)->"映射后的100的默认值") //100的默认值  hp ==> {null=映射后的默认值, 1=new value:C, 2=B, 100=100的默认值}

2.2.8 遍历消费 forEach方法

（1）forEach方法

  • 源码

    public void forEach(BiConsumer<? super K, ? super V> action) {
    Node<K,V>[] tab;
    if (action == null)
        throw new NullPointerException();
    。。。之后就是遍历table，对结点进行消费action.accpet(e.key,e.value)
}

2.2.9 清空 clear方法

（1）clear方法

  • 源码

    public void clear() {
    Node<K,V>[] tab;
    modCount++;
    if ((tab = table) != null && size > 0) {
        size = 0;
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
    }
}

    判断table是否初始化，如果不为空，每个位置置为null,等待JVM回收各个结点即可

2.3 获取HashMap中的信息

2.3.1 获取值 get方法分析

（1）get方法

  • 源码：

    public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

    套娃方法,先用hash函数获取key的hash值，getNode去寻找Node结点，如果找到则返回value值，没找到则返回null

（2）getOrDefault方法

  • 源码：

    public V getOrDefault(Object key, V defaultValue) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}

    套娃方法，和get方法类似，只不过如果找不到结点则返回传入的默认值

（2）核心getNode方法

  • 源码：

    /**
* Implements Map.get and related methods.
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
    //tab：引用当前hashMap的散列表
    //first：桶位中的头元素
    //e：临时node元素
    //n：table数组长度
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;

    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //第一种情况：定位出来的桶位元素 即为咱们要get的数据
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;

        //说明当前桶位不止一个元素，可能 是链表 也可能是 红黑树
        if ((e = first.next) != null) {
            //第二种情况：桶位升级成了 红黑树
            if (first instanceof TreeNode)//下一期说
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            //第三种情况：桶位形成链表
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;

            } while ((e = e.next) != null);
        }
    }
    return null;
}

  • 方法逻辑

    • 创建几个引用tab表,头结点first,临时结点e,表长度n
    • 如果：tab不为空 并且 表长大于0 并且 通过路由算法得出的结点first = tab[(n - 1) & hash]不为空，则：
      • 如果得到的first即为自己所寻找的元素的key，返回first
      • 如果：frist不是所寻找的元素的key,first.next不为空，说明可能存在与之后的链式结构中
        • 如果：first是红黑树根结点，调用getTreeNode(hash, key)寻找树种符合条件的结点，并返回结果
        • 否则：frist为链表头结点，遍历链表，去比较，获得对应结点，并返回结果
    • 如果：以上都没找到，返回null

2.3.2 检查是否包含key,value containsXX方法

（1）containsKey(K)

  • 源码：

    public boolean containsKey(Object key) {
       return getNode(hash(key), key) != null;
}

    套娃方法，调用getNode方法查找，返回是否查找到结点

（2）containsValue(V)

  • 源码：

    public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

  • 方法逻辑

    • 遍历table，对于每个桶:
      • 遍历每个桶的链式结构，比较Node.value与传入value
        • 如果：找到对应value,返回true
    • 没找到对应value,返回false

2.3.3 检查大小

（1）isEmpty方法

  • return size == 0,判断是否为空

（2）size方法

  • return this.size，返回元素个数

2.4 其它方法

2.4.1 序列化与反序列化

（1）HashMap中的序列化方法介绍

  • 为了确保JVM的跨平台，防止因机器的不同序列化与反序列化的结果可能并不是正常构建的结果，HashMap中的数据属性很多都用transient修饰，序列化时会被跳过，所以需要重写方法来自定义序列化的数据的写入与读取

    transient Node<K,V>[] table;

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

transient int size;

transient int modCount;

  • HashMap中还为了方便，提供了序列化与反序列化方法(这里就不贴源码了，可以去jdk中看)：

    • final private wirteObject(ObjectOutputStream)
      • HashMap序列化的时候不会将保存数据的数组序列化，而是将元素个数以及每个元素的Key和Value都进行序列化
    • final private readObject(ObjectOutputStream)
      • 在反序列化的时候，重新计算Key和Value的位置，重新填充一个数组，重新构建HashMap

（2）方法作用

  • 上述方法作用为当进行序列化与反序列化时，会判断被序列化的对象是否自己重写了writeObject方法，如果重写了，就会调用被序列化对象自己的writeObject方法，如果没有重写，才会调用默认的序列化方法
  • final类型也保证了如果有类继承HashMap时，

HashMap序列化与反序列化参考

3. 总结

3.1.1 HashMap中的其他类与方法

  • HashMap中为了功能的增强与扩展还定义了许多类，比如红黑树结点TreeNode,对于值的遍历Values类与key的遍历Keys，EntrySet等以及各种迭代器的设计，它们各自都有自己的数据操作方法，篇幅原因，就不一一赘述了
  • 如果有错误，还请指出

b站HashMap源码讲解参考

加载全部内容
相关教程
猜你喜欢
用户评论