ToB企服应用市场:ToB评测及商务社交产业平台

标题: Java HashMap 详解 [打印本页]

作者: 海哥 时间: 2024-5-12 15:17
标题: Java HashMap 详解
HashMap

HashMap 继续自 AbstractMap，实现了 Map 接口，基于哈希表实现，元素以键值对的方式存储，允许键和值为 null。由于 key 不允许重复，因此只能有一个键为 null。HashMap 不能包管放入元素的顺序，它是无序的，和放入的顺序并不相同。HashMap 是线程不安全的。
1. 哈希表

哈希表基于数组实现，当前元素的关键字通过某个哈希函数得到一个哈希值，这个哈希值映射到数组中的某个位置。哈希函数的优劣直接决定该哈希表的性能
当我们对某个元素举行哈希运算，得到一个存储地址，然后要举行插入的时候，发现已经被其他元素占用了，这就是所谓的哈希辩论，也叫哈希碰撞
解决方法如下：

开放定址法：当辩论发生时，使用某种探查技术在散列表中形成一个探查序列，沿此序列逐个单位地查找，直到碰到一个开放的地址（即该地址单位为空），将待插入的新结点存入该地址单位
链地址法：可将散列表界说为一个由 m 个头指针构成的指针数组，将所有关键字为同义词的结点链接在同一个单链表中，初始时数组中各分量的初值应均为 1
再哈希法：同时构造多个不同的哈希函数，发生辩论时再换别的哈希函数

2. JDK1.7 实现原理

HashMap 由数组和链表实现对数据的存储，HashMap 里面实现一个静态内部类 Entry，包含 Key、Value 和对 key 的 hashcode 值举行 hash 运算后得到的 Hash 值，它还具有 Next 指针，可以毗连下一个 Entry 实体，以此来解决 Hash 辩论的问题
3. JDK1.7 存储流程

初始化哈希表：真正初始化哈希表（初始化存储数组）是在第一次添加键值对时
- 数组为空：设置默认阈值与初始容量
- 设置了传入容量：将传入的容量巨细转化为大于自身的最小的二次幂。如果超出最大允许容量，则设置为最大值
判断键是否为空：对 null 作哈希运算，结果为 0，以是以 null 为键的键值对一样平常放在数组首位，该位置的新值总是会覆盖旧值
计算元素存放位置：起首根据 key 的 hashcode 计算 hash 值，然后根据 hash 值计算 index 下标值
- 哈希辩论：当发生哈希辩论时，为了包管键的唯一性，哈希表不会马上在链表中插入新数据，而是先遍历链表，查找该键是否已存在，若已存在，替换即可
添加键值对：使用头插法，新添加元素放在链表头部，原始节点作为新节点的后继节点

4. JDK1.7 哈希函数

JDK 1.7 做了 9 次扰动处理 = 4 次位运算 + 5 次异或运算
5. JDK1.7 下标计算

计算元素位置接纳的是 & 运算，该方法返回 h & (length - 1)，此中 h 为 key 的 hash 值，length 是数组长度
6. JDK1.7 扩容机制

先判断是否需要扩容，再插入

7. JDK1.8 实现原理

1.8 以前 HashMap 接纳数组 + 链表实现，即使用链表处理辩论，同一 hash 值的节点都存储在一个链表里。但是当同一 hash 值相等的元素较多时，通过 key 值依次查找的服从较低。JDK1.8 中，HashMap 接纳数组 + 链表 + 红黑树实现，当链表长度超过阈值时，将链表转换为红黑树，大大镌汰了查找时间
8. JDK1.8 存储流程

初始化哈希表：真正初始化哈希表（初始化存储数组）是在第一次添加键值对时
- 数组为空：设置默认阈值与初始容量
- 设置了传入容量：将传入的容量巨细转化为大于自身的最小的二次幂。如果超出最大允许容量，则设置为最大值
判断键是否为空：对 null 作哈希运算，结果为 0，以是以 null 为键的键值对一样平常放在数组首位，该位置的新值总是会覆盖旧值
计算元素存放位置：起首根据 key 的 hashcode 计算 hash 值，然后根据 hash 值计算 index 下标值
- 哈希辩论：当发生哈希辩论时，为了包管键的唯一性，哈希表不会马上在链表中插入新数据，而是先遍历链表，查找该键是否已存在，若已存在，替换即可；如果不存在，判断当前节点范例是不是树型节点，如果是树型节点，创造树型节点插入红黑树中；如果不是树型节点，创建普通 Node 加入链表中；判断链表长度是否大于 8 并且数组长度大于 64，大于的话链表转换为红黑树
添加键值对：链表的插入方式从头插法改成了尾插法，简单说就是插入时，如果数组位置上已经有元素，1.7 将新元素放到数组中，原始节点作为新节点的后继节点，1.8 遍历链表，将元素放置到链表的最后

9. JDK1.8 哈希函数

JDK 1.8 简化了扰动函数 = 只做了 2 次扰动 = 1 次位运算 + 1 次异或运算，本质是哈希码的低 16 位异或高 16 位
10. JDK1.8 下标计算

计算元素位置接纳的是 & 运算，该方法返回 h & (length - 1)，此中 h 为 key 的 hash 值，length 是数组长度
11. JDK1.8 扩容机制

先举行插入，插入完成再判断是否需要扩容。扩容时，1.7 需要对原数组中的元素举行重新 hash 定位，以确定在新数组中的位置，1.8 接纳更简单的判断逻辑，位置稳定或索引 + 旧容量巨细

相关问题

1. 扩容机制？

HashMap 使用懒扩容机制，只有在举行 PUT 操作时才会判断是否扩容，需要用到的属性有两个：

阈值：threshold，初始容量为 16，扩容时需要使用
负载因子：loadFactor，默认是 0.75，用于减缓哈希辩论，如果等到数组满了才扩容，那是某些桶可能就不止一个元素了

阈值 = 数组巨细 * 负载因子，容器默认巨细为 16，此时阈值 = 16 * 0.75 = 12，如果当前数组中元素的数量大于阈值，则将数组巨细扩大为原来的两倍，并将原来数组中的元素举行重新放到新数组中。需要注意的是，每次扩容之后，都要重新计算元素在数组的位置，由于元素所在位置和数组长度有关，既然扩容后数组长度发生了变化，那么元素位置也会发生变化
2. 针对扩容机制的优化方案？

我们可以自界说数组容量及加载因子的巨细。加载因子过大时，HashMap 内的数组使用率高，内部极有可能形成 Entry 链，影响查找速度。加载因子过小时，HashMap 内的数组使用率低，内部不会天生 Entry 链，或者天生的 Entry 链很短，提高了查找速度，不过会占用更多的内存。以是要举行时间和空间的折中考虑
3. 为什么不直接使用 hashcode 作为存储数组的下标位置？

由于 key.hashCode() 函数调用的是 key 键值范例自带的哈希函数，返回 int 型散列值。int 值范围为非常大，前后加起来大概 40 亿的映射空间，一个 40 亿长度的数组，内存是放不下的。而且使用之前还需要对数组的长度取模运算，得到余数才能用来访问数组下标
4. 为什么要作扰动处理？

加大哈希码低位的随机性，使得分布更均匀，从而提高对应数组存储下标位置的随机性 & 均匀性，最终镌汰哈希辩论
5. 为什么接纳（哈希码 & 数组长度减一）这种方式？

这也解释了为什么 HashMap 的数组长度要取 2 的整数幂。由于数组长度减一恰好相称于一个低位掩码。与操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问，其结果与取模运算相同，服从却要高很多
6. 为什么在 1.8 使用尾插法插入新结点？

由于 1.7 扩容时，元素会被重新移动到新的数组，而使用头插法会使链表发生反转，好比原本是 A-B-C 的链表，扩容之后就酿成 C-B-A 了，在多线程情况下，会导致链表成环的问题。而尾插法，在扩容时会保持链表原本的顺序稳定，就不会出现链表成环的问题

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)