golang之哈希表：散列查找算法

清疚 2022-11-26 10:59 229阅读 0赞

# 线性查找 #

我们要通过一个`key`来查找相对的`value`。有一种最简单的方式，就是将键值对存放在链表里，然后遍历链表来查找是否存在`key`，存在则更新`key`对应的`value`，不存在则将`key-value`链接到链表上。

这种链表查找，最坏的时间复杂度为`O(n)`

# 散列查找 #

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

> 散列表（Hash table，也叫哈希表），是根据关键码值(Key  
> value)而直接进行访问的数据结构。也就是说，它通过dao把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

> Hash 算法虽然是一种算法，但更像一种思想，没有一个固定的公式，只要符合这种思想的算法都称 Hash 算法。

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

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

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

# hash函数 #

## 哈希函数的作用: 根据key获取hash值 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]  
当hash冲突不严重的时候，查找某个键，只需要求hash值，然后取余，定位到数组的某个下标即可，时间复杂度为`O(1)`

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

所以hash表实现要解决的问题就是寻找相对均匀，具有很好的随机分布性的hash函数。

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

xxhash:[https://code.google.com/p/xxhash][https_code.google.com_p_xxhash]  
cityhash: [https://code.google.com/p/cityhash][https_code.google.com_p_cityhash]  
当然还有其他哈希算法如MurmurHash:[https://code.google.com/p/smhasher][https_code.google.com_p_smhasher]。

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

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

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

package main
    
    import (
        "fmt"
        "github.com/OneOfOne/xxhash"
    )
    
    // 将一个键进行Hash
    func XXHash(key []byte) uint64 {
        
        h := xxhash.New64()
        h.Write(key)
        return h.Sum64()
    }
    
    func main() {
        
        keys := []string{
        "hi", "my", "friend", "I", "love", "you", "my", "apple"}
        for _, key := range keys {
        
            fmt.Printf("xxhash('%s')=%d\n", key, XXHash([]byte(key)))
        }
    }

输出：

xxhash('hi')=16899831174130972922
    xxhash('my')=13223332975333369668
    xxhash('friend')=4642001949237932008
    xxhash('I')=12677399051867059349
    xxhash('love')=12577149608739438547
    xxhash('you')=943396405629834470
    xxhash('my')=13223332975333369668
    xxhash('apple')=6379808199001010847

我们已经寻找到了计算较快，且均匀随机分布的哈希算法xxhash了，接下来就需要根据hash值映射到哈希数组了。

## 根据hash值映射到哈希数组 ##

拿到哈希值之后，我们要将这个值映射到数组的某一个空间，也就是进行数组寻址。如果数组的长度为len，那么`index = xxhash(key) % len`。

可以看出，不管是从初始化哈希数组还是根据值映射哈希数组，我们都需要先确定哈希数组的长度，那么数组的长度应该如何选择？

# hash函数为什么要选择对素数求余？ #

引出此问题，是看到一篇有关jdk中HashMap和Hashtable对于hash算法的选择。

1、**位运算(&)比模运算(%)效率高很多，原因是位运算直接对内存数据进行操作，不需要像模运算一样转成十进制，因此处理速度快。**

2、`HashMap`中对key求完hash值，在进行数组寻址时，使用的方法是位运算（代替的取模运算）。公式如下：

(length - 1) & hash  // length为HashMap的容量，是2的n次方

3、`HashMap`我们一般选择2^x作为hash数组的长度, 是因为我们可以使用&代替%来进行数组寻址

// 可以使用位运算代替模运算的原因，见以下公式：
        hash % 2^n = hash & (2^n -1)
        
        // 5 % 8 = 5 & 7 = 0110 & 0111 = 0110 = 5
        // 13 % 8 = 13 & 7 = 1110 & 0111 = 0110 =5

4、`Hashtable`中求完hash值，在进行数组寻址时，使用的取模运算

int index = (hash & 0x7FFFFFFF) % tab.length;
        // 此处hash和0x7FFFFFFF的一次位与操作，是为了保证得到的index值首位为0（代表正数），其实就是在取绝对值。以避免负数计算index的复杂度
        // tab.length为Hashtable的长度。默认初始化为11，之后rehash每次扩容为oldCapacity * 2 + 1

*  前面说过，HashMap之所以不用取模的原因是为了提高效率，为什么Hashtable还要使用？有人认为，因为HashTable是个线程安全的类，本来就慢，所以Java并没有考虑效率问题，就直接使用取模算法了呢？但是其实并不完全是，Java这样设计还是有一定的考虑在的，虽然这样效率确实是会比HashMap慢一些。
 *  HashTable简单的取模是有一定的考虑在的。这就要涉及到HashTable的构造函数和扩容函数。Hashtable的长度：默认初始化为11，之后rehash每次扩容为oldCapacity \* 2 + 1。也就是说，HashTable的链表数组的默认大小是一个素数、奇数。之后的每次扩充结果也都是奇数。。
 *  **由于HashTable会尽量使用素数、奇数作为容量的大小。当哈希表的大小为素数时，简单的取模哈希的结果会更加均匀**。这就是文章开头所提到的，问题来源

[来自][Link 1]

https://www.jianshu.com/p/e4cbe8c545cf

https://www.cnblogs.com/nima/p/12724872.html  
https://www.cnblogs.com/itbsl/p/10600110.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/d7d99d151392400084bf95b3946e84b9.png
[https_code.google.com_p_xxhash]: https://code.google.com/p/xxhash
[https_code.google.com_p_cityhash]: https://code.google.com/p/cityhash
[https_code.google.com_p_smhasher]: https://code.google.com/p/smhasher
[https_github.com_OneOfOne_xxhash]: https://github.com/OneOfOne/xxhash
[Link 1]: http://www.manongjc.com/article/28968.html