【数据结构】散列表的插入和查找（C++实现）

基本概念

1. 散列表：散列表存储了各个关键字key及其地址。
2. 散列函数：p=H(key)，关键字key到其地址的映射。
3. 散列地址：将key作为参数，丢到散列函数H()中，算出来的结果，就是散列地址。
4. 冲突：不同的key，通过散列函数算出来的散列地址一样，这种现象称为冲突。即key1≠key2，但H(key1)=H(key2)。

散列查找的思路

1. 给定待查找的关键字key，根据散列函数计算出散列地址p=H(key)。
2. 若地址p中的元素为空，则key不存在，查找失败。
3. 若地址p中的元素为key，则没有冲突，查找成功，返回地址p。
4. 否则（即地址p中有元素，但该元素不为key），说明出现了冲突，利用处理冲突的方法，计算出下一个散列地址p，跳到步骤2。

代码实现

#include <stdio.h>
#include <stdlib.h>

#define SUCCESS 1
#define UNSUCCESS 0
#define OVERFLOW -1
#define OK 1
#define ERROR -1

typedef int Status;
typedef int KeyType;

typedef struct
{
    KeyType key;
} RcdType;

typedef struct
{
    RcdType *rcd;
    int size;
    int count;
    int *tag;
} HashTable;

int hashsize[] = {11, 31, 61, 127, 251, 503};
int index = 0;

Status InitHashTable(HashTable &H, int size)
{
    int i;
    H.rcd = (RcdType *)malloc(sizeof(RcdType) * size);
    H.tag = (int *)malloc(sizeof(int) * size);
    if (NULL == H.rcd || NULL == H.tag)
        return OVERFLOW;
    for (i = 0; i < size; i++)
        H.tag[i] = 0;
    H.size = size;
    H.count = 0;
    return OK;
}

int Hash(KeyType key, int m)
{
    return (3 * key) % m;
}

void collision(int &p, int m)
{ //线性探测
    p = (p + 1) % m;
}

Status SearchHash(HashTable H, KeyType key, int &p, int &c)
{
    p = Hash(key, H.size);
    int h = p;
    c = 0;
    while ((1 == H.tag[p] && H.rcd[p].key != key) || -1 == H.tag[p])
    {
        collision(p, H.size);
        c++;
    }

    if (1 == H.tag[p] && key == H.rcd[p].key)
        return SUCCESS;
    else
        return UNSUCCESS;
}

void printHash(HashTable H) //打印哈希表
{
    int i;
    printf("key : ");
    for (i = 0; i < H.size; i++)
        printf("%3d ", H.rcd[i].key);
    printf("\n");
    printf("tag : ");
    for (i = 0; i < H.size; i++)
        printf("%3d ", H.tag[i]);
    printf("\n\n");
}

Status InsertHash(HashTable &H, KeyType key); //对函数的声明

//重构
Status recreateHash(HashTable &H)
{
    RcdType *orcd;
    int *otag, osize, i;
    orcd = H.rcd;
    otag = H.tag;
    osize = H.size;

    InitHashTable(H, hashsize[index++]);
    //把所有元素，按照新哈希函数放到新表中
    for (i = 0; i < osize; i++)
    {
        if (1 == otag[i])
        {
            InsertHash(H, orcd[i].key);
        }
    }
}

Status InsertHash(HashTable &H, KeyType key)
{
    int p, c;
    if (UNSUCCESS == SearchHash(H, key, p, c))
    { //没有相同key
        if (c * 1.0 / H.size < 0.5)
        { //冲突次数未达到上线
            //插入代码
            H.rcd[p].key = key;
            H.tag[p] = 1;
            H.count++;
            return SUCCESS;
        }
        else
            recreateHash(H); //重构哈希表
    }
    return UNSUCCESS;
}

Status DeleteHash(HashTable &H, KeyType key)
{
    int p, c;
    if (SUCCESS == SearchHash(H, key, p, c))
    {
        //删除代码
        H.tag[p] = -1;
        H.count--;

        return SUCCESS;
    }
    else
        return UNSUCCESS;
}

void main()
{
    printf("-----哈希表-----\n");
    HashTable H;
    int i;
    int size = 11;
    KeyType array[8] = {22, 41, 53, 46, 30, 13, 12, 67};
    KeyType key;
    RcdType e;

    //初始化哈希表
    printf("初始化哈希表\n");
    if (SUCCESS == InitHashTable(H, hashsize[index++]))
        printf("初始化成功\n");

    //插入哈希表
    printf("插入哈希表\n");
    for (i = 0; i <= 7; i++)
    {
        key = array[i];
        InsertHash(H, key);
        printHash(H);
    }

    //删除哈希表
    printf("删除哈希表\n");
    int p, c;
    if (SUCCESS == DeleteHash(H, 12))
    {
        printf("删除成功，此时哈希表为：\n");
        printHash(H);
    }

    //查询哈希表
    printf("查询哈希表\n");
    if (SUCCESS == SearchHash(H, 67, p, c))
        printf("查询成功\n");

    //再次插入，测试哈希表的重构
    printf("再次插入，测试哈希表的重构：\n");
    KeyType array1[8] = {27, 47, 57, 47, 37, 17, 93, 67};
    for (i = 0; i <= 7; i++)
    {
        key = array1[i];
        InsertHash(H, key);
        printHash(H);
    }
}

参考资料：
1.https://blog.csdn.net/CHENYUFENG1991/article/details/50678878