用数组模拟哈希表---c语言

哈希表：哈希表是将某个数映射到哈希表的位置中，可以把哈希表看作一个带编号的桶

而数表示 需要放入桶中的元素。

哈希表能开辟的空间有限且不能为负数所以就会存在一个桶里面有多个元素的情况，但是如果就单单一个哈希表就不能判断这个位置存放的具体的数字

打个比方说 如果有一个数23它取模后的位置在3号位有另一个数56取模后也在3号位，这样就会引起冲突，所以就有了拉链法

拉链法就是在哈希表坐标下面建立一个链表，链表用来存储这个数利用哈希表来快速查找这个数是否存在

打个比方说 如果有一个数23它取模后的位置在3号位有另一个数56取模后也在3号位

就在哈希表的3号位置上连接上23和56。

代码

int h[N], e[N], ne[N], idx=0;//h 表示我们的哈希表，e存储的是链表的数据，ne是指向下一个结点，idx表示当前所用的点
//要记得将哈希表初始化为-1。因为-1表示NULL
memset(h, -1, sizeof(h));
void insert(int x)
{
    int k = (x % N + N) % N;//找到存放的位置
    e[idx] = x;    //将数字存放到链表中
    e[idx] = h[k]; //找到h的后继结点并将新结点连接到h的后继
    h[k] = idx++;  //在让h连接到新结点中
}
bool find(int x)
{
    int k = (x % N + N) % N;//找到存放的位置
    for (int i = h[k]; i != -1; i = ne[i])  //依次遍历结点如果找到直接返回true
    {
        if (e[i] == x)
            return true;
    }
    return false;
}

注意事项 其中x最好就取距离数组大小最近的素数，这样冲突就最小 由于需要存储的数有负数取模后还是负数所以要变成正数就要 (x%N+N)%N这样就能将负数变成正数 N表示数组的大小