哈希表：散列查找

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