当前位置： 首页 > news >正文

java溯本求源之基础(二十七)之--Map常用子类及源码分析(6000字长文)

news 2024/10/28 22:01:02

目录

1.引言

2.Map接口概述

3.常用Map子类详细分析

3.1 HashMap

3.1.1 概述

3.1.2 关键特性

3.1.3源码分析

3.1.3.1构造函数

3.1.3.2 主要方法分析

put 方法

get 方法 

resize 方法

3.2 TreeMap

3.2.1 概述

3.2.2 关键特性

3.2.3 源码分析

3.2.3.1构造函数

3.2.3.2主要方法分析

3.3 LinkedHashMap

3.3.1 概述

3.3.2 关键特性

3.3.3 源码分析

3.3.3.1 构造函数

3.3.3.2 主要方法分析

removeEldestEntry 方法

4. 其他Map子类

5. 性能比较

6.使用场景

7. 总结

1.引言

        在Java编程中，数据结构的选择至关重要。Map接口作为Java Collections Framework的一部分，提供了一种通过键值对存储数据的方式。本文将深入探讨Map接口的常用子类及其实现源码，帮助读者在实际开发中选择合适的数据结构，提高代码的性能和可维护性。

2.Map接口概述

        Map接口定义了一种映射关系，其中每个键（Key）都映射到一个值（Value）。Map的主要特性包括：

  • 键唯一：一个键只能对应一个值。
  • 不保证顺序：不同实现类对键值对的存储顺序有不同的特性。

常用的Map实现包括：

  • HashMap：基于哈希表实现，提供快速的插入和查找。
  • TreeMap：基于红黑树实现，支持自然排序或定制排序。
  • LinkedHashMap：结合了HashMap和LinkedList，维护插入顺序。

3.常用Map子类详细分析

3.1 HashMap
3.1.1 概述

        HashMap是Java中最常用的Map实现，底层使用哈希表存储键值对。它的主要优点是快速的插入和查找，时间复杂度为O(1)。

3.1.2 关键特性
  • 不保证顺序：HashMap中的元素顺序与插入顺序无关。
  • 线程不安全：在多线程环境下，HashMap需要外部同步。
3.1.3源码分析
3.1.3.1构造函数

  HashMap 提供了多种构造函数，主要有以下三种：

  • 默认构造函数
public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // 负载因子为默认值 0.75
}

  • 指定初始容量的构造函数

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

  • 指定初始容量和负载因子的构造函数

public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " + loadFactor);this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCapacity);
}

        在构造 HashMap 时，我们可以指定初始容量和负载因子，负载因子的默认值为 0.75，它表示当哈希表填充度达到 75% 时进行扩容。

3.1.3.2 主要方法分析
  • put 方法

 put 方法用于向 HashMap 中插入键值对：

//put 方法用于向 HashMap 中插入键值对：
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}
//计算键的哈希值
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}//查找桶的位置：通过哈希值对数组长度取模，找到对应的桶。//处理冲突：如果桶中已经存在节点，则通过链表（或红黑树）解决冲突。//插入新节点：如果桶为空，直接插入；如果有冲突则添加到链表末尾。

！！！put方法的大致流程 这里可以算作一个面试题

  • 根据 Key 计算数组下标：
    通过 Key 的哈希值，结合位运算，计算出数组中的位置（下标）。

  • 判断该下标是否为空：

    • 如果下标对应的数组位置为空，说明还没有元素占用这个位置。此时，会将 Key 和 Value 封装成一个 Entry 对象（在 JDK 1.7 中）或 Node 对象（在 JDK 1.8 中），并将其放入该位置。

  • 下标位置不为空时的处理：
    如果该下标位置已经有元素存在，就需要根据不同的情况进行处理：

    a. JDK 1.7 的处理：

        首先检查是否需要扩容，如果需要扩容就进行扩容操作。扩容完成后，重新插入元素。

如果不需要扩容，则会生成一个新的 Entry 对象，并使用头插法将这个新对象插入到当前链表的头部。

  • b. JDK 1.8 的处理：

       首先会检查当前 Node 的类型，判断该位置上的节点是红黑树节点还是链表节点。

       如果是红黑树节点：将 Key 和 Value 封装为红黑树的节点，并将其插入到红黑树中。在插入过程中，会检查红黑树中是否已经存在相同的 Key。如果存在，则更新对应的 Value。  

       如果是链表节点：将 Key 和 Value 封装为链表节点，并通过尾插法将新节点添加到链表的末尾。在这个过程中会遍历整个链表，检查是否有相同的 Key。如果找到相同的 Key，则更新其对应的 Value。 - 插入完成后，会检查链表的节点数量。如果链表中的节点数量大于或等于 8，则会将该链表转换为红黑树，以提高性能。

        扩容判断：不论是插入到链表还是红黑树中，最后都会再次检查是否需要扩容。如果需要扩容，则进行扩容操作。如果不需要扩容，则 put() 方法执行完毕。

  • get 方法 
//get 方法用于根据键查找对应的值：
public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//通过计算哈希值找到桶的位置。//遍历链表或红黑树，查找与键匹配的节点。
  • resize 方法
final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // 阈值翻倍}else if (oldThr > 0) // 初始容量存放在阈值中newCap = oldThr;else {               // 零初始阈值表示使用默认值newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {oldTab[j] = null;if (e.next == null)newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // 保持顺序Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.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;
}
3.2 TreeMap
3.2.1 概述

        TreeMap基于红黑树实现，自动对键进行排序。它适合需要有序键的场景。

3.2.2 关键特性
  • 支持自然排序或定制排序。
  • 迭代时返回的键是有序的。
3.2.3 源码分析
3.2.3.1构造函数
  • 默认构造函数
public TreeMap() {comparator = null; // 默认使用自然顺序
}
  • 使用指定比较器的构造函数
public TreeMap(Comparator<? super K> comparator) {this.comparator = comparator;
}
  • 根据现有映射构造
public TreeMap(Comparator<? super K> comparator) {this.comparator = comparator;
}
3.2.3.2主要方法分析

  • put 方法

//        put 方法用于向 TreeMap 中插入键值对：
public V put(K key, V value) {return putVal(key, value, false);}//        在插入过程中，首先检查键是否已经存在。
//        如果键不存在，则创建一个新节点，并根据红黑树的插入规
  • get 方法
//        get 方法用于根据键查找对应的值：public V get(Object key) {Entry<K,V> e = getEntry(key);return (e == null) ? null : e.value;}
//        通过比较器找到键对应的节点。
//        如果找到，返回对应的值；否则返回 null。

  • remove 方法

        public V remove(Object key) {Entry<K,V> p = getEntry(key);if (p == null) return null;V oldValue = p.value;deleteEntry(p);return oldValue;}//        找到要删除的节点后，进行删除操作，并调整树的结构以保持红黑树的性质。
3.3 LinkedHashMap
3.3.1 概述

        LinkedHashMap结合了HashMap和双向链表，维护插入顺序或访问顺序。

3.3.2 关键特性
  • 保持元素的插入顺序或访问顺序。
  • 适用于需要顺序的遍历场景。
3.3.3 源码分析

LinkedHashMap在HashMap的基础上增加了双向链表的逻辑。

3.3.3.1 构造函数
  • 默认构造函数
public LinkedHashMap() {super(); // 调用父类 HashMap 的构造函数，默认初始容量为 16，负载因子为 0.75accessOrder = false; // 默认按插入顺序
}
  • 指定初始容量的构造函数
public LinkedHashMap(int initialCapacity) {super(initialCapacity); // 调用父类 HashMap 的构造函数accessOrder = false; // 默认按插入顺序
}
  • 指定初始容量和访问顺序的构造函数
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {super(initialCapacity, loadFactor); // 调用父类 HashMap 的构造函数this.accessOrder = accessOrder; // 指定访问顺序
}
3.3.3.2 主要方法分析
  • put 方法
public V put(K key, V value) {return super.put(key, value); // 调用父类 HashMap 的 put 方法
}
  • get 方法
public V get(Object key) {Node<K,V> e;// 通过计算哈希值找到对应节点if ((e = getNode(hash(key), key)) == null) {return null; // 如果未找到，返回 null}// 如果是按访问顺序，则更新访问节点的顺序if (accessOrder) {afterNodeAccess(e);}return e.value; // 返回节点的值
}

  • removeEldestEntry 方法

//此方法用于控制在插入新元素时是否移除最老的元素，可以通过重写此方法来实现自定义的容量限制。
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {return false; // 默认不移除
}

4. 其他Map子类

除了上述常用子类，Java还提供了一些其他Map实现：

  • ConcurrentHashMap：线程安全的HashMap实现，采用分段锁机制，提高并发性能。
  • WeakHashMap：允许垃圾回收器回收的Map实现，适用于缓存场景。

5. 性能比较

在选择Map实现时，应考虑以下性能指标：

  • HashMap：适合快速查找和插入，使用广泛。
  • TreeMap：适合需要排序的场景，性能相对较慢。
  • LinkedHashMap：在保持顺序的情况下提供合理性能，适用于需要遍历的场景。

6.使用场景

  • HashMap：缓存、查找表,或者在做业务的时候为了避免重复for循环查询某个表，也可以全量查询出来封装成Map。
  • TreeMap：有序数据存储，如字典。
  • LinkedHashMap：实现LRU缓存策略。

7. 总结

        本文详细分析了Java中Map的常用子类及其源码实现。理解这些实现的特性和适用场景，对于提升Java开发者的编码能力至关重要。希望读者能够根据具体需求选择合适的Map实现，优化程序性能。


http://www.mrgr.cn/news/60596.html

相关文章：

  • DSPy：不需要手写prompt啦，You Only Code Once！
  • 前端零基础入门到上班：【Day1】什么是前端？
  • python 安装教程
  • STL-常用容器-list
  • Python 中的 object
  • # 渗透测试#安全见闻9 二进制安全
  • 中项到高项：软考信息系统项目管理师证书进阶指南
  • Pytest用例执行顺序和跳过执行详解
  • SQL-lab靶场less1-4
  • 《C++ 旧项目全局变量模块化改造：稳扎稳打，守护原有功能》
  • Flow-based生成模型理解
  • DevSecOps在数字政府建设中的实践研究
  • MinIO方法封装
  • 【C++】Type punning类型双关、union联合体、C++中的类型转换casting
  • 手机也能开数电票了，可能我也即将要失业了
  • Codigger桌面模式之Size Look介绍
  • 使用语言模型进行文本摘要的五个级别（llm）
  • 去中心化的概述
  • 机器学习中的谱聚类及实践案例
  • VLAN聚合
  • 1.字节大小
  • Java集合框架中的泛型有什么优点？
  • 第13天小整理
  • 机器学习入门之监督学习
  • 并联 高电压、高电流 放大器实现 2 倍输出电流模块±2A
  • 《学会提问》