算法学习指南一：哈希

请搭配《hello算法》食用：https://www.hello-algo.com/chapter_hashing/

取模操作（%）最核心的本质，就是建立一种“安全、循环且确定”的映射机制。当你面对海量、未知、甚至无限的输入，却只有有限的存储空间（比如一个固定长度的数组）时，取模是把这两者桥接起来的最有效手段。

空间压缩
边界安全：对正整数N取模的结果一定落在[0, N-1]
均匀分布与确定：key不变，那么结果一定不变

借助数组和链表来存。或者是扩容。还有开放寻址法，当位置冲突的时候就往后顺位，有线性和平方，但是会很容易出现恶意循环，因为每次跳的距离都一样。所以就有了二次哈希或者多重哈希，比如hash1不管用那就用hash2 还有渐进式扩容，达到负载的时候不一口气把之前的内容全部整理进新的表，而是旧表新表并存，每当旧表里的东西被访问的时候自动把他再存到新表，直到旧表清空。

哈希函数的例子

1
def add_hash(key: str) -> int:
2
    """加法哈希
3
    最烂，因为有加法交换律，换位之后的结果一样
4
    """
5
    hash = 0
6
    modulus = 1000000007
7
    for c in key:
8
        hash += ord(c)
9
    return hash % modulus
10

11
def mul_hash(key: str) -> int:
12
    """乘法哈希
13
    最好
14
    """
15
    hash = 0
16
    modulus = 1000000007
17
    for c in key:
18
        hash = 31 * hash + ord(c)
19
    return hash % modulus
20

21
def xor_hash(key: str) -> int:
22
    """异或哈希
23
    异或自己也一样
24
    """
25
    hash = 0
26
    modulus = 1000000007
27
    for c in key:
28
        hash ^= ord(c)
29
    return hash % modulus
30

31
def rot_hash(key: str) -> int:
32
    """旋转哈希
33
    一般
34
    """
35
    hash = 0
36
    modulus = 1000000007
37
    for c in key:
38
        hash = (hash << 4) ^ (hash >> 28) ^ ord(c)
39
    return hash % modulus
40

41
ord是啥，取asii码

为何取模是1000000007这是一个质数，并且是十亿级别的，因为int的范围是2³¹ -1，大概是20亿，这正好是一半
为什么乘法哈希的值取31，因为这是2⁵ -1的值，只用左移5次，然后很好用，算出来的哈希值在分布上已经足够均匀，冲突率降到了最低。
<< 和 >> 右移分别作用与乘2的n次方和除2的n次方

支持与分享

目录