> 说说你对 HashMap 数据结构的理解？

`HashMap`又称哈希表，又称散列表。首先，hashmap 的数据结构是基于数组和链表的，如图：

![img](https://cs-wlei224.obs.cn-south-1.myhuaweicloud.com/blog-imgs/202312070046177.png)

so，既然是基于数组和链表的，那就说明数组和链表的特点也就是 HashMap 的特点：

**数组：寻址快，直接根据索引访问元素，插入和删除慢；**

**链表：寻址慢，需要从头节点开始遍历，插入和删除快。**



说到 HashMap 就要说到 Java 8 了，Java 8 之前，HashMap 使用一个数组加链表的结构来存储 【K，V】 键值对。

如果发生 hash 冲突，那么

这将导致在处理 hash 冲突的时候性能不高，尤其是链表很长的时候。因此，Java 8 中的 HashMap 引入了红黑树来替代链表，这样当链表变长的时候，会自动转换为红黑树，从而提高了增删改查的性能。



> 什么是 Hash 冲突？怎么解决？

哈希冲突就是不同的数据经过哈希计算之后，得到的
`hash`值相同，然后被映射到了哈希表中的同一个位置，这就是哈希冲突。

**解决方法：**
1. 开放寻址法
意思就是，一旦发生冲突的话，就去按线性顺序寻找下一个空的散列地址，知道找到存放位置；
2. 链地址法
就是将哈希表数组的元素作为链表的头结点（这个链表的所有元素构成一个近义词链表，因为经过`hash`计算值相同），一旦哈希冲突，就把该关键字链接到该结点的尾部；
3. 再哈希法
顾名思义，就是再次通过另一个`hash`函数计算，得到另外的散列地址，直到冲突不发生；
4. 建立公共溢出区
将哈希表分为`基本表`与`溢出表`，发生冲突的元素放入溢出表中。
