数据结构底层之HashMap(面经篇1)

1 . 讲一下hashmap的数据结构

   HashMap是一种基于哈希表实现的数据结构，通常用于关联键值对，其中键是唯一的，而值可以重复。在Java中，HashMap是java.util.Map接口的一个实现，它提供了快速的查找、插入和删除操作。

数据结构

HashMap的核心结构包括以下组成部分：

1. 数组：HashMap的底层是一个数组，这个数组的每个位置（通常称为“桶”或“槽”）可以存放一个或多个键值对。数组的大小通常是2的幂，以便能够高效地进行哈希值到数组索引的转换。

2. 链表或红黑树：在数组的每个位置，如果多个键的哈希值映射到同一个数组索引上（这种情况称为哈希冲突），那么这些键值对会被组织成一个链表或者在某些情况下是红黑树。从Java 8开始，当链表中的节点超过一定阈值（默认为8）且数组达到最小大小（默认为64），链表会转换为红黑树，以提高查找效率。

3. 节点（Node）：每个键值对被封装在一个节点对象中，这个对象包含了键、值、哈希码和指向下一个节点的引用。在Java 8中，为了支持链表和红黑树的转换，引入了更复杂的节点类型，如  TreeNode。

工作原理

1. 哈希函数：当插入一个新的键值对时，首先会计算键的哈希码，这通常由键对象的hashCode()方法提供。然后，这个哈希码经过一定的运算（如按位与运算）被转换为数组索引。

2. 冲突解决：如果两个或更多键的哈希值映射到同一个索引，它们会被添加到该索引处的链表或红黑树中。

3. 查找：当需要查找一个键时，首先计算其哈希码并找到相应的数组索引。然后遍历该位置上的链表或红黑树，使用equals()方法比较键，直到找到匹配的键为止。

4. 调整大小（Resize）：当HashMap中的元素数量超过了其容量乘以加载因子（默认为0.75）时，HashMap会自动调整其大小（通常增加为两倍），并将所有元素重新散列到新的数组中。这个过程称为“rehashing”。