哈希表
基础
数组通过索引在 O(1)的时间复杂度内查找到对应元素,索引是一个非负整数。
哈希表通过 key 在 O(1)的时间复杂度内查找到这个 key 对应的 value。key 的类型可以是数字、字符串等多种类型。
哈希表的底层实现就是一个数组(我们不妨称之为 table)。它先把这个 key 通过一个哈希函数(我们不妨称之为 hash)转化成数组里面的索引,然后增删查改操作和数组基本相同:
// 哈希表伪码逻辑
class MyHashMap {
private:
vector<void*> table;
public:
// 增/改,复杂度 O(1)
void put(auto key, auto value) {
int index = hash(key);
table[index] = value;
}
// 查,复杂度 O(1)
auto get(auto key) {
int index = hash(key);
return table[index];
}
// 删,复杂度 O(1)
void remove(auto key) {
int index = hash(key);
table[index] = nullptr;
}
private:
// 哈希函数,把 key 转化成 table 中的合法索引
// 时间复杂度必须是 O(1),才能保证上述方法的复杂度都是 O(1)
int hash(auto key) {
// ...
}
};
常见的哈希函数
字符串
需要注意的几个点:
- 哈希表key唯一,value不唯一(类比数组索引和元素值)
-
哈希函数:把任意长度的输入(key)转化成固定长度的输出(索引)。哈希函数需要保证:
- 哈希函数的复杂度为O(1)。如果你设计的这个哈希函数复杂度是 O(N),那么哈希表的增删查改性能就会退化成 O(N)
- 输入相同的
key,输出也必须要相同。
-
哈希冲突:如果两个不同的
key通过哈希函数得到了相同的索引- 哈希冲突是一定会出现的。因为这个
hash函数相当于是把一个无穷大的空间映射到了一个有限的索引空间,所以必然会有不同的key映射到同一个索引上。
-
解决哈希冲突的方法
- 拉链法(纵向):哈希表的底层数组并不直接存储
value类型,而是存储一个链表,当有多个不同的key映射到了同一个索引上,这些key -> value对儿就存储在这个链表中,这样就能解决哈希冲突的问题。 - 线性探查法(开放寻址法)(横向):一个
key发现算出来的index值已经被别的key占了,那么它就去index + 1的位置看看,如果还是被占了,就继续往后找,直到找到一个空的位置为止
- 拉链法(纵向):哈希表的底层数组并不直接存储
-
那么为什么会频繁出现哈希冲突:
- 哈希函数设计的不好,导致
key的哈希值分布不均匀,很多key映射到了同一个索引上。 - 哈希表里面已经装了太多的
key-value对了,这种情况下即使哈希函数再完美,也没办法避免哈希冲突。
对于第一个问题没什么好说的,开发编程语言标准库的大佬们已经帮你设计好了哈希函数,你只要调用就行了。
对于第二个问题是我们可以控制的,即避免哈希表装太满,这就引出了「负载因子」的概念。
- 哈希函数设计的不好,导致
- 哈希冲突是一定会出现的。因为这个
「负载因子」
负载因子是一个哈希表装满的程度的度量。一般来说,负载因子越大,说明哈希表里面存储的 key-value 对越多,哈希冲突的概率就越大,哈希表的操作性能就越差。
负载因子的计算公式也很简单,就是 size / table.length。其中 size 是哈希表里面的 key-value 对的数量,table.length 是哈希表底层数组的容量。
你不难发现,用拉链法实现的哈希表,负载因子可以无限大,因为链表可以无限延伸;用线性探查法实现的哈希表,负载因子不会超过 1。
像 Java 的 HashMap,允许我们创建哈希表时自定义负载因子,不设置的话默认是 0.75,这个值是经验值,一般保持默认就行了。
当哈希表内元素达到负载因子时,哈希表会扩容。和之前讲解 动态数组的实现 是类似的,就是把哈希表底层 table 数组的容量扩大,把数据搬移到新的大数组中。size 不变,table.length 增加,负载因子就减小了。
为什么不能依赖哈希表的遍历顺序
首先,由于 hash 函数要把你的 key 进行映射,所以 key 在底层 table 数组中的分布是随机的,不像数组/链表结构那样有个明确的元素顺序。
其次,刚才讲了哈希表达到负载因子时会怎样?会扩容对吧,也就是 table.length 会变化,且会搬移元素。
那么这个搬移数据的过程,是不是要用 hash 函数重新计算 key 的哈希值,然后放到新的 table 数组中?
而这个 hash 函数,它计算出的值依赖 table.length。也就是说,哈希表自动扩容后,同一个 key 的哈希值可能变化,即这个 key-value 对儿存储在 table 的索引也变了,所以遍历结果的顺序就和之前不一样了。
面试常考问题
1、为什么我们常说,哈希表的增删查改效率都是 O(1)?
因为哈希表底层就是操作一个数组,其主要的时间复杂度来自于哈希函数计算索引和哈希冲突。只要保证哈希函数的复杂度在 O(1)O(1),且合理解决哈希冲突的问题,那么增删查改的复杂度就都是 O(1)。
2、哈希表的遍历顺序为什么会变化?
因为哈希表在达到负载因子时会扩容,这个扩容过程会导致哈希表底层的数组容量变化,哈希函数计算出来的索引也会变化,所以哈希表的遍历顺序也会变化。
3、哈希表的增删查改效率一定是 O(1)吗?
不一定,正如前面分析的,只有哈希函数的复杂度是 O(1),且合理解决哈希冲突的问题,才能保证增删查改的复杂度是 O(1)。
哈希冲突好解决,都是有标准答案的。关键是哈希函数的计算复杂度。如果使用了错误的 key 类型,比如前面用 ArrayList 作为 key 的例子,那么哈希表的复杂度就会退化成 O(N)。
4、为啥一定要用不可变类型作为哈希表的 key?
因为哈希表的主要操作都依赖于哈希函数计算出来的索引,如果 key 的哈希值会变化,会导致键值对意外丢失,产生严重的 bug。