我将从Java集合的基础概念入手，介绍常见集合类型，再深入剖析HashMap的底层数据结构、源码实现及应用实例，助你全面掌握相关知识。
Java集合面试题详解：从数据结构到HashMap源码剖析
在Java开发领域，对集合框架的深入理解是至关重要的。无论是在日常开发还是面试场景中，集合相关知识都是高频考点。本文将带你深入探究Java集合，从常见的数据结构到HashMap的源码剖析，并结合实际应用实例，助力你全面掌握相关知识。
一、Java集合框架概述
Java集合框架为开发者提供了一套功能丰富、高效的数据结构和算法，用于存储、操作和管理数据。它主要包含三大类接口：Collection、Map和Iterator。
（一）Collection接口
Collection接口是集合框架的基础接口，它定义了一组操作元素的方法，如添加、删除、查询等。其主要的子接口有List和Set。
List接口：有序且可重复的集合。常见的实现类有ArrayList和LinkedList。
- ArrayList：基于数组实现，支持快速随机访问，但在插入和删除元素时，若涉及元素位置变动，时间复杂度较高。例如，在列表末尾添加元素时间复杂度为O(1)，而在指定位置插入或删除元素，时间复杂度为O(n-i)，其中i为指定位置。
- LinkedList：基于双向链表实现，插入和删除元素时间复杂度不受元素位置影响，近似为O(1)，但随机访问性能较差。
Set接口：无序且不可重复的集合。常见的实现类有HashSet和TreeSet。
- HashSet：基于HashMap实现，通过哈希表存储元素，能快速判断元素是否存在，添加和查询元素的时间复杂度平均为O(1)。
- TreeSet：基于红黑树实现，能对元素进行自动排序，默认按照自然顺序排序，也可通过传入Comparator实现自定义排序，其添加、删除和查询元素的时间复杂度为O(log n)。
（二）Map接口
Map接口用于存储键值对，键是唯一的，值可以重复。常见的实现类有HashMap、TreeMap和HashTable。
- HashMap：非线程安全，基于哈希表实现，允许null键和null值，插入和查询操作效率高，平均时间复杂度为O(1)，但在哈希冲突严重时性能会下降。
- TreeMap：基于红黑树实现，能对键进行排序，插入、删除和查询操作时间复杂度为O(log n)，不允许null键。
- HashTable：线程安全，方法都被synchronized修饰，性能相对较低，不允许null键和null值，已逐渐被ConcurrentHashMap替代。
（三）Iterator接口
Iterator接口用于遍历集合中的元素，提供了一种通用的遍历方式，允许在遍历过程中安全地删除元素。
二、HashMap底层数据结构
HashMap的底层数据结构在JDK1.8前后有较大变化。
（一）JDK1.7及之前
在JDK1.7及之前，HashMap底层由数组加链表组成，采用纯拉链法解决哈希冲突。其核心数据结构是Entry数组，每个数组元素是一个链表的头节点。当发生哈希冲突时，新的键值对会以头插法插入到链表头部。
例如，假设有一个HashMap，数组长度为4，负载因子为0.75。当向HashMap中插入键值对时，首先计算键的哈希值，然后通过 (n - 1) & hash（n为数组长度）确定该键值对在数组中的位置。如果该位置已经有元素存在，即发生哈希冲突，那么新的键值对会被插入到该位置链表的头部。
这种数据结构在链表较长时，查询效率会退化为O(n)，并且在多线程环境下进行扩容操作时，由于头插法的特性，可能会导致循环链表，进而出现死循环。
（二）JDK1.8及之后
JDK1.8对HashMap进行了优化，底层数据结构变为数组 + 链表 + 红黑树。当链表长度大于等于8且数组长度大于等于64时，链表会转换为红黑树，以提高查询效率。当树节点数小于等于6时，又会退化为链表。
此时，HashMap的核心数据结构变为Node数组，链表节点由Node表示，红黑树节点由TreeNode表示，TreeNode继承自Node。在插入元素时，采用尾插法，避免了多线程环境下头插法可能导致的循环链表问题。
例如，同样是一个数组长度为4，负载因子为0.75的HashMap。当插入键值对时，计算键的哈希值并确定在数组中的位置。若该位置为空，则直接插入；若该位置已有元素且为链表结构，当链表长度小于8时，采用尾插法将新元素插入链表尾部；当链表长度达到8且数组长度大于等于64时，链表转换为红黑树，新元素按照红黑树的插入规则插入。
这种优化使得HashMap在哈希冲突严重时，查询效率得到显著提升，最坏情况下时间复杂度从O(n)变为O(log n)。
三、HashMap源码剖析
（一）重要属性
- table：Node[]类型的数组，用于存储键值对，是HashMap的主体。
- size：记录HashMap中键值对的数量。
- threshold：阈值，当HashMap中的元素数量超过该值时，会触发扩容操作，计算公式为capacity * loadFactor。
- loadFactor：负载因子，默认值为0.75，它是空间和时间效率的一个权衡值。较大的负载因子可以提高空间利用率，但会增加哈希冲突的概率，降低查询效率；较小的负载因子则相反，哈希冲突减少，但会浪费更多内存空间。
（二）put方法流程
- 计算键的哈希值：调用key的hashCode()方法得到哈希值，然后通过扰动函数进一步处理，减少哈希冲突。在JDK1.8中，扰动函数为hash = key.hashCode() ^ (hash >>> 16)。
- 若数组未初始化，则进行扩容操作。
- 计算桶位索引：通过 (n - 1) & hash（n为数组长度）计算出该键值对在数组中的存储位置。
- 处理哈希冲突：
- 如果该位置为空，直接将新的键值对插入。
- 如果该位置已有元素：
- 若为链表结构，遍历链表，比较每个节点的哈希值和键是否与新插入的相同。若相同，则直接覆盖旧值；若不同，则采用尾插法将新元素插入链表尾部。当链表长度达到8且数组长度大于等于64时，链表转换为红黑树。
- 若为红黑树结构，按照红黑树的插入规则插入新元素。
- 判断是否需要树化：如果当前桶位的链表长度达到8且数组长度大于等于64，将链表转换为红黑树。
- 检查扩容阈值：插入元素后，检查HashMap的元素数量是否超过阈值，若超过则进行扩容操作。
（三）扩容机制（resize方法）
- 触发条件：当HashMap中的元素数量size大于阈值threshold（threshold = capacity * loadFactor）时，触发扩容操作。
- 扩容策略：
- 容量变为原来的2倍，并且新容量仍为2的幂次方。这是因为在计算桶位索引时，使用 (n - 1) & hash（n为数组长度），当n为2的幂次方时，这种位运算等价于取模运算，且位运算效率更高。
- 重新计算键值对在新数组中的位置。在JDK1.8中，采用高低位拆分的方式优化数据迁移。对于每个键值对，其在新数组中的位置要么是原索引位置，要么是原索引位置加上旧容量。
例如，假设原数组长度为4，扩容后新数组长度为8。对于某个键值对，其在原数组中的索引为1，经过高低位拆分计算后，在新数组中的索引可能还是1，也可能是1 + 4 = 5。
四、Java集合应用实例
（一）订单管理系统
在订单管理系统中，通常需要根据订单ID快速查询订单信息。可以使用HashMap来存储订单数据，订单ID作为键，订单对象作为值。
import java.util.HashMap;
import java.util.Map;
class Order {
private String orderId;
private String productName;
// 其他订单相关属性和方法
public Order(String orderId, String productName) {
this.orderId = orderId;
this.productName = productName;
}
public String getOrderId() {
return orderId;
}
public String getProductName() {
return productName;
}
}
public class OrderManagementSystem {
private Map<String, Order> orderMap;
public OrderManagementSystem() {
orderMap = new HashMap<>();
}
public void addOrder(Order order) {
orderMap.put(order.getOrderId(), order);
}
public Order getOrder(String orderId) {
return orderMap.get(orderId);
}
public static void main(String[] args) {
OrderManagementSystem system = new OrderManagementSystem();
Order order1 = new Order("1001", "手机");
Order order2 = new Order("1002", "电脑");
system.addOrder(order1);
system.addOrder(order2);
Order retrievedOrder = system.getOrder("1001");
if (retrievedOrder != null) {
System.out.println("订单ID: " + retrievedOrder.getOrderId() + "，商品名称: " + retrievedOrder.getProductName());
}
}
}
在这个例子中，通过HashMap的put方法将订单信息存入，使用get方法根据订单ID快速获取订单对象，利用了HashMap基于键快速查找的特性，提高了订单管理系统的查询效率。
（二）用户权限管理系统
在用户权限管理系统中，每个用户可能拥有多个权限，且权限集合是无序且唯一的。可以使用HashSet来存储用户的权限。
import java.util.HashSet;
import java.util.Set;
class User {
private String userId;
private Set<String> permissions;
public User(String userId) {
this.userId = userId;
permissions = new HashSet<>();
}
public void addPermission(String permission) {
permissions.add(permission);
}
public boolean hasPermission(String permission) {
return permissions.contains(permission);
}
public String getUserId() {
return userId;
}
}
public class UserPermissionSystem {
public static void main(String[] args) {
User user = new User("user001");
user.addPermission("read");
user.addPermission("write");
boolean hasReadPermission = user.hasPermission("read");
boolean hasDeletePermission = user.hasPermission("delete");
System.out.println("用户user001是否有读取权限: " + hasReadPermission);
System.out.println("用户user001是否有删除权限: " + hasDeletePermission);
}
}
这里使用HashSet存储用户权限，利用其无序且不允许重复元素的特性，确保每个权限在集合中唯一，并且通过add和contains方法实现高效的权限添加和查询操作。
五、总结
通过对Java集合框架的全面了解，特别是对HashMap底层数据结构和源码的深入剖析，以及结合实际应用实例，我们可以更好地掌握Java集合在开发中的应用。在面试中，对于集合相关问题也能更加从容应对。希望本文能对你有所帮助，在Java开发学习和实践中不断积累和提升。
如果你在学习过程中有任何疑问，或者希望我对文中某个知识点进一步展开讲解，欢迎随时告诉我，我很乐意提供更多帮助。
Java 集合，数据结构，HashMap, 源码剖析，面试题，ArrayList,LinkedList,HashSet,TreeSet,ConcurrentHashMap, 集合框架，泛型，迭代器，扩容机制，高频考点
资源地址：
https://pan.quark.cn/s/14fcf913bae6
