[TOC] ## 一 线性查找 哈希表查找,是一种用空间换时间的查找算法,时间复杂度能达到:`O(1)`,最坏情况下退化到查找链表:`O(n)`。但均匀性很好的哈希算法以及合适空间大小的数组,在很大概率避免了最坏情况 哈希表在添加元素时会进行伸缩,会造成较大的性能消耗,所以有时候会用到其他的查找算法:树查找算法。 ## 二 散列查找 也称哈希查找,是一种空间换时间的查找算法, 依赖的数据结构称为哈希表或散列表:`HashTable` 散列查找: 1. 键进行`hash`计算得出一个大整数,然后与数组长度进行取余 2. 利用数组索引快的特征,用空间换时间的思路,使得查找的速度快于线性查找 3. 取数据时按同样的步骤进行查找。 有两种方式实现哈希表:线性探测法和拉链法。 ### 线性探测法 [不推荐] 线性探测法实现的哈希表是一个大数组。 首先,哈希表数据结构会初始化`N`个大小的数组,然后存取键`key`时,会求键的哈希值`hash(key)`,这是一个整数。然后与数组的大小进行取余:`hash(key)%N`,将会知道该键值对要存在数组的哪个位置。 如果数组该位置已经被之前的键值对占领了,也就是哈希冲突,那么会偏移加1,探测下个位置是否被占用,如果下个位置为空,那么占位,否则继续探测。查找时,也是查看该位置是否为该键,不是则继续往该位置的下一个位置查找。因为这个步骤是线性的,所以叫线性探测法。 ![](https://goa.lenggirl.com/picture/hash_table2.png) 因为线性探测法很少使用,我们接下来主要分析拉链法。 ### 哈希表:拉链法 拉链法实现的哈希表是一个数组链表,也就是数组中的元素是链表。数组链表很像一条条拉链,所以又叫拉链法查找。 首先,哈希表数据结构会初始化`N`个大小的数组,然后存取键`key`时,会求键的哈希值`hash(key)`,这是一个整数。然后与数组的大小进行取余:`hash(key)%N`,将会知道该键值对要存在数组的哪个位置。 如果数组该位置已经被之前的键值对占领了,也就是哈希冲突,那么键值对会追加到之前键值对的后面,形成一条链表。 比如键`51`的哈希`hash(51)`假设为`4`,那么`hash(51) % 4 = 4 % 4 = 0`,所以放在数组的第一个位置,同样键`43`的哈希`hash(43)`假设为`8`,那么`hash(43) % 4 = 8 % 4 = 0`,同样要放在数组的第一个位置。 因为哈希冲突了,所以键`43`链接在键`51`后面。 ![](https://goa.lenggirl.com/picture/hash_table.png) 查找的时候,也会继续这个过程,比如查找键`43`,进行哈希后得到位置`0`, 定位到数组第一位,然后遍历这条链表,先找到键`51`,发现不到,往下找,直到找到键`43`。 `Golang`内置的数据类型:字典`map`就是用拉链法的哈希表实现的,但相对复杂,感兴趣的可参考标准库`runtime`下的`map.go`文件。 ### 哈希函数 当哈希冲突十分严重的时候,每个数组元素对应的链表会越来越长,即使定位到数组的某个下标,也要遍历一条很长很长的链表,就退化为查找链表了,时间复杂度为:`O(n)`。 ![UTOOLS1588991050283.png](http://yanxuan.nosdn.127.net/f678c3f86b806d63a983b422729028c9.png) 实际上`hash(key) % len`的分布是和`len`有关的,一组均匀分布的`hash(key)`在`len`是素数时才能做到均匀,但是为了数组扩容和计算更方便,仍然还是使用`2^x`的数组长度 ### 实现拉链哈希表