面试常见问题之剖析哈希表

一、时间复杂度基础

- 时间复杂度是衡量算法效率的指标，用大O表示法（如O(1)、O(n)、O(n^2)）。数值越小，算法效率越高。
- O(1)：无循环的简单操作，如赋值、基本运算、数组下标访问。
- O(n)：单层循环操作，时间消耗随n线性增长。
- O(n^2)：嵌套双层循环操作，时间消耗随n平方增长。

二、哈希表底层结构与查找效率

- 哈希表底层物理结构是数组，利用数组下标访问的O(1)特性，实现哈希表查找的高效性。

三、哈希存储与哈希函数

- 存储数据时，通过**哈希函数（取模运算）**将数据映射到数组下标。例如数组长度为8时，数字5直接存在下标5的位置；数字8通过8 \% 8 = 0，存在下标0的位置。

四、哈希冲突

- 定义：不同数据经哈希函数映射后得到相同下标，导致冲突。如8、16、32对8取模都得0。
- 解决方法（链地址法）：将哈希冲突的元素串联成链表，哈希表升级为链表数组（数组每个元素是链表头指针）。

五、负载因子与Rehash

- 负载因子：公式为 元素个数 / 数组长度 。当负载因子过大（如大于5），哈希表会出现大量长链表，查找效率退化。
- Rehash（重新哈希）：数组扩容为原来的2倍，所有元素重新通过哈希函数映射，分散链表元素，避免长链表。
- 渐进式Rehash：避免一次性Rehash导致的性能波动，将Rehash过程分散到程序运行的多个阶段，逐步完成元素重新映射。

六、哈希表长度的优化

- 哈希表长度设计为2的幂，利用**位运算（与运算）**优化取模操作。因为x \% 2^n等价于x \& (2^n - 1)，位运算效率高于取模运算。