樟木头东莞网站建设深圳网络推广方法
目录
HashMap是什么？
为什么要使用HashMap？
HashMap存储元素原理（put⽅法）
扰动函数
前置知识
异或运算
&运算
为什么使用扰动函数
实验验证扰动函数
常见问题
HashMap的默认长度是多少？
HashMap是先扩容在插入数据还是先插数据在扩容
HashMap链表转红黑树 和 红黑树退化为链表的条件分别是什么
HashMap链表转红黑树
HashMap红黑树退化成链表
HashMap和Hashtable的区别
HashMap的搜索的时间复杂度是多少？
HashMap是什么？
- JDk1.7：HashMap 数据结构为 数组+链表（JDk1.7）。
- JDK1.8中增加了红黑树，其中：链表的节点存储的是一个 Entry 对象，每个Entry 对象存储四个属性（hash，key，value，next） 。
为什么要使用HashMap？
对于要求查询次数特别多，查询效率比较高同时插入和删除的次数比较少的情况下，通常会选择ArrayList，因为它的底层是通过数组实现的。对于插入和删除次数比较多同时在查询次数不多的情况下，通常会选择LinkedList，因为它的底层是通过链表实现的。
但现在同时要求插入，删除，查询效率都很高的情况下我们该如何选择容器呢？
那么就有一种新的容器叫HashMap，他里面既有数组结构，也有链表结构，所以可以弥补相互的缺点。而且HashMap主要用法是get()和put() 。
HashMap存储元素原理（put⽅法）
扰动函数
在HashMap存放元素时候有这样一段代码来处理哈希值，这是java 8的散列值扰动函数，用于优化散列效果；
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}前置知识
异或运算
异或运算是一种布尔运算，通常表示为符号“^”，它的结果为两个操作数相应位上的数值相异或得到的值。如果两个相应位的值相同，则结果为0，否则结果为1。具体来说，如果输入的两个二进制数的某一位相同，则该位上的异或结果为0，否则为1。
&运算
&运算是位运算符之一，用来执行按位与操作。它对两个操作数的每一位执行逻辑“与”操作，即如果两个操作数的对应位都是1，则结果为1，否则为0。&运算符通常用于处理二进制数据，例如在编程语言中进行位操作。
为什么使用扰动函数
理论上来说字符串的hashCode是一个int类型值，那可以直接作为数组下标了，且不会出现碰撞。但是这个hashCode的取值范围是[-2147483648, 2147483647]，有将近40亿的长度，谁也不能把数组初始化的这么大，内存也是放不下的。
我们默认初始化的Map大小是16个长度 DEFAULT_INITIAL_CAPACITY = 1 << 4，所以获取的Hash值并不能直接作为下标使用，需要与数组长度进行取模运算得到一个下标值，也就是我们上面做的散列列子。
那么，hashMap源码这里不只是直接获取哈希值，还进行了一次扰动计算，(h = key.hashCode()) ^ (h >>> 16)。把哈希值右移16位，也就正好是自己长度的一半，之后与原哈希值做异或运算，这样就混合了原哈希值中的高位和低位，增大了随机性。计算方式如下图；
说白了，使用扰动函数就是为了增加随机性，让数据元素更加均衡的散列，减少碰撞。
从上面的分析可以看出，扰动函数使用了哈希值的高半区和低半区做异或，混合原始哈希码的高位和低位，以此来加大低位区的随机性。
但看不到实验数据的话，这终究是一段理论，具体这段哈希值真的被增加了随机性没有，并不知道。所以这里我们要做一个实验，这个实验是这样做；
选取10万个单词词库
定义128位长度的数组格子
分别计算在扰动和不扰动下，10万单词的下标分配到128个格子的数量
统计各个格子数量，生成波动曲线。如果扰动函数下的波动曲线相对更平稳，那么证明扰动函数有效果。
实验验证扰动函数
扰动函数对比方法
public class Disturb {public static int disturbHashIdx(String key, int size) {return (size - 1) & (key.hashCode() ^ (key.hashCode() >>> 16));}public static int hashIdx(String key, int size) {return (size - 1) & key.hashCode();}}- disturbHashIdx 扰动函数下，下标值计算
- hashIdx 非扰动函数下，下标值计算
单元测试
// 10万单词已经初始化到words中
@Test
public void test_disturb() {Map<Integer, Integer> map = new HashMap<>(16);for (String word : words) {// 使用扰动函数int idx = Disturb.disturbHashIdx(word, 128);// 不使用扰动函数// int idx = Disturb.hashIdx(word, 128);if (map.containsKey(idx)) {Integer integer = map.get(idx);map.put(idx, ++integer);} else {map.put(idx, 1);}}System.out.println(map.values());
}以上分别统计两种函数下的下标值分配，最终将统计结果放到excel中生成图表。
扰动函数散列图表
以上的两张图，分别是没有使用扰动函数和使用扰动函数的，下标分配。实验数据；
- 10万个不重复的单词
- 128个格子，相当于128长度的数组
未使用扰动函数
使用扰动函数
- 从这两种的对比图可以看出来，在使用了扰动函数后，数据分配的更加均匀了。
- 数据分配均匀，也就是散列的效果更好，减少了hash的碰撞，让数据存放和获取的效率更佳。
常见问题
HashMap的默认长度是多少？
严格意义说，HashMap的默认长度是0，但是长度为0的时候，第一次插入数据的时候若判断当前长度为0则直接扩容到16.leng
HashMap是先扩容在插入数据还是先插数据在扩容
- 若判断长度=0时则是先扩容再插入数据
- 若长度不为0则是先插入数据再扩容
HashMap链表转红黑树 和 红黑树退化为链表的条件分别是什么
先展示一下HashMap里的三个常量
HashMap链表转红黑树
- 链表的节点数量(包括新增节点)大于等于树化阈值
- HashMap的容量(Node数组的长度)大于等于最小树化容量值。
（延伸题） 若链表节点数超过树化阈值，但是HashMap的容量小于树化容量会如何？
会进行一次扩容，使其大于或等于最小束花容量值，随后在进行树化
HashMap红黑树退化成链表
当红黑树中的元素个数小于等于6时，该红黑树会被转换为链表。这是因为，当元素数量较少时，红黑树的性能反而会不如链表。
HashMap和Hashtable的区别
| HashMap | Hashtable | |
| 父类 | 继承AbstractMap，AbstractMap又实现了 Map 接口 | Hashtable 继承了 Dictionary 并实现Map接口 |
| 默认值不同 | 默认的初始数组长度是 16， 默认的加载因子是 0.75， 每次扩容变成之前数组的 2 倍长度 | 默认的初始数组长度是 11， 默认的加载因子是 0.75， 每次扩容是之前数组的 2 倍长度加 1 |
| 空值 | 只能有一个key为空 允许value为空。 | key，value 都不允许为空。 |
| 获取数组下标的方式 |
|
|
| 底层数据结构不同 | 数组+链表+红黑树 | 数组+链表 |
| 线程安全问题 | false | true |
HashMap的搜索的时间复杂度是多少？
若不hash冲突则是：O(1)
链表则是：O(n)
红黑树是：O(logn)