哈希表

哈希表

哈希表又称散列表，一种以「key-value」形式存储数据的数据结构，可以理解为一种另类的数组

哈希函数

为了让键和值一一对应，实现这个条件的方法就被叫做哈希函数或者叫散列函数。

image-20231006163339659

哈希函数应当易于计算，并且尽量使计算出来的索引均匀分布。

假设我们用数组 a 存放数据，哈希函数是 f，那键值对 (key, value) 就应该放在 a[f(key)] 上。不论键值是什么类型，范围有多大，f(key) 都是在可接受范围内的整数，可以作为数组的下标。

冲突的解决

如果对于任意的键值，哈希函数计算出来的索引都不相同，那只用根据索引把 (key, value) 放到对应的位置就行了。但实际上，常常会出现两个不同的键值，他们用哈希函数计算出来的索引是相同的。这时候就需要一些方法来处理冲突。

拉链法（常用）

在存值的地方开链表，把所有key相同的都放进去，需要的时候都遍历一遍。

image-20231006171406553

闭散列法

闭散列方法把所有记录直接存储在散列表中，如果发生冲突则根据某种方式继续进行探查。

有线性探测法、二次探测法、双哈希法

结束

此外还有哈希表的删除问题