哈希表：散列查找

    这种链表查找，最坏的时间复杂度为：O(n)，因为可能遍历到链表最后也没找到。

    二、散列查找

    有一种算法叫散列查找，也称哈希查找，是一种空间换时间的查找算法，依赖的数据结构称为哈希表或散列表：HashTable。

    散列查找，主要是将键进行 hash 计算得出一个大整数，然后与数组长度进行取余，这样一个比较大的域空间就只会映射到数组的下标范围，利用数组索引快的特征，用空间换时间的思路，使得查找的速度快于线性查找。

    首先有一个大数组，每当存一个键值对时，先把键进行哈希，计算出的哈希值是一个整数，使用这个整数对数组长度取余，映射到数组的某个下标，把该键值对存起来，取数据时按同样的步骤进行查找。

    有两种方式实现哈希表：线性探测法和拉链法。

    线性探测法实现的哈希表是一个大数组。

    首先，哈希表数据结构会初始化 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 后面。

    哈希表：散列查找 - 图2

    查找的时候，也会继续这个过程，比如查找键 43，进行哈希后得到位置 0， 定位到数组第一位，然后遍历这条链表，先找到键 51，发现不到，往下找，直到找到键 43。

    Golang 内置的数据类型：字典 map 就是用拉链法的哈希表实现的，但相对复杂，感兴趣的可参考标准库 runtime 下的 map.go 文件。

    当哈希冲突不严重的时候，查找某个键，只需要求哈希值，然后取余，定位到数组的某个下标即可，时间复杂度为：O(1)。

    当哈希冲突十分严重的时候，每个数组元素对应的链表会越来越长，即使定位到数组的某个下标，也要遍历一条很长很长的链表，就退化为查找链表了，时间复杂度为：O(n)。

    所以哈希表首先要解决的问题是寻找相对均匀，具有很好随机分布性的哈希函数 hash()，这样才不会扎堆冲突。

    Golang 语言实现的哈希函数参考了以下两种哈希算法：

    1. xxhash:
    2. cityhash: https://code.google.com/p/cityhash

    当然还有其他哈希算法如 MurmurHash: 。

    还有哈希算法如 Md4 和 Md5 等。

    因为研究均匀随机分布的哈希算法，是属于数学专家们的工作，我们在此不展开了。

    我们使用号称计算速度最快的哈希 xxhash，我们直接用该库来实现哈希：https://github.com/OneOfOne/xxhash：

    实现如下:

    输出：

    1. xxhash('hi')=16899831174130972922
    2. xxhash('my')=13223332975333369668
    3. xxhash('friend')=4642001949237932008
    4. xxhash('I')=12677399051867059349
    5. xxhash('love')=12577149608739438547
    6. xxhash('you')=943396405629834470
    7. xxhash('my')=13223332975333369668
    8. xxhash('apple')=6379808199001010847

    拿到哈希值之后，我们要对结果取余，方便定位到数组下标 index。如果数组的长度为 len，那么 index = xxhash(key) % len。

    我们已经寻找到了计算较快，且均匀随机分布的哈希算法 xxhash 了，现在就是要解决取余操作中的数组长度选择的问题，数组的长度 len 应该如何选择？

    比如数组长度 len=8，那么取余之后可能有这些结果:

    1. xxhash(key) % 8 = 0，1，2，3，4，5，6，7

    如果我们选择 2^x 作为数组长度有一个很好的优点，就是计算速度变快了，如下是一个恒等式：

    1. 恒等式 hash % 2^k = hash & (2^k-1)，表示截断二进制的位数，保留后面的 k 位

    这样取余 % 操作将变成按位 & 操作：

    1. 哈希表数组长度 len=8，
    2. 存在一个哈希值 hash=165，二进制表示为 1010 0101
    4. 所以： 
    6. 165 % 8 
    7. = 165 % 2^3
    8. = 165 & (2^3-1)
    9. = 165 & 7
    10. = 1010 0101 & 0000 0111 
    11. = 0000 0000 0101 
    12. = 5

    选择 2^x 长度会使得计算速度更快，但是相当于截断二进制后保留后面的 k 位，如果存在很多哈希值的值很大，位数超过了 k 位，而二进制后 k 位都相同，那么会导致大片哈希冲突。

    即使如此，存在很大哈希值的情况很少发生，大部分哈希值的二进制位数都不会超过 k 位，因此编程语言 Golang 使用了这种 2^x 长度作为哈希表的数组长度。

    实际上 hash(key) % len 的分布是和 len 有关的，一组均匀分布的 hash(key) 在 len 是素数时才能做到均匀。

    素数(prime number)，也叫质数，是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数，也就是与任何数的最大公约数都为1。

    举例如下：

    1. f(n)为哈希表的下标，哈希表的长度是 m，而哈希值是 n，记 w=gcd(m,n) 为两个数的最大公约数，
    3. 那么：
    5. f(n) = n % m 
    6.      = n - a*m (a=0,1,2,3,4...)
    7.      = w * (n/w-a*m/w)
    9. 因为 w=gcd(m,n)，所以 (n/w-a*m/w) 是一个整数。
    11. 所以哈希表的下标 f(n) 只会是 w=gcd(m,n) 的倍数，倍数就注定了不会均匀分布在 `[0,m-1]`，除非 w=1。
    13. 在哈希值数列数量特别多的情况，对偶数和奇数数列进行取余求下标，如长度 m=5 和 m=6：
    15. 哈希数值：2 4 6 8 10 12 14 16 18 20 22...
    16. m=5时下标：2 4 1 3 0 2 4 1 3 0 2...
    17. m=6时下标：2 4 0 2 4 0 2 4 0 2 4...
    19. 哈希数值：1 3 5 7 9 11 13 15 17...
    20. m=5时下标：1 3 0 2 4 1 3 0 2...
    21. m=6时下标：1 3 5 1 3 5 1 3 5...
    23. 偶数队列可以看到素数5一直重复 `2 4 1 3 0`，而合数6一直重复 `2 4 0`，只有素数均匀分布。
    25. 奇数队列可以看到素数5一直重复 `1 3 0 2 4`，而合数6一直重复 `1 3 5`，只有素数均匀分布。
    27. 将偶数和奇数数列合并起来，步长为1时，素数和奇数都一样均匀，仅当步长不为1时的随机数列，素数会更均匀点。

    我们实现拉链哈希表的时候，为了数组扩容和计算更方便，仍然还是使用 2^x 的数组长度。

    六、实现拉链哈希表

    我们将实现一个简单的哈希表版本。

    实现拉链哈希表有以下的一些操作：

    1. 初始化：新建一个 2^x 个长度的数组，一开始 x 较小。
    2. 添加键值：进行 hash(key) & (2^x-1)，定位到数组下标，查找数组下标对应的链表，如果链表有该键，更新其值，否则追加元素。
    3. 获取键值：进行 hash(key) & (2^x-1)，定位到数组下标，查找数组下标对应的链表，如果链表不存在该键，返回 false，否则返回该值以及 true。
    4. 删除键值：进行 hash(key) & (2^x-1)，定位到数组下标，查找数组下标对应的链表，如果链表不存在该键，直接返回，否则删除该键。
    5. 进行键值增删时如果数组容量太大或者太小，需要相应缩容或扩容。

    哈希查找的速度快，主要是利用空间换时间的优点。如果哈希表的数组特别大特别大，那么哈希冲突的几率就会降低。然而哈希表中的数组太大或太小都不行，太大浪费了空间，太小则哈希冲突太严重，所以需要对哈希表中的数组进行缩容和扩容。

    如何伸缩主要根据哈希表的大小和已添加的元素数量来决定。假设哈希表的大小为 16，已添加到哈希表中的键值对数量是 8，我们称 8/16=0.5 为加载因子 factor。

    我们可以设定加载因子 factor <= 0.125 时进行数组缩容，每次将容量砍半，当加载因子 factor >= 0.75 进行数组扩容，每次将容量翻倍。

    大部分编程语言实现的哈希表只会扩容，不会缩容，因为对于一个经常访问的哈希表来说，缩容后会很快扩容，造成的哈希搬迁成本巨大，这个成本比起存储空间的浪费还大，所以我们在这里只实现哈希表扩容。

    我们使用结构体 HashMap 来表示哈希表：

    1. const (
    2.     // 扩容因子
    3.     expandFactor = 0.75
    4. )
    6. // 哈希表
    7. type HashMap struct {
    8.     array        []*keyPairs // 哈希表数组，每个元素是一个键值对
    9.     capacity     int         // 数组容量
    10.     len          int         // 已添加键值对元素数量
    11.     capacityMask int         // 掩码，等于 capacity-1
    12.     // 增删键值对时，需要考虑并发安全
    13.     lock sync.Mutex
    14. }
    16. // 键值对，连成一个链表
    17. type keyPairs struct {
    18.     key   string      // 键
    19.     value interface{} // 值
    20.     next  *keyPairs   // 下一个键值对
    21. }

    其中 array 为哈希表数组，capacity 为哈希表的容量，capacityMask 为容量掩码，主要用来计算数组下标，len 为实际添加的键值对元素数量。

    我们还使用了 lock 来实现并发安全，防止并发增删元素时数组伸缩，产生混乱。

    使用 expandFactor = 0.75 作为扩容因子，没什么其他的理由，只是它刚刚好，你也可以设置成 等任何值。

    1. // 创建大小为 capacity 的哈希表
    2. func NewHashMap(capacity int) *HashMap {
    3.     // 默认大小为 16
    4.     defaultCapacity := 1 << 4
    5.     if capacity <= defaultCapacity {
    6.         // 如果传入的大小小于默认大小，那么使用默认大小16
    7.         capacity = defaultCapacity
    8.     } else {
    9.         // 否则，实际大小为大于 capacity 的第一个 2^k
    10.         capacity = 1 << (int(math.Ceil(math.Log2(float64(capacity)))))
    11.     }
    13.     // 新建一个哈希表
    14.     m := new(HashMap)
    15.     m.array = make([]*keyPairs, capacity, capacity)
    16.     m.capacity = capacity
    17.     m.capacityMask = capacity - 1
    18.     return m
    19. }
    21. // 返回哈希表已添加元素数量
    22. func (m *HashMap) Len() int {
    23.     return m.len
    24. }

    我们可以传入 capacity 来初始化当前哈希表数组容量，容量掩码 capacityMask = capacity-1 主要用来计算数组下标。

    如果传入的容量小于默认容量 16，那么将 16 作为哈希表的初始数组大小。否则将第一个大于 capacity 的 2 ^ k 值作为数组的初始大小。

    6.2. 计算哈希值和数组下标

    首先，为结构体生成一个 hashIndex 方法。

    根据公式 hash(key) & (2^x-1)，使用 xxhash 哈希算法来计算键 key 的哈希值，并且和容量掩码 mask 进行 & 求得数组的下标，用来定位键值对该放在数组的哪个下标下。

    1. // 哈希表添加键值对
    2. func (m *HashMap) Put(key string, value interface{}) {
    3.     // 实现并发安全
    4.     defer m.lock.Unlock()
    6.     // 键值对要放的哈希表数组下标
    7.     index := m.hashIndex(key, m.capacityMask)
    9.     // 哈希表数组下标的元素
    10.     element := m.array[index]
    12.     // 元素为空，表示空链表，没有哈希冲突，直接赋值
    13.     if element == nil {
    14.         m.array[index] = &keyPairs{
    15.             key:   key,
    16.             value: value,
    17.         }
    18.     } else {
    19.         // 链表最后一个键值对
    20.         var lastPairs *keyPairs
    22.         // 遍历链表查看元素是否存在，存在则替换值，否则找到最后一个键值对
    23.         for element != nil {
    24.             // 键值对存在，那么更新值并返回
    25.             if element.key == key {
    26.                 element.value = value
    27.                 return
    28.             }
    30.             lastPairs = element
    31.             element = element.next
    32.         }
    34.         // 找不到键值对，将新键值对添加到链表尾端
    35.         lastPairs.next = &keyPairs{
    36.             key:   key,
    37.             value: value,
    38.         }
    39.     }
    41.     // 新的哈希表数量
    42.     newLen := m.len + 1
    44.     // 如果超出扩容因子，需要扩容
    45.     if float64(newLen)/float64(m.capacity) >= expandFactor {
    46.         // 新建一个原来两倍大小的哈希表
    47.         newM := new(HashMap)
    48.         newM.array = make([]*keyPairs, 2*m.capacity, 2*m.capacity)
    49.         newM.capacity = 2 * m.capacity
    50.         newM.capacityMask = 2*m.capacity - 1
    52.         // 遍历老的哈希表，将键值对重新哈希到新哈希表
    53.         for _, pairs := range m.array {
    54.             for pairs != nil {
    55.                 // 直接递归Put
    56.                 newM.Put(pairs.key, pairs.value)
    57.                 pairs = pairs.next
    58.             }
    59.         }
    61.         // 替换老的哈希表
    62.         m.array = newM.array
    63.         m.capacity = newM.capacity
    64.         m.capacityMask = newM.capacityMask
    65.     }
    67.     m.len = newLen
    68. }

    首先使用锁实现了并发安全：

    1.     m.lock.Lock()
    2.     defer m.lock.Unlock()

    接着使用哈希算法计算出数组的下标，并取出该下标的元素：

    1.     // 键值对要放的哈希表数组下标
    2.     index := m.hashIndex(key, m.capacityMask)
    4.     // 哈希表数组下标的元素
    5.     element := m.array[index]

    如果该元素为空表示链表是空的，不存在哈希冲突，直接将键值对作为链表的第一个元素：

    1.     // 元素为空，表示空链表，没有哈希冲突，直接赋值
    2.     if element == nil {
    3.         m.array[index] = &keyPairs{
    4.             key:   key,
    5.             value: value,
    6.         }
    7.     }

    否则，则遍历链表，查找键是否存在：

    1.         // 链表最后一个键值对
    2.         var lastPairs *keyPairs
    4.         // 遍历链表查看元素是否存在，存在则替换值，否则找到最后一个键值对
    5.         for element != nil {
    6.             // 键值对存在，那么更新值并返回
    7.             if element.key == key {
    8.                 element.value = value
    9.                 return
    10.             }
    12.             lastPairs = element
    13.             element = element.next
    14.         }

    当 element.key == key ，那么键存在，直接更新值，退出该函数。否则，继续往下遍历。

    当跳出 for element != nil 时，表示找不到键值对，那么往链表尾部添加该键值对：

    1.         // 找不到键值对，将新键值对添加到链表尾端
    2.         lastPairs.next = &keyPairs{
    3.             key:   key,
    4.             value: value,
    5.         }

    最后，检查是否需要扩容，如果需要则扩容：

    1.          // 新的哈希表数量
    2.          newLen := m.len + 1
    4.          // 如果超出扩容因子，需要扩容
    5.          if float64(newLen)/float64(m.capacity) >= expandFactor {
    6.              // 新建一个原来两倍大小的哈希表
    7.              newM := new(HashMap)
    8.              newM.array = make([]*keyPairs, 2*m.capacity, 2*m.capacity)
    9.              newM.capacity = 2 * m.capacity
    10.              newM.capacityMask = 2*m.capacity - 1
    13.              for _, pairs := range m.array {
    14.                  for pairs != nil {
    15.                      // 直接递归Put
    16.                      newM.Put(pairs.key, pairs.value)
    17.                      pairs = pairs.next
    18.                  }
    19.              }
    21.              // 替换老的哈希表
    22.              m.capacity = newM.capacity
    23.              m.capacityMask = newM.capacityMask
    24.          }
    26.          m.len = newLen

    创建了一个新的两倍大小的哈希表：newM := new(HashMap)，然后遍历老哈希表中的键值对，重新 Put 进新哈希表。

    最后将新哈希表的属性赋予老哈希表。

    6.3. 获取键值对

    同样先加锁实现并发安全，然后进行哈希算法计算出数组下标：index := m.hashIndex(key, m.capacityMask)，取出元素：element := m.array[index]。

    对链表进行遍历：

    1.     // 遍历链表查看元素是否存在，存在则返回
    2.     for element != nil {
    3.         if element.key == key {
    4.             return element.value, true
    5.         }
    7.         element = element.next
    8.     }

    如果键在哈希表中存在，返回键的值 element.value 和 true。

    1. // 哈希表删除键值对
    2. func (m *HashMap) Delete(key string) {
    3.     // 实现并发安全
    4.     m.lock.Lock()
    5.     defer m.lock.Unlock()
    7.     // 键值对要放的哈希表数组下标
    8.     index := m.hashIndex(key, m.capacityMask)
    10.     // 哈希表数组下标的元素
    11.     element := m.array[index]
    13.     // 空链表，不用删除，直接返回
    14.     if element == nil {
    15.         return
    16.     }
    18.     // 链表的第一个元素就是要删除的元素
    19.     if element.key == key {
    20.         // 将第一个元素后面的键值对链上
    21.         m.array[index] = element.next
    22.         m.len = m.len - 1
    23.         return
    24.     }
    26.     // 下一个键值对
    27.     nextElement := element.next
    28.     for nextElement != nil {
    29.         if nextElement.key == key {
    30.             // 键值对匹配到，将该键值对从链中去掉
    31.             element.next = nextElement.next
    32.             m.len = m.len - 1
    33.             return
    34.         }
    36.         element = nextElement
    37.         nextElement = nextElement.next
    38.     }
    39. }

    删除键值对，如果键值对存在，那么删除，否则什么都不做。

    键值对删除时，哈希表并不会缩容，我们不实现缩容。

    同样先加锁实现并发安全，然后进行哈希算法计算出数组下标：index := m.hashIndex(key, m.capacityMask)，取出元素：element := m.array[index]。

    如果元素是空的，表示链表为空，那么直接返回：

    1.     // 空链表，不用删除，直接返回
    2.     if element == nil {
    3.         return
    4.     }

    否则查看链表第一个元素的键是否匹配：element.key == key，如果匹配，那么对链表头部进行替换，链表的第二个元素补位成为链表头部：

    1.     // 链表的第一个元素就是要删除的元素
    2.     if element.key == key {
    3.         // 将第一个元素后面的键值对链上
    4.         m.array[index] = element.next
    5.         m.len = m.len - 1
    6.         return
    7.     }

    如果链表的第一个元素不匹配，那么从第二个元素开始遍历链表，找到时将该键值对删除，然后将前后两个键值对连接起来：

    1.     // 下一个键值对
    2.     nextElement := element.next
    3.     for nextElement != nil {
    4.         if nextElement.key == key {
    5.             // 键值对匹配到，将该键值对从链中去掉
    6.             element.next = nextElement.next
    7.             m.len = m.len - 1
    8.             return
    9.         }
    11.         element = nextElement
    12.         nextElement = nextElement.next
    13.     }

    6.4. 遍历打印哈希表

    1. // 哈希表遍历
    2. func (m *HashMap) Range() {
    3.     // 实现并发安全
    4.     m.lock.Lock()
    5.     defer m.lock.Unlock()
    6.     for _, pairs := range m.array {
    7.         for pairs != nil {
    8.             fmt.Printf("'%v'='%v',", pairs.key, pairs.value)
    9.             pairs = pairs.next
    10.         }
    11.     }
    13.     fmt.Println()
    14. }

    遍历哈希表比较简单，粗暴的遍历数组，如果数组中的链表不为空，打印链表中的元素。

    1. func main() {
    2.     // 新建一个哈希表
    3.     hashMap := NewHashMap(16)
    5.     // 放35个值
    6.     for i := 0; i < 35; i++ {
    7.         hashMap.Put(fmt.Sprintf("%d", i), fmt.Sprintf("v%d", i))
    8.     }
    9.     fmt.Println("cap:", hashMap.Capacity(), "len:", hashMap.Len())
    11.     // 打印全部键值对
    12.     hashMap.Range()
    14.     key := "4"
    15.     value, ok := hashMap.Get(key)
    16.     if ok {
    17.         fmt.Printf("get '%v'='%v'\n", key, value)
    18.     } else {
    19.         fmt.Printf("get %v not found\n", key)
    20.     }
    22.     // 删除键
    23.     hashMap.Delete(key)
    24.     fmt.Println("after delete cap:", hashMap.Capacity(), "len:", hashMap.Len())
    25.     value, ok = hashMap.Get(key)
    26.     if ok {
    27.         fmt.Printf("get '%v'='%v'\n", key, value)
    28.     } else {
    29.         fmt.Printf("get %v not found\n", key)
    30. }

    输出：

    首先 hashMap := NewHashMap(16) 新建一个 16 容量的哈希表。然后往哈希表填充 35 个键值对，遍历打印出来 hashMap.Range() 。

    可以看到容量从 16 一直翻倍到 `64，而打印出来的键值对是随机的。

    获取键值对时：value, ok := hashMap.Get(key) 能正常获取到值：get '4'='v4'。

    删除键值对：hashMap.Delete(key) 后，哈希表的容量不变，但元素数量变少：after delete cap: 128 len: 34。

    尝试再一次获取键 4，报错：get 4 not found。

    哈希表查找，是一种用空间换时间的查找算法，时间复杂度能达到：，最坏情况下退化到查找链表：O(n)。但均匀性很好的哈希算法以及合适空间大小的数组，在很大概率避免了最坏情况。

    哈希表在添加元素时会进行伸缩，会造成较大的性能消耗，所以有时候会用到其他的查找算法：树查找算法。

    附录

    代码下载： 。