跳到主要内容

Java中的HashMap的工作原理是什么？

参考答案：

在 Java 中，HashMap 属于常用的基于哈希表实现的键值对存储结构，它采用了数组+链表/红黑树的方式进行实现。下面将从以下几个方面介绍 HashMap 的实现原理：哈希函数、数组+链表的实现、扩容机制。

一、哈希函数
HashMap 的核心思想是哈希映射，即将任意长度的输入（即键）通过哈希函数变换成固定长度的输出（即该键在数组中的索引位置），并将该键和值存储到找到的索引位置处。具体来说，哈希函数需要满足以下两个条件：
散列均匀。这意味着不同的键应该有不同的哈希值，并且此哈希值在数组中分布均匀，也就是不要让大量哈希值都集中到一个区域。
计算速度快。为了避免计算哈希值过于缓慢，需要使用高效的哈希函数。
在 Java 中，Java 8 以前使用的是传统的拉链法解决哈希冲突（即多个键映射到同一个数组下标的情况），而 Java 8 之后为了进一步提升性能，采用了链表和红黑树相结合的方式来处理哈希冲突。

二、数组+链表的实现
HashMap 的内部结构是一个数组，数组中每个元素称为桶。桶里放的元素类型是 Entry 类型的对象，该类包含了键和值。当 HashMap 中加入一个键值对时，它会首先根据键获取其哈希码（即通过根据 hash() 方法计算得到），然后通过这个哈希码在数组中找到相应桶，并把键值对存储在桶中。
如果多个键映射到同一索引位置上，就需要通过链表将它们串联起来，而 JDK 1.8 之前版本中采用的则是最基础的链式结构。但随着链表长度的增加，查询效率会逐渐变低，甚至还可能造成链表成环并导致死循环等情况，因此，Java 8 引入了一种新的机制：当链表长度超过阈值（默认为 8）时，会将链表转化为红黑树，以提高查询效率。在使用红黑树优化后，HashMap 的查询性能会更进一步的提升。