HashMap 原理和面试常见的问题

痛定思痛。 2022-03-14 16:42 217阅读 0赞

# hashmap原理 #

HashMap 是基于哈斯表的 Map 接口的非同步实现，此实现提供所有可选的映射操作，并允许 null 值、null 键的存在，它存储的是键值对，但不保证映射的顺序，不保证该循序有恒不变。

## 数据结构 ##

HashMap 底层是*数组+链表*的组合，结合了数组和链表优势，使寻址和插入、删除变容易了。

1.7结构如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dyZXlfbW91c2U_size_16_color_FFFFFF_t_70][]

1.8结构如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dyZXlfbW91c2U_size_16_color_FFFFFF_t_70 1][]

从1.7的结构可以看出，如果链表越来越长，查询的效率就会变得越来越差，因此在1.8中做了写修改，当链表得元素大于或等于8时，就把链表变为红黑树（一种二叉树）。

JDK 1.7和1.8的不同：

>  *  1.7 如果发生了冲突，新元素会放在链表头
>  *  1.8 如果发生了冲突，新元素会放在链表尾
>  *  1.7 扩容后链表的顺序会颠倒
>  *  1.8 扩容后链表的顺序会保持

1.8 后对链表长度控制有新的优化

>  *  当链表长度过长时，会首先执行扩容
>  *  当扩容的大小超过64时，就不会使用扩容减少链表长度了
>  *  在链表长度大于等于8时，会把链表变为一个搜索二叉树(红黑树)

容量初始大小是 16 ， 当元素超过了初始大小的 3/4， 就会发生扩容

## 过程 ##

当要把数据放入 HashMap 中时，首先计算该数据的 HashCode 值，让后把 HashCode 值 % HashMap 容量值 计算出桶下标（位置），让后把数据放到该桶下标处，以此类推，当要查询时，也是要算出桶下标，接着到该桶下标处把数据沿着链表用 equals 比较，是否相同，如果相同，就查到该数据，因此 HashMap 必须实现 HashCode 和 equals 方法，如果当元素超过初始大小（初始大小16）的3/4发生扩容时，会重新计算桶下标，这时有些数据会位置会变化，把变化位置的数据移到正确的位置就好了。

## HashMap Ddos 攻击 ##

精心生成一大批 hashCode 相同的字符串，不断的向 hash 表中加入大量这样的 key ，让 hash 表退化为线性结构，造成性能严重下降。

## 面试时的常见问题 ##

**1) HashMap 底层的数据结构**

答：数据+链表+红黑树

**2) 负载因子是干嘛的**

答：决定了扩容的一个因素

**3) 扩容过程**

答：容量翻倍，遍历原来的链表，重新计算hashcode和桶下标，然后把桶下标发生改变的元素迁移到新的位置

**4) 为什么hashmap的容量是 2^n**

答：因为容量为2^n的时候，不同的key算得得位置相同的几率小，那么数据分布就比较均匀，也就是说碰撞减小了，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就提高了。

**5) hashmap 多线程访问时发生了扩容，会发生什么现象**

答：死链、数据丢失

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dyZXlfbW91c2U_size_16_color_FFFFFF_t_70]: /images/20220312/91dea021381543b2ac92781a44d10500.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dyZXlfbW91c2U_size_16_color_FFFFFF_t_70 1]: /images/20220312/484b56e6e1be4d5cb45da4459abe73aa.png