HashMap面试题讲解:HashMap的数据结构 #java

大家好，今天讲解HashMap的数据结构，先看下思维导图从三个方面进行讲解：一、简单的数据结构。二、HashMap的数据结构。三、案例演示。

先看下Java中的数据结构有哪些？Java中提供了以下几种：数组链表栈队列哈希表。接下来看下概念，数组、寻址易、插山难练表、寻址难、插山易。而HashMap的数据结构就是使用了数组+链表的方式，在JDK1.8之前是数组+链表法，在JDK1.8中是数组+链表+红黑树，其目的是提高性能。看一下下面两张图，加深对HashMap的数据结构的理解。

下面来看一下HashMap的数据结构介绍。当我们向HashMap中添加键值对时，会涉及到哈希表哈希码，索引计算冲突处理和可能的扩容。下面我将通过一个案例来演示这些概念。

·假设要创建一个HashMap，存储员工的姓名和工资信息。

→一、创建HashMap。首先创建一个空的HashMap。

→二、添加键值对。接下来可以向HashMap中添加键值对，例如。

→三、哈希码和索引计算。

HashMap使用键的哈希码来计算键值对应的索引位置。在这个案例中键是字符串类型，所以需要计算每个键的哈希码。并用哈希码计算索引位置，例如假设键"Alice"的哈希码是209119。

HashMap的大小是16(默认初始大小)，可以利用哈希码和HashMap大小计算索引位置。

→四、冲突处理。如果两个键计算得到的索引位置相同，则会发生冲突。

HashMap使用链表或红黑树来解决冲突。

在上述的情况下，假设"Alice"和"Charlie"的哈希码计算得到的索引位置相同，即索引位置为3HashMap的数据结构如下。

因为发生了冲突，"Alice"和"Charlie"被存储在同一个桶(Bucket)中。使用链表(或红黑树取决于桶内的元素数量)，将它们连接在一起。

·5扩容：如果HashMap中的键值对数量超过了载荷因子(默认为0.75)，HashMap将会进行扩容，以保持较低的冲突率和较高的性能。

在扩容过程中HashMap会创建一个新的数组，将存储的键值对重新计算索引位置，并重新分配到新的桶中，这样可以减少冲突的发生并提高性能。

当面试官问到HashMap的数据结构时，可以这样回答。