//测试数据1：14 36 42 38 40 15 19 12 51 65 34 25

//测试数据2：14 36 42 38 40 15 19 12 51 65 34 18

#include<iostream>
#include<cstring>
using namespace std;
#define m 15//哈希表的表长
#define NULLKEY 0//单元为空的标记
int HT[m], HC[m];

int H(int key) { //哈希函数
    return key % 13;
}

// 线性探测法
// 在哈希表中找出一个可以放置冲突数据的位置


int Linedetect(int HT[], int H0, int key, int &cnt) { //线性探测
    // 哈希表，起冲突的地址，存入的关键字，统计比较次数
    int Hi; //可能的新地址
    for (int i = 1; i < m; ++i) {
        cnt++; //被比较了几次cnt+几次
        Hi = (H0 + i) % m; //按照线性探测法计算下一个哈希地址Hi
        // (原地址 + i) % 表长
        if (HT[Hi] == NULLKEY || HT[Hi] == key) //新地址没用
            //或者新地址有相同元素
            return Hi;    //线性探测就返回这个新地址
    }
    return -1; // 找不到新地址
}




bool InsertHash(int HT[], int key) {
    int H0 = H(key); //根据哈希函数H（key）
    // 计算哈希地址
    int Hi = -1, cnt = 1;
    if (HT[H0] == 0) { //若H0为空,不冲突
        HC[H0] = 1; //统计比较次数
        HT[H0] = key;    //放入H0中
        return 1; //表示这个值可以存入哈希表
    } else {
        Hi = Linedetect(HT, H0, key, cnt); //线性探测 解决冲突的核心代码
        // 返回一个新的不冲突的地址给key

        //Hi=Seconddetect(HT,H0,key,cnt);//二次探测
        if (Hi != -1 && HT[Hi] == 0) { //若Hi为空
            HC[Hi] = cnt;
            HT[Hi] = key;
            return 1; //找到一个可以放进去的地址
        }
    }
    return 0; // 没有在哈希表中找到可以放置的地址
}



int main() {
    int x;
    cout << "输入12个关键字，存入哈希表中：" << endl;
    for (int i = 0; i < 12; i++) {
        cin >> x; // 输入关键字
        if (InsertHash(HT, x) == 0) { //如果关键字无法存入哈希表
            cout << "创建哈希表失败！" << endl;
            return 0;
        }
    }
    cout << "输出哈希表：" << endl; // 输出哈希表
    for (int i = 0; i < m; i++)
        cout << HT[i] << "\t"; //输出
    cout << endl;
    return 0;
}

二次探测法

int Seconddetect(int HT[],int H0,int key,int &cnt){//二次探测
    int Hi;
    for(int i=1;i<=m/2;++i){
        int i1=i*i;
        int i2=-i1;
        cnt++;
        Hi=(H0+i1)%m; //按照二次探测法计算下一个哈希地址
        if(HT[Hi]==NULLKEY || HT[Hi]==key)//若单元Hi为空或查找成功
            return Hi;
        cnt++;
        Hi=(H0+i2)%m; //按照二次探测法计算下一个哈希地址
        if(Hi<0)
            Hi+=m;
        if(HT[Hi]==NULLKEY || HT[Hi]==key)//若单元Hi为空或查找成功
            return Hi;
    }
    return -1;
}