Hashmap

一、HashMap的工作原理

HashMap的核心是哈希表，它通过哈希函数将键映射到表中的特定位置（桶）。每个桶中可能存储一个或多个键值对（在发生哈希冲突时）。

哈希函数：将键转换为哈希码（一个整数），然后使用该哈希码计算桶的索引。哈希冲突：不同的键可能产生相同的哈希码，导致它们被映射到同一个桶中。HashMap通过链表（在Java 8及以后版本中，当链表长度超过一定阈值时，会转换为红黑树）来解决哈希冲突。负载因子与扩容：HashMap有一个负载因子（默认值为0.75），用于控制哈希表的填充程度。当哈希表中的元素数量超过负载因子与当前容量的乘积时，HashMap会进行扩容操作，以维持其性能。

在JDK1.7以前，HashMap的底层数据结构的实现是数组 + 链表的实现方式。但是在1.8之后HashMap的实现是数组 + 链表 + 红黑树

HashMap的扩容原理 扩容(resize)就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组，就像我们用一个小桶装水，如果想装更 多的水，就得换大水桶。

二、HashMap的使用方法

在Java中，HashMap的使用非常简单。以下是一个基本的示例：

import java.util.HashMap; public class HashMapExample { public static void main(String[] args) { // 创建一个HashMap实例 HashMap<String, Integer> map = new HashMap<>(); // 添加键值对 map.put("Apple", 1); map.put("Banana", 2); map.put("Cherry", 3); // 访问键值对 Integer value = map.get("Banana"); System.out.println("Value for Banana: " + value); // 检查键是否存在 boolean containsKey = map.containsKey("Apple"); System.out.println("Contains Apple: " + containsKey); // 遍历HashMap for (String key : map.keySet()) { System.out.println("Key: " + key + ", Value: " + map.get(key)); } // 移除键值对 map.remove("Cherry"); // 获取HashMap的大小 int size = map.size(); System.out.println("Size of HashMap: " + size); } } 数组+链表 初始状态与常见情况：在HashMap的初始状态或元素较少时，它主要使用数组来存储键值对。当发生哈希冲突（即不同的键被映射到数组的同一位置）时，会采用链表来解决冲突。此时，冲突的元素会以链表的形式链接在一起，形成一个同义词链表。适用场景：链表适用于元素数量相对较少，且哈希冲突不频繁的情况。在这种情况下，链表的插入、查找和删除操作都能保持较高的效率。 数组+红黑树 转换条件：从Java 8开始，HashMap引入了红黑树来优化性能。当链表中的元素数量超过一定阈值（默认为8），并且HashMap的容量大于64时，链表会被转换成红黑树。这是因为在元素数量较多时，链表的查找效率会下降，而红黑树能够提供O(log n)的查找时间复杂度，从而提高性能。适用场景：红黑树适用于元素数量较多，且哈希冲突较频繁的情况。在这种情况下，红黑树能够保持较好的平衡性，提高查找、插入和删除操作的效率。转换回链表：需要注意的是，当红黑树中的节点数量减少到一定程度（默认为6）时，红黑树会被转换回链表。这是为了避免在元素数量较少时，红黑树的复杂结构带来的额外开销。 三、HashMap的性能特点 时间复杂度：在理想情况下（哈希函数分布均匀，没有哈希冲突），HashMap的get和put操作的时间复杂度为O(1)。然而，在发生哈希冲突时，性能可能会下降。空间复杂度：HashMap的空间复杂度取决于其容量和负载因子。由于需要额外的空间来处理哈希冲突，因此实际的空间占用可能会比理论值稍大。线程安全性：HashMap不是线程安全的。如果在多线程环境中使用，需要采取额外的同步措施或使用ConcurrentHashMap等线程安全的替代方案。 四、注意事项 null键和null值：HashMap允许使用null作为键和值（但每个键只能映射到一个值，且每个null键只能映射到一个null值）。然而，在Java 8及以后版本中，如果尝试使用null作为键调用putIfAbsent方法，则会抛出NullPointerException。哈希函数的选择：自定义键类时，应确保重写hashCode和equals方法，以保持哈希函数的一致性和正确性。否则，可能会导致哈希冲突和性能下降。扩容开销：扩容是一个相对昂贵的操作，因为它需要重新分配内存和重新哈希所有现有的键值对。因此，在设置初始容量和负载因子时，应充分考虑应用程序的需求和预期的使用场景。 五、结语

HashMap是Java中一种非常强大且灵活的数据结构，它提供了高效的键值对存储和检索功能。通过理解其工作原理、掌握其使用方法以及注意其性能特点和注意事项，你可以更好地利用HashMap来优化你的Java应用程序。希望本文能帮助你深入理解HashMap，并在实际开发中灵活运用这一数据结构。