美文网首页
【数据结构】散列表的插入和查找(C++实现)

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

作者: w8ed | 来源:发表于2019-04-12 13:20 被阅读0次

基本概念

  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

相关文章

  • 【数据结构】散列表的插入和查找(C++实现)

    基本概念 散列表:散列表存储了各个关键字key及其地址。 散列函数:p=H(key),关键字key到其地址的映射。...

  • 散列表下

    为什么散列表和链表经常会一起使用? 散列表这种数据结构虽然支持非常高效的数据插入、删除、查找操作,但是散列表中的数...

  • 散列表下

    为什么散列表和链表经常会一起使用? 散列表这种数据结构虽然支持非常高效的数据插入、删除、查找操作,但是散列表中的数...

  • HashMap底层原理分析

    HashMap又称之为散列表,这是一种使查找,插入和删除都具备良好性能的数据结构,其查找的时间复杂度为O()。散列...

  • 数据结构——散列

    散列也叫作散列表,是一种非线性的数据结构,可以用来快速的查找和插入数据。在 JavaScript 中,通常使用数组...

  • 散列表

    概念 散列表的实现常常叫做散列(hashing)。散列是一种用于以常数平均时间执行插入、删除和查找的技术。散列函数...

  • 散列表(Hash Table)

    定义 散列表是一种以平均O(1)时间插入、删除和查找的数据结构,可是类似于findMax,findMin等操作则需...

  • 哈希表与HashCode

    散列表 又叫哈希表(hash table)。哈希表是种数据结构,它可以提供快速的插入操作和查找操作。通过访...

  • 数据结构与算法之散列表

    1 散列表概述 散列表(hash table):是实现字典操作的一种有效数据结构。最坏查找时间为O(n),理论上可...

  • 算法笔记(二)

    二分搜索、哈希表 散列表的实现叫做散列,散列是一种用来以常数平均时间执行插入,删除和查找的技术。 散列函数 解决冲...

网友评论

      本文标题:【数据结构】散列表的插入和查找(C++实现)

      本文链接:https://www.haomeiwen.com/subject/awccwqtx.html