DS哈希查找—线性探测再散列

Description

定义哈希函数为H(key) = key%11，输入表长（大于、等于11）。输入关键字集合，用线性探测再散列构建哈希表，并查找给定关键字。

–程序要求–

若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio

程序中若include多过一个头文件，不看代码，作0分处理

不允许使用第三方对象或函数实现本题的要求

Input

测试次数t

每组测试数据为：

哈希表长m、关键字个数n

n个关键字

查找次数k

k个待查关键字

Output

对每组测试数据，输出以下信息：

构造的哈希表信息，数组中没有关键字的位置输出NULL

对k个待查关键字，分别输出：0或1（0—不成功，1—成功）、比较次数、查找成功的位置（从1开始）

Sample

#0

Input

Copy

1
12 10
22 19 21 8 9 30 33 4 15 14
4
22
56
30
17

Output

Copy

22 30 33 14 4 15 NULL NULL 19 8 21 9
1 1 1
0 6
1 6 2
0 1

哈希算法：

• 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）
• 对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同；
• 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小；
• 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。

简而言之：哈希算法不可逆，并且有两个不同的例如a，b的哈希值的散列值相等的概率很小、、

哈希表：

? ? ? ?哈希表也叫散列表，哈希表是一种数据结构，它提供了快速的插入操作和查找操作，无论哈希表总中有多少条数据，插入和查找的时间复杂度都是为O(1)，因为哈希表的查找速度非常快，所以在很多程序中都有使用哈希表。

思路：

? ? ? ?本题给的数据会造成哈希的散列冲突，造成哈希冲突的时候就可以按顺序顺沿数组位置找空位，然后插入我们的值。

如：
H(key) = key%11

tips：这个表其实也可以理解为首尾相连的表：

坑点：

? ? ? ? 好像没人告诉你要哈希的数一定比表长度小吧。如果多了的话，我表塞满了，我们靠循环找空位置的写法可能会导致卡在循环里出不来。写法如果是找不到就找下一个位置，直到找到空位为止，那就可能会死循环了！！！

? ? ? ?所以多余的部分你要不就不找了，要不就找的时候控制下循环，让查找次数不能超过表长

完整代码：

#include <iostream>
using namespace std;
const int maxn = 1e3 + 10;
int hashi[maxn];
int n, m;//n是表长，m是有多少个数将被哈希
int findnullindex(int num)
{
    int key = num % 11;//这个就是哈希函数获得的值
    int cnt = 0;//cnt我是用来表示查找次数的，如果我们表每个位置都遍历一遍没有位置，说明没有空位
    while (1)
    {
        if (cnt > n)//如果查找次数大于表长，那就说明没有空位
        {                 //原因是如果要哈希的数多于表长，塞满了哪里还塞得下
            return -1;
        }
        if (hashi[key] != -1)//说明这个位置有数了，所以得继续往下找
        {
            key++;
        }
        else
        {
            return key;//查找到了空位，返回空位下标
        }
        key = key % n;//每次都取余一下，这样就不会超过表长了
        cnt++;//查找次数+1
    }
}
void insert(int num)
{
    int index = findnullindex(num);//查找可以插入的空位
    if (index != -1)//如果有空位就在index这个位置插入num
    {
        hashi[index] = num;
    }
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        for (int i = 0; i <= n; i++)
        {
            hashi[i] = -1;//首先初始化哈希表都为-1
        }
        for (int i = 1; i <= m; i++)
        {
            int num;
            cin >> num;
            insert(num);//输入要哈希的数，然后将他插入进表里
        }
        for (int i = 0; i < n; i++)
        {
            if (hashi[i] != -1)
            {
                cout << hashi[i] << " ";
            }
            else
            {
                cout << "NULL ";
            }
        }
        cout << endl;
        int t;
        cin >> t;
        while (t--)
        {
            int num;
            cin >> num;
            int key = num % 11;
            int cnt = 1;//这里的cnt是计算查找次数的
            while (hashi[key] != -1 && hashi[key] != num)//如果key所在为-1，说明没有这个数
            {                        //key这个位置有数也可能是冲突值，得往之后的位置查找一遍
                if (cnt >= n)//这个意思说明查找完所有位置都没找到
                {
                    key = n;//因为我表长n，下标为0-n-1，所以n这个位置是-1，肯定不会被更改
                    break;  //所以我用来当作没找到
                }
                key++;
                cnt++;//如果找到了cnt刚好也可以记查找次数
                key = key % n;
            }
            if (hashi[key] == -1)//key所在的值为-1说明就是没找到
            {
                cout << "0 " << cnt << endl;
            }
            else
            {
                cout << "1 " << cnt << " " << key + 1 << endl;
            }
        }
    }
    return 0;
}

---