哈希表

哈希表由一个基于数组的数据结构和哈希函数组成。它的基本原理是将key通过哈希函数计算得到一个索引值，然后将值存储在该索引对应的位置上。这样，在需要查找、插入或删除值时，可以通过哈希函数快速计算出对应的索引，从而直接访问到目标值，而无需遍历整个数据集。

下面是一些关键特点和操作：

1. 快速访问: 哈希表能够以接近常数时间复杂度 O(1) 进行查找、插入和删除操作，即使数据集很大。

2. 哈希函数: 哈希函数将键转换为索引，通常将键的特征映射到数组的某个范围内。一个良好的哈希函数应该均匀地分布键的值，尽量减少冲突，以提高性能。

3. 冲突处理: 不同的键可能会映射到相同的索引，这就是哈希冲突。常见的解决冲突的方法有两种：开放寻址法和拉链法。

4. 开放寻址法: 当发生冲突时，通过一定的方法（如线性探测、二次探测、双重哈希等）在哈希表中寻找下一个可用的位置来存储冲突的键值对。

5. 拉链法: 每个哈希桶（索引位置）都是一个链表或其他数据结构，用于存储多个键值对。当出现冲突时，冲突的键值对会以链表的形式连接在一起。

6. 容量和负载因子: 容量是指哈希表中可以存储的键值对数量上限，负载因子是已存储键值对数量与容量的比值。适当选择容量和负载因子可以平衡空间利用率和性能。当负载因子超过一定阈值时，哈希表可能需要进行扩容操作。

7. 哈希表应用: 哈希表广泛应用于各种场景，例如缓存系统、数据库索引、字典结构等。它能够快速查找、唯一存储和高效更新数据。

@startmindmap
* 哈希表
** 存储结构
*** 开放寻址法
**** 线性探测
*** 拉链法
**** 邻接表
** 字符串前缀哈希
@endmindmap

其中字符串哈希主要作用是将字符串转换为哈希值，从而实现高效的字符串比较和匹配。

算法竞赛中，哈希表常见于将一个较大的定义域，映射到一个较小的值域中。一般来说，模上目标范围就行，但为了减少冲突，习惯取大于目标范围的最小质数，为了让所有key同这个数的公约数都为1，从而保证余数的均匀分布，降低冲突率。

哈希函数：一般取大于目标范围的最小质数。

int k=( x % N + N ) % N;

加N模N操作也是非常常见了，如果x >= 0，( x % N + N ) % N == x % N;如果x <= 0，也能通过加N操作把数据限制为大于0的数，确保能映射到0~N这个范围内。

开放寻址法写起来非常简单，不过为了减少冲突一般会多开两到三倍的空间。邻接表写起来稍微麻烦点。

一般哈希：

(1) 拉链法
    int h[N], e[N], ne[N], idx;

    // 向哈希表中插入一个数
    void insert(int x)
    {
        int k = (x % N + N) % N;
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx ++ ;
    }

    // 在哈希表中查询某个数是否存在
    bool find(int x)
    {
        int k = (x % N + N) % N;
        for (int i = h[k]; i != -1; i = ne[i])
            if (e[i] == x)
                return true;

        return false;
    }

(2) 开放寻址法
    int h[N];

    // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
    int find(int x)
    {
        int t = (x % N + N) % N;
        while (h[t] != null && h[t] != x)
        {
            t ++ ;
            if (t == N) t = 0;
        }
        return t;
    }

字符串前缀哈希

核心思想：通过预先计算每个前缀的哈希值，来实现快速计算任意子串的哈希值。

可以说是KMP算法的平替了，学过前缀和，这个就很好理解了。

具体做法：将整个字符串看成一个P进制的数，字符串的每一位字母看成这个P进制数的每一位。又因为P进制得到的数可能非常大，多半会溢出，所以需要模上一个Q。

Tips:

1. 一般不能把某个字母映射成0，例如：A，AA的前缀哈希都是0，这样会把不同的字符串映射成同一个值。
2. 一般做题时默认人品足够好，不存在哈希冲突。
3. 一般默认P=131或13331，Q=2[HTML_REMOVED]64[HTML_REMOVED]。做题经验值，但貌似也能证明这样冲突很小。
4. 已知前缀求任意字串时记得高位对齐再相减
5. 取模Q小技巧，直接用unsigned long long存储哈希值就行，溢出即取模。

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

对于取模这件事，第一次学的时候还有些计较，现在看来，貌似所有的哈希都不关心哈希值具体是多少，我们只需要知道，我们能通过这个东西得到何种信息就行。两个哈希值相等就说明两个字符串一样呗（假设无冲突），至于是怎么得到的、取模还是自动溢出还是啥啥啥，不重要。