数据结构 --- 散列表
Why
散列表是数组的升级版, 在数组中, 我们可以使用整数索引作为key, 而在散列表中, 我们可以使用任意的类型作为key.
当然这其中需要一个转化: AnyType –> Int, 而这个转化函数就是散列函数.
散列冲突
AnyType –> Int 这个散列函数中, 由于数组是定长的, 而AnyType是无限的, 所以可能出现不同的AnyType 会散列到相同的 Int, 解决冲突的最简单的两种方法是:
分离链表法
在冲突的位置创建新的链表, 这样一次查表就转化为hash + 遍历.
探测法
如C所示, 如果发生冲突, 那么就从冲突的位置开始接着往下找, 直到出现空位.
再散列
类似与列表的扩容, 当table 中的数据过多时, 冲突会越来越频繁, 所以在装填一定的数据后我们需要把table 扩容, 然后把数据拷贝到新table中