← 返回学习路线

SYSTEM

Map

Java基础Mapsystem
src/content/notes/system/Map.md

Map

概述

Collection 是单值集合体系,Map集合是一种双列集合,每个元素包含两个值。

Map集合的每个元素的格式:key=value(键值对元素),Map集合也被称为键值对集合

Map集合的完整格式:{key1=value1, key2=value2, key3=value3, ...}

Map集合的体系:
        Map<K , V>(接口,Map集合的祖宗类)
       /                      \
      TreeMap<K , V>           HashMap<K , V>(实现类,经典的,用的最多)
                                 \
                                  LinkedHashMap<K, V>(实现类)

Map 集合的特点:

  1. Map 集合的特点都是由键决定的
  2. Map 集合的键是无序,不重复的,无索引的(Set)
  3. Map 集合的值无要求(List)
  4. Map 集合的键值对都可以为 null
  5. Map 集合后面重复的键对应元素会覆盖前面的元素

HashMap:元素按照键是无序,不重复,无索引,值不做要求

LinkedHashMap:元素按照键是有序,不重复,无索引,值不做要求


常用API

Map 集合的常用 API

  • public V put(K key, V value):把指定的键与值添加到 Map 集合中,重复的键会覆盖前面的值元素
  • public V remove(Object key):把指定的键对应的键值对元素在集合中删除,返回被删除元素的值
  • public V get(Object key):根据指定的键,在 Map 集合中获取对应的值
  • public Set<K> keySet():获取 Map 集合中所有的键,存储到 Set 集合中
  • public Collection<V> values():获取全部值的集合,存储到 Collection 集合
  • public Set<Map.Entry<K,V>> entrySet():获取Map集合中所有的键值对对象的集合
  • public boolean containsKey(Object key):判断该集合中是否有此键
public class MapDemo {
    public static void main(String[] args) {
        Map<String , Integer> maps = new HashMap<>();
        maps.put(.....);
        System.out.println(maps.isEmpty());//false
        Integer value = maps.get("....");//返回键值对象
        Set<String> keys = maps.keySet();//获取Map集合中所有的键,
        //Map集合的键是无序不重复的,所以返回的是一个Set集合
        Collection<Integer> values = maps.values();
        //Map集合的值是不做要求的,可能重复,所以值要用Collection集合接收!
    }
}

遍历方式

Map集合的遍历方式有:3种。

  1. “键找值”的方式遍历:先获取 Map 集合全部的键,再根据遍历键找值。
  2. “键值对”的方式遍历:难度较大,采用增强 for 或者迭代器
  3. JDK 1.8 开始之后的新技术:foreach,采用 Lambda 表达式

集合可以直接输出内容,因为底层重写了 toString() 方法

public static void main(String[] args){
    Map<String , Integer> maps = new HashMap<>();
	//(1)键找值
    Set<String> keys = maps.keySet();
    for(String key : keys) {
        System.out.println(key + "=" + maps.get(key));
    }
    //Iterator<String> iterator = hm.keySet().iterator();
    
    //(2)键值对
    //(2.1)普通方式
    Set<Map.Entry<String,Integer>> entries = maps.entrySet();
    for (Map.Entry<String, Integer> entry : entries) {
             System.out.println(entry.getKey() + "=>" + entry.getValue());
    }
    //(2.2)迭代器方式
    Iterator<Map.Entry<String, Integer>> iterator = maps.entrySet().iterator();
    while (iterator.hasNext()) {
        Map.Entry<String, Integer> entry = iterator.next();
        System.out.println(entry.getKey() + "=" + entry.getValue());

    }
    //(3) Lamda
    maps.forEach((k,v) -> {
        System.out.println(k + "==>" + v);
    })
}

HashMap

基本介绍

HashMap 基于哈希表的 Map 接口实现,是以 key-value 存储形式存在,主要用来存放键值对

特点:

  • HashMap 的实现不是同步的,这意味着它不是线程安全的
  • key 是唯一不重复的,底层的哈希表结构,依赖 hashCode 方法和 equals 方法保证键的唯一
  • key、value 都可以为null,但是 key 位置只能是一个null
  • HashMap 中的映射不是有序的,即存取是无序的
  • key 要存储的是自定义对象,需要重写 hashCode 和 equals 方法,防止出现地址不同内容相同的 key

JDK7 对比 JDK8:

  • 7 = 数组 + 链表,8 = 数组 + 链表 + 红黑树
  • 7 中是头插法,多线程容易造成环,8 中是尾插法
  • 7 的扩容是全部数据重新定位,8 中是位置不变或者当前位置 + 旧 size 大小来实现
  • 7 是先判断是否要扩容再插入,8 中是先插入再看是否要扩容

底层数据结构:

  • 哈希表(Hash table,也叫散列表),根据关键码值而直接访问的数据结构。通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度,这个映射函数叫做散列函数,存放记录的数组叫做散列表

  • JDK1.8 之前 HashMap 由数组+链表组成

    • 数组是 HashMap 的主体
    • 链表则是为了解决哈希冲突而存在的(拉链法解决冲突),拉链法就是头插法,两个对象调用的 hashCode 方法计算的哈希码值(键的哈希)一致导致计算的数组索引值相同
  • JDK1.8 以后 HashMap 由数组+链表 +红黑树数据结构组成

    • 解决哈希冲突时有了较大的变化
    • 当链表长度超过(大于)阈值(或者红黑树的边界值,默认为 8)并且当前数组的长度大于等于 64 时,此索引位置上的所有数据改为红黑树存储
    • 即使哈希函数取得再好,也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时,就相当于一个长的单链表,假如单链表有 n 个元素,遍历的时间复杂度是 O(n),所以 JDK1.8 中引入了 红黑树(查找时间复杂度为 O(logn))来优化这个问题,使得查找效率更高

参考视频:https://www.bilibili.com/video/BV1nJ411J7AA


继承关系

HashMap 继承关系如下图所示:

说明:

  • Cloneable 空接口,表示可以克隆, 创建并返回 HashMap 对象的一个副本。
  • Serializable 序列化接口,属于标记性接口,HashMap 对象可以被序列化和反序列化。
  • AbstractMap 父类提供了 Map 实现接口,以最大限度地减少实现此接口所需的工作

成员属性
  1. 序列化版本号

    private static final long serialVersionUID = 362498820763181265L;
  2. 集合的初始化容量(必须是二的 n 次幂 )

    // 默认的初始容量是16 -- 1<<4相当于1*2的4次方---1*16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

    HashMap 构造方法指定集合的初始化容量大小:

    HashMap(int initialCapacity)// 构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap
    • 为什么必须是 2 的 n 次幂?用位运算替代取余计算,减少 rehash 的代价(移动的节点少)

      HashMap 中添加元素时,需要根据 key 的 hash 值确定在数组中的具体位置。为了减少碰撞,把数据分配均匀,每个链表长度大致相同,实现该方法就是取模 hash%length,计算机中直接求余效率不如位移运算, hash % length == hash & (length-1) 的前提是 length 是 2 的 n 次幂

      散列平均分布:2 的 n 次方是 1 后面 n 个 0,2 的 n 次方 -1 是 n 个 1,可以保证散列的均匀性,减少碰撞

      例如长度为8时候,3&(8-1)=3  2&(8-1)=2 ,不同位置上,不碰撞;
      例如长度为9时候,3&(9-1)=0  2&(9-1)=0 ,都在0上,碰撞了;
    • 如果输入值不是 2 的幂会怎么样?

      创建 HashMap 对象时,HashMap 通过位移运算和或运算得到的肯定是 2 的幂次数,并且是大于那个数的最近的数字,底层采用 tableSizeFor() 方法

  3. 默认的负载因子,默认值是 0.75

    static final float DEFAULT_LOAD_FACTOR = 0.75f;
  4. 集合最大容量

    // 集合最大容量的上限是:2的30次幂
    static final int MAXIMUM_CAPACITY = 1 << 30;// 0100 0000 0000 0000 0000 0000 0000 0000 = 2 ^ 30
  5. 当链表的值超过 8 则会转红黑树(JDK1.8 新增)

    // 当桶(bucket)上的结点数大于这个值时会转成红黑树
    static final int TREEIFY_THRESHOLD = 8;

    为什么 Map 桶中节点个数大于 8 才转为红黑树?

    • 在 HashMap 中有一段注释说明:空间和时间的权衡

      TreeNodes占用空间大约是普通节点的两倍,所以我们只在箱子包含足够的节点时才使用树节点。当节点变少(由于删除或调整大小)时,就会被转换回普通的桶。在使用分布良好的用户hashcode时,很少使用树箱。理想情况下,在随机哈希码下,箱子中节点的频率服从"泊松分布",默认调整阈值为0.75,平均参数约为0.5,尽管由于调整粒度的差异很大。忽略方差,列表大小k的预期出现次数是(exp(-0.5)*pow(0.5, k)/factorial(k))
      0:    0.60653066
      1:    0.30326533
      2:    0.07581633
      3:    0.01263606
      4:    0.00157952
      5:    0.00015795
      6:    0.00001316
      7:    0.00000094
      8:    0.00000006
      more: less than 1 in ten million
      一个bin中链表长度达到8个元素的概率为0.00000006,几乎是不可能事件,所以我们选择8这个数字
    • 其他说法 红黑树的平均查找长度是 log(n),如果长度为 8,平均查找长度为 log(8)=3,链表的平均查找长度为 n/2,当长度为 8 时,平均查找长度为 8/2=4,这才有转换成树的必要;链表长度如果是小于等于 6,6/2=3,而 log(6)=2.6,虽然速度也很快的,但转化为树结构和生成树的时间并不短

  6. 当链表的值小于 6 则会从红黑树转回链表

    // 当桶(bucket)上的结点数小于这个值时树转链表
    static final int UNTREEIFY_THRESHOLD = 6;
  7. 当 Map 里面的数量大于等于这个阈值时,表中的桶才能进行树形化 ,否则桶内元素超过 8 时会扩容,而不是树形化。为了避免进行扩容、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD (8)

    // 桶中结构转化为红黑树对应的数组长度最小的值 
    static final int MIN_TREEIFY_CAPACITY = 64;

    原因:数组比较小的情况下变为红黑树结构,反而会降低效率,红黑树需要进行左旋,右旋,变色这些操作来保持平衡

  8. table 用来初始化(必须是二的 n 次幂)

    // 存储元素的数组 
    transient Node<K,V>[] table;
  9. HashMap 中存放元素的个数

    // 存放元素的个数,HashMap中K-V的实时数量,不是table数组的长度
    transient int size;
  10. 记录 HashMap 的修改次数

    // 每次扩容和更改map结构的计数器
     transient int modCount;  
  11. 调整大小下一个容量的值计算方式为:容量 * 负载因子,容量是数组的长度

    // 临界值,当实际大小(容量*负载因子)超过临界值时,会进行扩容
    int threshold;
  12. 哈希表的加载因子

     final float loadFactor;
    • 加载因子的概述

      loadFactor 加载因子,是用来衡量 HashMap 满的程度,表示 HashMap 的疏密程度,影响 hash 操作到同一个数组位置的概率,计算 HashMap 的实时加载因子的方法为 size/capacity,而不是占用桶的数量去除以 capacity,capacity 是桶的数量,也就是 table 的长度 length

      当 HashMap 容纳的元素已经达到数组长度的 75% 时,表示 HashMap 拥挤需要扩容,而扩容这个过程涉及到 rehash、复制数据等操作,非常消耗性能,所以开发中尽量减少扩容的次数,通过创建 HashMap 集合对象时指定初始容量来避免

      HashMap(int initialCapacity, float loadFactor)//构造指定初始容量和加载因子的空HashMap
    • 为什么加载因子设置为 0.75,初始化临界值是 12?

      loadFactor 太大导致查找元素效率低,存放的数据拥挤,太小导致数组的利用率低,存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值

    • threshold 计算公式:capacity(数组长度默认16) * loadFactor(默认 0.75)。当 size >= threshold 的时候,那么就要考虑对数组的 resize(扩容),这就是衡量数组是否需要扩增的一个标准, 扩容后的 HashMap 容量是之前容量的两倍


构造方法
  • 构造一个空的 HashMap ,默认初始容量(16)和默认负载因子(0.75)

    public HashMap() {
    	this.loadFactor = DEFAULT_LOAD_FACTOR; 
    	// 将默认的加载因子0.75赋值给loadFactor,并没有创建数组
    }
  • 构造一个具有指定的初始容量和默认负载因子(0.75)HashMap

    // 指定“容量大小”的构造函数
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
  • 构造一个具有指定的初始容量和负载因子的 HashMap

    public HashMap(int initialCapacity, float loadFactor) {
        // 进行判断
        // 将指定的加载因子赋值给HashMap成员变量的负载因子loadFactor
        this.loadFactor = loadFactor;
      	// 最后调用了tableSizeFor
        this.threshold = tableSizeFor(initialCapacity);
    }
    • 对于 this.threshold = tableSizeFor(initialCapacity)

      JDK8 以后的构造方法中,并没有对 table 这个成员变量进行初始化,table 的初始化被推迟到了 put 方法中,在 put 方法中会对 threshold 重新计算

  • 包含另一个 Map 的构造函数

    // 构造一个映射关系与指定 Map 相同的新 HashMap
    public HashMap(Map<? extends K, ? extends V> m) {
        // 负载因子loadFactor变为默认的负载因子0.75
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

    putMapEntries 源码分析:

    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        //获取参数集合的长度
        int s = m.size();
        if (s > 0) {
            //判断参数集合的长度是否大于0
            if (table == null) {  // 判断table是否已经初始化
                // pre-size
                // 未初始化,s为m的实际元素个数
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                // 计算得到的t大于阈值,则初始化阈值
                if (t > threshold)
                    threshold = tableSizeFor(t);
            }
            // 已初始化,并且m元素个数大于阈值,进行扩容处理
            else if (s > threshold)
                resize();
            // 将m中的所有元素添加至HashMap中
            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);
            }
        }
    }

    float ft = ((float)s / loadFactor) + 1.0F 这一行代码中为什么要加 1.0F ?

    s / loadFactor 的结果是小数,加 1.0F 相当于是对小数做一个向上取整以尽可能的保证更大容量,更大的容量能够减少 resize 的调用次数,这样可以减少数组的扩容


成员方法
  • hash():HashMap 是支持 Key 为空的;HashTable 是直接用 Key 来获取 HashCode,key 为空会抛异常

    • &(按位与运算):相同的二进制数位上,都是 1 的时候,结果为 1,否则为零

    • ^(按位异或运算):相同的二进制数位上,数字相同,结果为 0,不同为 1,不进位加法

      0 1 相互做 & | ^ 运算,结果出现 0 和 1 的数量分别是 3:1、1:3、1:1,所以异或是最平均的

    static final int hash(Object key) {
        int h;
        // 1)如果key等于null:可以看到当key等于null的时候也是有哈希值的,返回的是0
        // 2)如果key不等于null:首先计算出key的hashCode赋值给h,然后与h无符号右移16位后的二进制进行按位异或
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    计算 hash 的方法:将 hashCode 无符号右移 16 位,高 16bit 和低 16bit 做异或,扰动运算

    原因:当数组长度很小,假设是 16,那么 n-1 即为 1111 ,这样的值和 hashCode() 直接做按位与操作,实际上只使用了哈希值的后 4 位。如果当哈希值的高位变化很大,低位变化很小,就很容易造成哈希冲突了,所以这里把高低位都利用起来,让高16 位也参与运算,从而解决了这个问题

    哈希冲突的处理方式:

    • 开放定址法:线性探查法(ThreadLocalMap 使用),平方探查法(i + 1^2、i - 1^2、i + 2^2……)、双重散列(多个哈希函数)
    • 链地址法:拉链法
  • put():jdk1.8 前是头插法 (链地址法),多线程下扩容出现循环链表,jdk1.8 以后引入红黑树,插入方法变成尾插法

    第一次调用 put 方法时创建数组 Node[] table,因为散列表耗费内存,为了防止内存浪费,所以延迟初始化

    存储数据步骤(存储过程):

    1. 先通过 hash 值计算出 key 映射到哪个桶,哈希寻址
    2. 如果桶上没有碰撞冲突,则直接插入
    3. 如果出现碰撞冲突:如果该桶使用红黑树处理冲突,则调用红黑树的方法插入数据;否则采用传统的链式方法插入,如果链的长度达到临界值,则把链转变为红黑树
    4. 如果数组位置相同,通过 equals 比较内容是否相同:相同则新的 value 覆盖旧 value,不相同则将新的键值对添加到哈希表中
    5. 最后判断 size 是否大于阈值 threshold,则进行扩容
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    putVal() 方法中 key 在这里执行了一下 hash(),在 putVal 函数中使用到了上述 hash 函数计算的哈希值:

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
      	//。。。。。。。。。。。。。。
      	if ((p = tab[i = (n - 1) & hash]) == null){//这里的n表示数组长度16
      		//.....
          } else {
              if (e != null) { // existing mapping for key
                  V oldValue = e.value;
                  //onlyIfAbsent默认为false,所以可以覆盖已经存在的数据,如果为true说明不能覆盖
                  if (!onlyIfAbsent || oldValue == null)
                      e.value = value;
                  afterNodeAccess(e);
                  // 如果这里允许覆盖,就直接返回了
                  return oldValue;
              }
          }
        // 如果是添加操作,modCount ++,如果不是替换,不会走这里的逻辑,modCount用来记录逻辑的变化
        ++modCount;
        // 数量大于扩容阈值
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
    • (n - 1) & hash:计算下标位置
    • 余数本质是不断做除法,把剩余的数减去,运算效率要比位运算低
  • treeifyBin()

    节点添加完成之后判断此时节点个数是否大于 TREEIFY_THRESHOLD 临界值 8,如果大于则将链表转换为红黑树,转换红黑树的方法 treeifyBin,整体代码如下:

    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
       //转换为红黑树 tab表示数组名  hash表示哈希值
       treeifyBin(tab, hash);
    1. 如果当前数组为空或者数组的长度小于进行树形化的阈 MIN_TREEIFY_CAPACITY = 64 就去扩容,而不是将节点变为红黑树
    2. 如果是树形化遍历桶中的元素,创建相同个数的树形节点,复制内容,建立起联系,类似单向链表转换为双向链表
    3. 让桶中的第一个元素即数组中的元素指向新建的红黑树的节点,以后这个桶里的元素就是红黑树而不是链表数据结构了
  • tableSizeFor():创建 HashMap 指定容量时,HashMap 通过位移运算和或运算得到比指定初始化容量大的最小的 2 的 n 次幂

    static final int tableSizeFor(int cap) {//int cap = 10
        int n = cap - 1;
        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;
    }

    分析算法:

    1. int n = cap - 1:防止 cap 已经是 2 的幂。如果 cap 已经是 2 的幂, 不执行减 1 操作,则执行完后面的无符号右移操作之后,返回的 capacity 将是这个 cap 的 2 倍
    2. n=0 (cap-1 之后),则经过后面的几次无符号右移依然是 0,返回的 capacity 是 1,最后有 n+1
    3. |(按位或运算):相同的二进制数位上,都是 0 的时候,结果为 0,否则为 1
    4. 核心思想:把最高位是 1 的位以及右边的位全部置 1,结果加 1 后就是大于指定容量的最小的 2 的 n 次幂

    例如初始化的值为 10:

    • 第一次右移

      int n = cap - 1;//cap=10  n=9
      n |= n >>> 1;
      00000000 00000000 00000000 00001001 //9
      00000000 00000000 00000000 00000100 //9右移之后变为4
      --------------------------------------------------
      00000000 00000000 00000000 00001101 //按位或之后是13
      //使得n的二进制表示中与最高位的1紧邻的右边一位为1
    • 第二次右移

      n |= n >>> 2;//n通过第一次右移变为了:n=13
      00000000 00000000 00000000 00001101  // 13
      00000000 00000000 00000000 00000011  // 13右移之后变为3
      -------------------------------------------------
      00000000 00000000 00000000 00001111	 //按位或之后是15
      //无符号右移两位,会将最高位两个连续的1右移两位,然后再与原来的n做或操作,这样n的二进制表示的高位中会有4个连续的1

      注意:容量最大是 32bit 的正数,因此最后 n |= n >>> 16,最多是 32 个 1(但是这已经是负数了)。在执行 tableSizeFor 之前,对 initialCapacity 做了判断,如果大于 MAXIMUM_CAPACITY(2 ^ 30),则取 MAXIMUM_CAPACITY;如果小于 MAXIMUM_CAPACITY(2 ^ 30),会执行移位操作,所以移位操作之后,最大 30 个 1,加 1 之后得 2 ^ 30

    • 得到的 capacity 被赋值给了 threshold

      this.threshold = tableSizeFor(initialCapacity);//initialCapacity=10
    • JDK 11

      static final int tableSizeFor(int cap) {
          //无符号右移,高位补0
      	//-1补码: 11111111 11111111 11111111 11111111
          int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
          return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
      }
      //返回最高位之前的0的位数
      public static int numberOfLeadingZeros(int i) {
          if (i <= 0)
              return i == 0 ? 32 : 0;
          // 如果i>0,那么就表明在二进制表示中其至少有一位为1
          int n = 31;
          // i的最高位1在高16位,把i右移16位,让最高位1进入低16位继续递进判断
          if (i >= 1 << 16) { n -= 16; i >>>= 16; }
          if (i >= 1 <<  8) { n -=  8; i >>>=  8; }
          if (i >= 1 <<  4) { n -=  4; i >>>=  4; }
          if (i >= 1 <<  2) { n -=  2; i >>>=  2; }
          return n - (i >>> 1);
      }
  • resize():

    当 HashMap 中的元素个数超过 (数组长度)*loadFactor(负载因子) 或者链表过长时(链表长度 > 8,数组长度 < 64),就会进行数组扩容,创建新的数组,伴随一次重新 hash 分配,并且遍历 hash 表中所有的元素非常耗时,所以要尽量避免 resize

    扩容机制为扩容为原来容量的 2 倍:

    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 以前的容量已经是最大容量了,这时调大 扩容阈值 threshold
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // 初始化的threshold赋值给newCap
        newCap = oldThr;
    else { 
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    HashMap 在进行扩容后,节点要么就在原来的位置,要么就被分配到”原位置+旧容量”的位置

    判断:e.hash 与 oldCap 对应的有效高位上的值是 1,即当前数组长度 n 二进制为 1 的位为 x 位,如果 key 的哈希值 x 位也为 1,则扩容后的索引为 now + n

    注意:这里要求数组长度 2 的幂

    普通节点:把所有节点分成高低位两个链表,转移到数组

    // 遍历所有的节点
    do {
        next = e.next;
        // oldCap 旧数组大小,2 的 n 次幂
        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;
    }

    红黑树节点:扩容时 split 方法会将树拆成高位和低位两个链表,判断长度是否小于等于 6

    //如果低位链表首节点不为null,说明有这个链表存在
    if (loHead != null) {
        //如果链表下的元素小于等于6
        if (lc <= UNTREEIFY_THRESHOLD)
            //那就从红黑树转链表了,低位链表,迁移到新数组中下标不变,还是等于原数组到下标
            tab[index] = loHead.untreeify(map);
        else {
            //低位链表,迁移到新数组中下标不变,把低位链表整个赋值到这个下标下
            tab[index] = loHead;
            //如果高位首节点不为空,说明原来的红黑树已经被拆分成两个链表了
            if (hiHead != null)
                //需要构建新的红黑树了
                loHead.treeify(tab);
        }
    }

​

  • remove():删除是首先先找到元素的位置,如果是链表就遍历链表找到元素之后删除。如果是用红黑树就遍历树然后找到之后做删除,树小于 6 的时候退化为链表

     final Node<K,V> removeNode(int hash, Object key, Object value,
                                boolean matchValue, boolean movable) {
         Node<K,V>[] tab; Node<K,V> p; int n, index;
         // 节点数组tab不为空、数组长度n大于0、根据hash定位到的节点对象p,
         // 该节点为树的根节点或链表的首节点)不为空,从该节点p向下遍历,找到那个和key匹配的节点对象
         if ((tab = table) != null && (n = tab.length) > 0 &&
             (p = tab[index = (n - 1) & hash]) != null) {
             Node<K,V> node = null, e; K k; V v;//临时变量,储存要返回的节点信息
             //key和value都相等,直接返回该节点
             if (p.hash == hash &&
                 ((k = p.key) == key || (key != null && key.equals(k))))
                 node = p;
             
             else if ((e = p.next) != null) {
                 //如果是树节点,调用getTreeNode方法从树结构中查找满足条件的节点
                 if (p instanceof TreeNode)
                     node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                 //遍历链表
                 else {
                     do {
                         //e节点的键是否和key相等,e节点就是要删除的节点,赋值给node变量
                         if (e.hash == hash &&
                             ((k = e.key) == key ||
                              (key != null && key.equals(k)))) {
                             node = e;
                             //跳出循环
                             break;
                         }
                         p = e;//把当前节点p指向e 继续遍历
                     } while ((e = e.next) != null);
                 }
             }
             //如果node不为空,说明根据key匹配到了要删除的节点
             //如果不需要对比value值或者对比value值但是value值也相等,可以直接删除
             if (node != null && (!matchValue || (v = node.value) == value ||
                                  (value != null && value.equals(v)))) {
                 if (node instanceof TreeNode)
                     ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                 else if (node == p)//node是首节点
                     tab[index] = node.next;
                 else	//node不是首节点
                     p.next = node.next;
                 ++modCount;
                 --size;
                 //LinkedHashMap
                 afterNodeRemoval(node);
                 return node;
             }
         }
         return null;
     }
  • get()

    1. 通过 hash 值获取该 key 映射到的桶

    2. 桶上的 key 就是要查找的 key,则直接找到并返回

    3. 桶上的 key 不是要找的 key,则查看后续的节点:

      • 如果后续节点是红黑树节点,通过调用红黑树的方法根据 key 获取 value

      • 如果后续节点是链表节点,则通过循环遍历链表根据 key 获取 value

    4. 红黑树节点调用的是 getTreeNode 方法通过树形节点的 find 方法进行查

      • 查找红黑树,之前添加时已经保证这个树是有序的,因此查找时就是折半查找,效率更高。
      • 这里和插入时一样,如果对比节点的哈希值相等并且通过 equals 判断值也相等,就会判断 key 相等,直接返回,不相等就从子树中递归查找
    5. 时间复杂度 O(1)

      • 若为树,则在树中通过 key.equals(k) 查找,O(logn)
      • 若为链表,则在链表中通过 key.equals(k) 查找,O(n)

并发异常

HashMap 和 ArrayList 一样,内部采用 modCount 用来记录集合结构发生变化的次数,结构发生变化是指添加或者删除至少一个元素的所有操作,或者是调整内部数组的大小,仅仅只是设置元素的值不算结构发生变化

在进行序列化或者迭代等操作时,需要比较操作前后 modCount 是否改变,如果其他线程此时修改了集合内部的结构,就会直接抛出 ConcurrentModificationException 异常

HashMap map = new HashMap();
Iterator iterator = map.keySet().iterator();
final class KeySet extends AbstractSet<K> {
    // 底层获取的是 KeyIterator
	public final Iterator<K> iterator()     { 
        return new KeyIterator(); 
    }
}
final class KeyIterator extends HashIterator implements Iterator<K> {
    // 回调 HashMap.HashIterator#nextNode
    public final K next() { 
        return nextNode().key; 
    }
}
abstract class HashIterator {
    Node<K,V> next;        // next entry to return
    Node<K,V> current;     // current entry
    int expectedModCount;  // for 【fast-fail】,快速失败
    int index;             // current slot

    HashIterator() {
        // 把当前 map 的数量赋值给 expectedModCount,迭代时判断
        expectedModCount = modCount;
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        if (t != null && size > 0) { // advance to first entry
            do {} while (index < t.length && (next = t[index++]) == null);
        }
    }

    public final boolean hasNext() {
        return next != null;
    }
	// iterator.next() 会调用这个函数
    final Node<K,V> nextNode() {
        Node<K,V>[] t;
        Node<K,V> e = next;
        // 这里会判断 集合的结构是否发生了变化,变化后 modCount 会改变,直接抛出并发异常
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        if ((next = (current = e).next) == null && (t = table) != null) {
            do {} while (index < t.length && (next = t[index++]) == null);
        }
        return e;
    }
	// 迭代器允许删除集合的元素,【删除后会重置 expectedModCount = modCount】
    public final void remove() {
        Node<K,V> p = current;
        if (p == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        current = null;
        K key = p.key;
        removeNode(hash(key), key, null, false, false);
        // 同步expectedModCount
        expectedModCount = modCount;
    }
}

LinkedMap

原理分析

LinkedHashMap 是 HashMap 的子类

  • 优点:添加的元素按照键有序不重复的,有序的原因是底层维护了一个双向链表

  • 缺点:会占用一些内存空间

对比 Set:

  • HashSet 集合相当于是 HashMap 集合的键,不带值
  • LinkedHashSet 集合相当于是 LinkedHashMap 集合的键,不带值
  • 底层原理完全一样,都是基于哈希表按照键存储数据的,只是 Map 多了一个键的值

源码解析:

  • 内部维护了一个双向链表,用来维护插入顺序或者 LRU 顺序

    transient LinkedHashMap.Entry<K,V> head;
    transient LinkedHashMap.Entry<K,V> tail;
  • accessOrder 决定了顺序,默认为 false 维护的是插入顺序(先进先出),true 为访问顺序(LRU 顺序)

    final boolean accessOrder;
  • 维护顺序的函数

    void afterNodeAccess(Node<K,V> p) {}
    void afterNodeInsertion(boolean evict) {}
  • put()

    // 调用父类HashMap的put方法
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
    → afterNodeInsertion(evict);// evict为true

    afterNodeInsertion方法,当 removeEldestEntry() 方法返回 true 时会移除最近最久未使用的节点,也就是链表首部节点 first

    void afterNodeInsertion(boolean evict) {
        LinkedHashMap.Entry<K,V> first;
        // evict 只有在构建 Map 的时候才为 false,这里为 true
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);//移除头节点
        }
    }

    removeEldestEntry() 默认为 false,如果需要让它为 true,需要继承 LinkedHashMap 并且覆盖这个方法的实现,在实现 LRU 的缓存中特别有用,通过移除最近最久未使用的节点,从而保证缓存空间足够,并且缓存的数据都是热点数据

    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }
  • get()

    当一个节点被访问时,如果 accessOrder 为 true,则会将该节点移到链表尾部。也就是说指定为 LRU 顺序之后,在每次访问一个节点时会将这个节点移到链表尾部,那么链表首部就是最近最久未使用的节点

    public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }
    void afterNodeAccess(Node<K,V> e) {
        LinkedHashMap.Entry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            // 向下转型
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            // 判断 p 是否是首节点
            if (b == null)
                //是头节点 让p后继节点成为头节点
                head = a;
            else
                //不是头节点 让p的前驱节点的next指向p的后继节点,维护链表的连接
                b.after = a;
            // 判断p是否是尾节点
            if (a != null)
                // 不是尾节点 让p后继节点指向p的前驱节点
                a.before = b;
            else
                // 是尾节点 让last指向p的前驱节点
                last = b;
            // 判断last是否是空
            if (last == null)
                // last为空说明p是尾节点或者只有p一个节点
                head = p;
            else {
                // last和p相互连接
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }
  • remove()

    //调用HashMap的remove方法
    final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable)
    → afterNodeRemoval(node);

    当 HashMap 删除一个键值对时调用,会把在 HashMap 中删除的那个键值对一并从链表中删除

    void afterNodeRemoval(Node<K,V> e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        // 让p节点与前驱节点和后继节点断开链接
        p.before = p.after = null;
        // 判断p是否是头节点
        if (b == null)
            // p是头节点 让head指向p的后继节点
            head = a;
        else
            // p不是头节点 让p的前驱节点的next指向p的后继节点,维护链表的连接
            b.after = a;
        // 判断p是否是尾节点,是就让tail指向p的前驱节点,不是就让p.after指向前驱节点,双向
        if (a == null)
            tail = b;
        else
            a.before = b;
    }

LRU

使用 LinkedHashMap 实现的一个 LRU 缓存:

  • 设定最大缓存空间 MAX_ENTRIES 为 3
  • 使用 LinkedHashMap 的构造函数将 accessOrder 设置为 true,开启 LRU 顺序
  • 覆盖 removeEldestEntry() 方法实现,在节点多于 MAX_ENTRIES 就会将最近最久未使用的数据移除
public static void main(String[] args) {
    LRUCache<Integer, String> cache = new LRUCache<>();
    cache.put(1, "a");
    cache.put(2, "b");
    cache.put(3, "c");
    cache.get(1);//把1放入尾部
    cache.put(4, "d");
    System.out.println(cache.keySet());//[3, 1, 4]只能存3个,移除2
}

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private static final int MAX_ENTRIES = 3;

    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_ENTRIES;
    }

    LRUCache() {
        super(MAX_ENTRIES, 0.75f, true);
    }
}

TreeMap

TreeMap 实现了 SotredMap 接口,是有序不可重复的键值对集合,基于红黑树(Red-Black tree)实现,每个 key-value 都作为一个红黑树的节点,如果构造 TreeMap 没有指定比较器,则根据 key 执行自然排序(默认升序),如果指定了比较器则按照比较器来进行排序

TreeMap 集合指定大小规则有 2 种方式:

  • 直接为对象的类实现比较器规则接口 Comparable,重写比较方法
  • 直接为集合设置比较器 Comparator 对象,重写比较方法

说明:TreeSet 集合的底层是基于 TreeMap,只是键的附属值为空对象而已

成员属性:

  • Entry 节点

     static final class Entry<K,V> implements Map.Entry<K,V> {
         K key;
         V value;
         Entry<K,V> left;		//左孩子节点
         Entry<K,V> right;		//右孩子节点
         Entry<K,V> parent;		//父节点
         boolean color = BLACK;	//节点的颜色,在红黑树中只有两种颜色,红色和黑色
     }
  • compare()

    //如果comparator为null,采用comparable.compartTo进行比较,否则采用指定比较器比较大小
    final int compare(Object k1, Object k2) {
        return comparator == null ? ((Comparable<? super K>)k1).compareTo((K)k2)
            : comparator.compare((K)k1, (K)k2);
    }

参考文章:https://blog.csdn.net/weixin_33991727/article/details/91518677


WeakMap

WeakHashMap 是基于弱引用的,内部的 Entry 继承 WeakReference,被弱引用关联的对象在下一次垃圾回收时会被回收,并且构造方法传入引用队列,用来在清理对象完成以后清理引用

private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
    Entry(Object key, V value, ReferenceQueue<Object> queue, int hash, Entry<K,V> next) {
        super(key, queue);
        this.value = value;
        this.hash  = hash;
        this.next  = next;
    }
}

WeakHashMap 主要用来实现缓存,使用 WeakHashMap 来引用缓存对象,由 JVM 对这部分缓存进行回收

Tomcat 中的 ConcurrentCache 使用了 WeakHashMap 来实现缓存功能,ConcurrentCache 采取分代缓存:

  • 经常使用的对象放入 eden 中,eden 使用 ConcurrentHashMap 实现,不用担心会被回收(伊甸园)

  • 不常用的对象放入 longterm,longterm 使用 WeakHashMap 实现,这些老对象会被垃圾收集器回收

  • 当调用 get() 方法时,会先从 eden 区获取,如果没有找到的话再到 longterm 获取,当从 longterm 获取到就把对象放入 eden 中,从而保证经常被访问的节点不容易被回收

  • 当调用 put() 方法时,如果 eden 的大小超过了 size,那么就将 eden 中的所有对象都放入 longterm 中,利用虚拟机回收掉一部分不经常使用的对象

    public final class ConcurrentCache<K, V> {
        private final int size;
        private final Map<K, V> eden;
        private final Map<K, V> longterm;
    
        public ConcurrentCache(int size) {
            this.size = size;
            this.eden = new ConcurrentHashMap<>(size);
            this.longterm = new WeakHashMap<>(size);
        }
    
        public V get(K k) {
            V v = this.eden.get(k);
            if (v == null) {
                v = this.longterm.get(k);
                if (v != null)
                    this.eden.put(k, v);
            }
            return v;
        }
    
        public void put(K k, V v) {
            if (this.eden.size() >= size) {
                this.longterm.putAll(this.eden);
                this.eden.clear();
            }
            this.eden.put(k, v);
        }
    }