B站河北王校长-精华-深度核心面试知识点汇总.pdf

简介：
本PDF汇集了针对B站UP主“王校长”进行深度核心面试的知识点和精华内容，适合希望了解互联网行业发展趋势及新媒体运营技巧的学习者。 ### JAVA容器概述 #### Collection与Map的分类及继承体系 JAVA容器主要分为两大类：`Collection` 和 `Map`。 1. **Collection**：这是所有单列集合的根接口，主要包括 `List`、`Set` 等子接口。 - `List`：有序集合，允许重复元素。主要有 `ArrayList`、`LinkedList` 等实现类。 - `Set`：不允许重复元素的集合，主要有 `HashSet`、`TreeSet` 等实现类。 2. **Map**：键值对集合，主要用于存储键值对数据。主要包括 `HashMap`、`TreeMap` 等实现类。 #### HashMap详解 ##### 数据结构 `HashMap` 是一种基于哈希表的 `Map` 容器，它提供了快速的插入和查找操作。 - **内部结构**：`HashMap` 底层使用了一个 `Entry` 对象数组。每个 `Entry` 对象包含了键、值、哈希值以及指向下一个元素的引用。 - **数组与链表**：每个数组索引位置上的元素是以链表的形式存储的，即同一个索引位置上的多个元素通过链表连接起来。 ##### put 方法实现原理 1. **JDK7 与 JDK8 的区别**： - **JDK7**：采用位桶+链表的方式。当链表长度超过一定阈值时不会转化为红黑树。 - **JDK8**：引入了红黑树优化。当链表长度超过一定阈值时（默认为 8），会将链表转换成红黑树，以提高查找效率。 2. **插入过程**： - 计算键的哈希值。 - 根据哈希值找到数组中的索引位置。 - 如果该位置为空，则创建一个新的 `Entry` 对象并插入。 - 若该位置不为空，则遍历链表或红黑树，根据键的相等性判断是否已有相同的键存在。若有则更新对应的值；若没有，则在链表头部或红黑树中插入新的 `Entry` 对象。 3. **负载因子与扩容**： - `HashMap` 有一个默认的负载因子为0.75，当容器容量达到（当前容量*负载因子）时，就会触发扩容机制。 - 扩容时会将原来的数据重新哈希并放置到新的数组中。 ##### put 方法参数 hash 的计算 1. **当 key 为 null 时**： - `HashMap` 允许键为 `null`。此时，hash 值为0。 2. **当 key 非空时**： - 计算 `key.hashCode()`。 - 使用扰动函数：`h ^= h >>> 16`（其中 `h` 是 `key.hashCode()` 的值）。 - 扰动函数的作用在于使高位参与低位的运算，从而使得不同对象的哈希值分布更均匀。 ##### 计算数据下标的方法 1. **计算公式**： - `index = (n - 1) & hash`。其中 n 是 `HashMap` 数组长度，hash 是键的哈希值。 2. **为什么要进行右移16位的异或运算**： - 为了使低位的哈希值更加随机以减少碰撞。 - `h >>> 16` 提取了 `h` 的高16位。通过将高16位与低16位进行异或操作，可以增加哈希值的随机性，进一步降低冲突概率。 3. **示例解析**： - 假设长度为8，则 `(length - 1)` 转换为二进制是 `111`。 - 若键的 `hashcode = 78897121`（转换成二进制为 `1001011001111011...`）。 - 进行按位与运算的结果为 `001`，通过让哈希值的低位与高位进行异或操作，可以提高索引分散性。 ### 总结 通过上述分析可以看出，`HashMap` 设计巧妙地结合了数组和链表（红黑树）的优势以提供高效的数据存储和检索功能。在设计过程中通过对哈希值的精心处理以及合理的扩容策略有效避免了哈希冲突的发生，并保证良好的性能表现。这对于理解和掌握 `HashMap` 的工作原理及其实际应用具有重要意义。