如果所有的键都是小整数(hash算法可以协助我们转为小整数),我们可以用数组来存储并查找
散列表就是在此基础上发展而来的,可以使我们可以拥有常数级别的查找和插入
常见的散列表的实现就是并行数组的实现,一条保存键,一条保存值,利用散列函数来产生数组索引
利用算术操作符来将键转化成数组的索引来访问键值对
对应的,如果没有空间限制,可以直接将键作为一个超大数组的索引
如果没有时间限制,可以直接遍历无序数组
那么按照这个思路
将查找的步骤分为两步,
第一步,用散列函数将被查找的键转化成数组的索引,
第二部,处理键散列到相同值的情况,处理冲突
对应的实际方法就是拉链法和线性探测法
关于这两种方法的详细比较取决于用例对于时间和空间的需求,
拉链法为每个键值都分配了一小块内存而线性探测为整个表使用了两个很大的数组
最后在开始之前,说一下散列表的缺点,对于散列表来说,每个类型的键都需要一个优秀的散列函数
性能保证来自于散列函数的质量