一、哈希表前传
1、TreeMap 的时间复杂度是多少？
- TreeMap 是基于红黑树实现的，所以增删改查时间复杂度都是：O(logn)
2、TreeMap 基于红黑树实现，那么 Key 需要具备什么特点？
- Key 必须具备可比性（因为二叉搜索树元素分布是有顺序的）
3、如果 Key 不考虑顺序，也不考虑可比性，Map 有没有更好的实现方案？
- 有：使用哈希表来实现
- 增删改查的平均时间复杂度可以达到 O(1)级别！！！
4、重要需求：使用电话号码(7位)作为 Key，存储厦门市所有居民的信息，要求增删改查的时间复杂度是 O(1)，说下实现思路？
- 做法：创建一个容量为【1000 0000】的数组，将电话号码作为索引，把居民信息存储在对应位置
- 这个巨大数组就是一个哈希表，哈希表是一个典型的
空间换时间的做法。 - 缺点：巨大数组的内存利用率极低，空间复杂度大，非常浪费内存空间。
image.png
二、哈希表相关的基本概念
1、哈希表的英文名称是什么？
- Hash Table
- hash 谐音
哈希，有剁碎、散列的含义
2、哈希表主要设计那三个对象？增删改查的主流程如何（两大步骤）？（重要）
- key、哈希函数、table
- 流程：①利用哈希函数生成 key 对应的 index【O(1)】；②根据 index 操作定位数组元素【O(1)】
image.png
3、什么是哈希冲突？哈希冲突常见的三种解决方案？
- 哈希冲突也叫做哈希碰撞：2 个不同的 key，经过哈希函数计算出相同的结果
- 常见三种解决方案：①开放定址法(Open Addressing) ②再哈希法(Re-Hashing) ③链地址法(Separate Chaining)
image.png
4、JDK1.8 的哈希冲突解决方案是什么？为什么使用单向链表？红黑树要有可比较性，但是哈希表不要求，这不是有冲突吗？
- JDK1.8 的哈希冲突解决方案是：使用链地址法（Separate Chaining），哈希冲突数量少时是单项链表，哈希冲突数数据量多时是红黑树。
- 为什么使用单向链表，而不是双向？因为只需要单向遍历，所以对比双向链表节约内存空间。
- 红黑树可比性问题如何解决：①hashCode ②类名 ③可比性(同类且有实现的情况下) ④内存地址
image.png
5、哈希表中的哈希函数实现步骤主要有哪两步？
- ① 先生成
key 的哈希值（必须是整数） - ② 再让
key 的哈希值跟数组的大小进行相关运算，生成一个索引值
image.png
6、为了提高效率，将数组的长度设计为 2 的幂(2^n)是为什么？
- 可以使用
&位运算取代%运算
7、什么是良好的哈希函数？
- 让哈希值更加均匀分部
- 尽量让每个 key 的哈希值是唯一的
- 尽量让 key 的所有信息参与运算
三、各种数据类型如何生成哈希值
1、int 和 float 如何生成哈希值？
- 整数：整数值当做哈希值，比如 10 的哈希值就是 10
- 浮点数：将存储的二进制格式转为整数值
image.png
2、long 和 double 如何生成哈希值？
- 高 32bit 和 低 32bit 混合计算出 32bit 的哈希值
- 充分利用所有信息计算出哈希值
image.png
3、字符串的哈希值如何计算？
image.png
4、自定义对象如何计算哈希值？
- 通常根据自定义对象内部的成员变量各自哈希值的叠加
image.png
5、为什么计算哈希值经常使用 31 这个数值？为什么不用 15？
-
31是一个奇素数，只能被 1 和自身整除，JVM 会将31 * i优化成(i << 5) - i - 31 * i = (2^5 - 1) * i = i * 2^5 - i = (i << 5) - i
- 素数和其他数相乘的结果比其他方式更容易产生唯一性，减少哈希冲突。
- 为什么不用
15：16 * i可以优化成(i << 4) - i，但是 15 不是素数，所以更容易产生哈希冲突。
6、为什么哈希值需要时 int 类型？
- 因为哈希表本质是数组，访问数组就需要索引，索引肯定是 int 类型丫
四、从理解 Java 中的 hashCode 和 equals 理解 哈希表（尽量能看懂即可）
1、Java 中 instanceof 和 getClass 的区别？
- getClass 用于判断当前类型的绝对匹配
- instanceof 当前类和当前类的子类都会囊括进去
2、Java 中自定义对象默认的哈希值是由什么决定的？
- 由内存地址参与哈希决定的
3、自定义对象的 hashCode 和 equals 基本实现如下：
image.png
4、为什么 Java 实现了 hashCode 还必须实现 equals 方法？
- 因为 Java 解决哈希冲突使用的是链地址法
- 链地址法会维护一个链表或者红黑树，此时需要用 equals 方法来判断两个发生冲突的对象，是否为同一个对象，从而决定是新增还是覆盖。
5、猜测下面 Map 的可能长度，从而验证是否掌握 hasCode 和 equals？
Person p1 = new Person(10, 1.67f, "jack");
Person p2 = new Person(10, 1.67f, "jack");
Map<Object, Object> map = new HashMap<>();
map.put(p1, "abc");
map.put("test", "ccc");
map.put(p2, "bcd");
System.out.println(map.size());
- 情况一：同时实现 hashCode 和 equals，输出：2
- 情况二：都不实现 hashCode 和 equals，可能输出：1、2、3
- 情况三：只实现 hashCode 不实现 equals，可能输出：3
- 情况四：不现实 hashCode 和 只实现equals，输出：2、3
五、哈希表代码实现细节记录
1、请问下面两段代码有区别吗？如果有，是什么区别？
//代码段一
void test(int h1, int h2) {
if (h1 > h2) {
//do xxx
} else {
//do yyy
}
}
//代码段二
void test2(int h1, int h2) {
int result = h1 - h2;
if (result > 0) {
//do xxx
} else {
//do yyy
}
}
- 上面两段代码运行效果有可能不一致
- 如果h1 是比较大的正数， h2 是比较大的负数，此时 value = h1 - h2 会导致 value 溢出，变成负数。这样就改变了该有的代码逻辑
2、使用哈希表实现 map，并没有要求 map 的 key 要具备可比较性。那么如何实现在 key 发生哈希冲突后，红黑树具备可比较性呢？
- ① 使用 hashCode 来比较。因为 hashCode 是 int 类型，天然具备可比较性。
- ② 比较 k1 和 k2 是否为同一个对象？如果是就相同
- ③ 使用是否同类别&&comparable 来比较
- ④ 上面三条都不行，实在没办法了，就比较内存地址（但是元素查找时，如果走到这步，需要使用遍历来查找）
- 上面的前三个步骤，即使省略 hashMap 也能正常运行。那为什么还需要前三步骤呢？
- 结论：如果代码达到第四步就要进行扫描了，会让红黑树的性能退化成链表，所以前三步骤目的是尽量减少扫描。
3、什么是装填因子？
- 装填因子(Load Factor)：节点总数量 / 哈希表桶数组长度，也叫做负载因子。
- 在 JDK1.8 的 HashMap 中，如果装填因子超过 0.75，就会扩容为原来的 2 倍？
4、如何对 HashMap 进行扩容？（4 大步骤，非常重要）
- ①在 HashMap 的 put 函数中，进行 resize()
- ②判断当前装填因子是否大于 0.75，如果大于就需要进行扩容
- ③将旧的 table 用临时变量存储起来，然后对 table 进行创建新数组并且 2倍(table.length << 1) 扩容
- ④将旧 table 的数组 move 到新的 table 中。（切记使用 move，不要创建新的节点，提升性能）
5、既然 HashMap 使用了红黑树或者链表去解决哈希冲突，那为什么我们还认为 HashMap 的增删改是 O(1)级别呢？
- 因为我们有装填因子的控制，而且装填因子是非常小的 0.75，所以我们可以认为节点基本上是均匀分布在 table 上的。
- 每个 bucket 上的节点数量是非常有限的常数项，所以 HashMap 的增删改是 O(1)级别的。
6、既然 HashMap 性能优于 TreeMap，我们是否永远选择 HashMap 就可以了呢？（非常重要）
- 何时选择 TreeMap：元素具备可比较性且要求升序遍历（按照元素从小到大）
- 何时选择 HashMap：元素无序存储
六、LinkedHashMap
1、什么是 LinkedHashMap？
- LinkedHashMap 是一个有记录插入顺序的 HashMap，遍历顺序按照插入顺序遍历
2、如果一定要用 % 号来计算索引，那么建议素组长度是多少？（一个小知识点，了解即可）
image.png
3、如果是你，如何基于 HashMap 设计一个 LinkedHashMap？
- 在 HashMap 的节点里面加入双向链表的思想，链表用于维护数据插入顺序
- 这里就出现一个很神奇的现象，用户插入数据即是 HashMap 的数据结构，也是双向链表的数据结构。（角度不同，看到的数据结构也就不同）
4、HashMap、LinkedHashMap、TreeMap 三种数据结构如何选择？（一定要能流利的回答）
- HashMap：效率最高、存储无序、遍历无序
- LinkedHashMap：效率其次、存储无序，遍历按插入顺序
- TreeMap：效率三者最低、存储有序，可从小到大遍历
5、HashSet 是基于什么实现的？
- HashSet 是基于 HashMap 实现的，将 map 的 value 部分置空即可。
七、效率测试
1、最终版本的：HashMap、TreeMap、LinkedHashMap 的效率对比
image.png
2、HashMap 去掉扩容代码运行效率
image.png
- 可以看到运行效率低了不少
3、HashMap 去掉扩容，并且每次查找都使用遍历查找（不发挥红黑树的优秀特性）
image.png
- 可以看到，相同的内容，消耗时间就长得很可怕了。体会到优秀数据结构的魅力了吗？（是的，体会到了~~~）
