HashMap源码分析

### HashMap源码分析 #### 一、概述 `HashMap`是Java编程语言中非常重要的一个数据结构，它属于`java.util`包的一部分，是`Map`接口的一个具体实现类。`HashMap`允许存储键值对，并且支持使用`null`作为键或值，这与`Hashtable`有所不同，后者不允许键或值为`null`。`HashMap`通过散列表来存储数据，这种设计使得在大多数情况下，其插入、删除和查找操作的时间复杂度均为O(1)。 #### 二、HashMap的数据结构 `HashMap`的数据结构由数组和链表共同组成，其中数组作为基础容器，每个数组元素实际上是一个链表的头部。当发生散列冲突时，即多个键值对被散列到同一个数组索引上时，这些键值对会被链接成一个链表。从JDK 8开始，当链表长度达到一定阈值后会转换为红黑树结构，以提高查找效率。 - **内部节点**：`HashMap`中的内部类`Entry<K, V>`表示一个键值对，其中包含`key`、`value`、指向下一个元素的指针`next`以及散列码`hash`。`Entry`类实现了`Map.Entry<K, V>`接口，这样就可以将`Entry`对象视为键值对的抽象表示。 #### 三、构造函数 `HashMap`提供了多种构造函数以满足不同场景的需求： 1. **无参构造函数** `HashMap()`：创建一个初始容量为16，加载因子为0.75的空`HashMap`。 2. **指定初始容量的构造函数** `HashMap(int initialCapacity)`：创建一个具有指定初始容量和默认加载因子0.75的空`HashMap`。 3. **指定初始容量和加载因子的构造函数** `HashMap(int initialCapacity, float loadFactor)`：创建一个具有指定初始容量和加载因子的空`HashMap`。 4. **基于另一个映射创建的构造函数** `HashMap(Map<? extends K, ? extends V> m)`：根据已存在的映射创建一个新的`HashMap`，新`HashMap`将包含原映射的所有映射关系。 以下重点介绍指定初始容量和加载因子的构造函数实现细节： ```java public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // 找到大于等于initialCapacity的2的幂 int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry[capacity]; useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); init(); } ``` - **参数检查**：首先对传入的`initialCapacity`和`loadFactor`进行有效性检查，确保它们符合逻辑要求。 - **确定容量**：为了提高散列表的性能，`HashMap`要求容量必须为2的幂。因此，这里通过循环左移的方式找到最接近`initialCapacity`的2的幂。 - **设置属性**：初始化`loadFactor`和`threshold`属性，`threshold`用于判断何时需要重新散列。 - **初始化散列表**：创建大小为`capacity`的`Entry[]`数组作为散列表，并设置`useAltHashing`标志以决定是否启用替代散列算法。 #### 四、总结 `HashMap`通过结合数组和链表（或红黑树）的数据结构，在保持高效的同时也具备了一定的灵活性。对于开发人员来说，理解`HashMap`的工作原理对于编写高效代码至关重要。通过本篇源码分析，我们深入了解了`HashMap`的基本结构、构造函数的具体实现，这对于进一步掌握`HashMap`的使用及优化具有重要意义。