散列表

散列针对数值范围较大但数据个数较少的情况，实现两个效果：

(1)将数据映射到$O(n)$空间复杂度的较小范围；

(2)可以在$O(1)$时间复杂度下高效地查找数据。

实现这样的效果需要定义一个散列函数，散列函数有可能将两个不同的数映射到同一个位置，即产生冲突，于是又有两种处理冲突的方式，拉链表法和开地址法。

散列函数

根据题目具体需要定义不同的散列函数，采取含x的表达式再对n取模的方式，将x计算为[0, n-1]的散列值，其中n最好是素数（n的值取决于冲突处理方式），取素数冲突的概率较小。

虽然散列函数的定义需要视情况而定，但是仍然有常用的函数定义；

如果x没有负值通常定义为：

int func(int x) {
    return x % n;
}

如果x有负值通常定义为：

int func(int x) {
    return (x%n + n) % n;
}

开地址法（闭散列方法）

产生冲突时，开地址法在散列表中向后找到第一个为空的数组位置插入元素。

hash[n]表示散列表；

假设数据一共有m个，开地址法的n一般定义为大于2m的第一个素数（这是一个经验值）；

int hash[n];

开地址法的查找算法，返回查找到该元素的位置，如果没有该元素，返回如果插入的话，该元素应该插入的位置：

null设定为数据范围外的数，数据全为正数，设定为-1，数据有正有负，设定为无穷大或无穷小（int类型为0x3f3f3f3f或0xc0c0c0c0）；

int search(int x) {
    int t = func(x);
    while (hash[t] != null && hash[t] != x)
        t = (t+1) % n;
    return t;
}

开地址法的插入算法：

int t = search(x);
hash[t] = x;

拉链表法（开散列方法）

产生冲突时，拉链表法将映射到散列表同一位置的元素存储到一个链表中。

拉链表法的存储结构与树和图邻接表存储结构中的多个链表形式一致，原来的邻接链表的首指针数组变成散列表hash[n]；

假设数据一共有m个，拉链表法的n一般定义为大于m的第一个素数；

int hash[n], next[n], point[n], d = 0;

拉链表法的查找算法，返回是否查找到元素：

bool search(int x) {
    int t = func(x);
    for (int i = hash[t]; i != -1; i = next[i])
        if (point[i] == x)
            return true;
    return false;
}

拉链表法的插入算法：

void insert(int x) {
    int t = func(x);
    point[d] = x;
    next[d] = hash[t];
    hash[t] = d++;
}

---