哈希数据结构和代码实现

标签: 数据结构  C语言  冲突解决方法  哈希函数  哈希表

在这里插入图片描述

主要结构体:

typedef enum
{
    EN_STATUS_EMPTY,
    EN_STATUS_DELETE,
    EN_STATUS_EXIST,
}ENUM_DATA_STATUS;

typedef int DATA_TYPE;

typedef struct
{
    DATA_TYPE   key;
    ENUM_DATA_STATUS status;
}STRU_HASH_NODE;

typedef struct
{
    STRU_HASH_NODE* hashNode;
    int size;
    int capacity;
}HASH_TABLE;

实现插入、删除、查找、扩容、冲突解决等接口,用于理解哈希这种数据结构

#include "Hash.h"
#include <stdio.h>
#include <memory>

int InitHash(HASH_TABLE* table, int capacity)
{
    if(NULL == table)
    {
        return DA_ERROR;
    }
    table->size = 0;
    table->capacity = capacity;
    table->capacity = GetCapacity(table);

    table->hashNode = (STRU_HASH_NODE*)malloc(sizeof(STRU_HASH_NODE) * table->capacity);

    for (int i = 0; i < table->capacity; i++)
    {
        table->hashNode[i].status = EN_STATUS_EMPTY;
    }

    return DA_SUCCESS;
}

/*重新扩容时,哈希表大小*/
int GetCapacity(HASH_TABLE* table)
{
    //哈希表容量递增表,一个合适的素数序列,减少冲突的可能
    const int nPrimeSize = 13;
    const int HashSize[] = 
    {
        7,13,17,101,
        211,307,401,503,
        601,701,809,907,
        997
    };

    for (int i = 0; i < nPrimeSize; i++)
    {
        if (table->capacity < HashSize[i])
        {
            return HashSize[i];
        }
    }

    return HashSize[nPrimeSize - 1];
}

bool CheckCapacity(HASH_TABLE* table)
{
    //检查负载因子大小
    int check_capacity = (table->size * 10) / table->capacity;
    if (check_capacity >= 7)
    {
        return true;
    }
    return false;
}

/*哈希表扩容*/
int RecreateHashTable(HASH_TABLE *table)
{
    HASH_TABLE NewTable;
    //创建新的哈希表
    InitHash(&NewTable,table->capacity);

    for (int i = 0; i < table->capacity; i++)
    {
        if (EN_STATUS_EXIST == table->hashNode[i].status)
        {
            InsertHash(&NewTable,table->hashNode[i].key);
        }
    }

   if (table->hashNode != NULL)
   {
       free(table->hashNode);
       table->hashNode = NULL;
   }

   table->capacity = NewTable.capacity;
   table->size = NewTable.size;
   table->hashNode = NewTable.hashNode;
   return DA_SUCCESS;
}

/*除留余数法*/
int HashFun(HASH_TABLE* table, DATA_TYPE data)
{
    return data % table->capacity;
}

/*冲突时,线性探测返回新的地址*/
int Collision(HASH_TABLE *table, int hash_addr)
{
    return (hash_addr + 1) % (table->capacity);
}

/*哈希表插入关键字*/
/*
step1:给出对应的哈希地址
step2:判断当前哈希地址是否有冲突
step3:有冲突则采用冲突策略,否则将该元素放在该位置
*/
int InsertHash(HASH_TABLE *table, DATA_TYPE data)
{
    if (CheckCapacity(table))
    {
        printf("hash table need to recreate\n");
        RecreateHashTable(table);
    }

    int hash_addr = HashFun(table, data);
    int index = hash_addr;
      
    //冲突检测以及冲突解决方法:线性探测法
    while (table->hashNode[index].status == EN_STATUS_EXIST)
    {
        if (table->hashNode[index].key == data)
        {
            return DA_ALREADY_EXIST;
        }

        index = Collision(table,index);
    }

    printf("key = %d hash addr=%d target= %d\n",data, hash_addr,index);

    table->hashNode[index].key = data;
    table->hashNode[index].status = EN_STATUS_EXIST;
    table->size += 1;
    return DA_SUCCESS;
}

/*哈希表关键字搜索*/
bool SearchHash(HASH_TABLE* table, DATA_TYPE data)
{
    int hash_addr = HashFun(table, data);
    int index = hash_addr;
    //线性探测法,查找
    while (table->hashNode[index].status == EN_STATUS_EXIST)
    {
        //相等则存在
        if (table->hashNode[index].key == data)
        {
            return true;
        }

        //线性探测下一个元素
        index = Collision(table,index);
    }
    
    return false;
}

/*删除哈希关键字*/
/*
采用线性探测法处理散列时的冲突,
当从哈希表删除一个记录时,不应将这个记录的所在位置置空,
否则影响其他记录的查找
*/
bool RemoveHash(HASH_TABLE* table, DATA_TYPE data)
{
    int hash_addr = HashFun(table, data);

    int index = hash_addr;
    //线性探测法,查找
    while (table->hashNode[index].status == EN_STATUS_EXIST)
    {
        //相等则存在
        if (table->hashNode[index].key == data)
        {
            table->hashNode[index].status = EN_STATUS_DELETE;
            table->size--;
            return true;
        }
        //线性探测下一个元素
        index = Collision(table,index);
    }

    return false;
}

void DestoryHash(HASH_TABLE* table)
{
    table->capacity = 0;
    table->size = 0;
    free(table->hashNode);
    table->hashNode = NULL;
}

void PrintHash(HASH_TABLE* table)
{
   printf("哈希表容量为%d, 元素个数为%d\n",table->capacity,table->size);
   for (int i = 0; i < table->capacity; i++)
   {
       if (table->hashNode[i].status == EN_STATUS_EXIST)
       {
           printf("key=%d\t",table->hashNode[i].key);
       }
   }
   printf("\n");
   for (int i = 0; i < table->capacity; i++)
   {
       if (table->hashNode[i].status == EN_STATUS_DELETE)
       {
           printf("delete key=%d\t",table->hashNode[i].key);
       }
   }

   printf("\n");
}

void test_hash()
{
    HASH_TABLE  ht;
    InitHash(&ht, 0);//哈希表初始化
    printf("begin insert data....\n");

    InsertHash(&ht, 37);//插入数据
    InsertHash(&ht, 25);//插入数据
    InsertHash(&ht, 11);//插入数据
    InsertHash(&ht, 36);//插入数据
    InsertHash(&ht, 41);//插入数据
    InsertHash(&ht, 42);//插入数据

    PrintHash(&ht);//打印哈希表;

    printf("begin search data....\n");
    
    if (SearchHash(&ht,11))
    {
        printf("find  data success...\n");
    }
    else
    {
        printf("find data fail...\n");
    }

    printf("begin remove data....\n");

    RemoveHash(&ht, 11);//插入数据

    PrintHash(&ht);//打印哈希表;

    DestoryHash(&ht);
}

完整代码参见github:

https://github.com/jinxiang1224/cpp/tree/master/DataStruct_Algorithm/hash

版权声明:本文为c_base_jin原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/c_base_jin/article/details/102810159

智能推荐

一致性hash算法

散列(hash)在我看来就是一个数组,而与数组不同的点在于数组是按顺序写入的,而hash是按照一定的hash算法确定元素在数组中的位置的。hash最难的问题在于会有冲突出现,如果两个object根据相应的hash算法得出的值一样便产生了hash冲突。在所有解决hash冲突的方法中,我最欣赏的是链式解决法,即将hash到同一位置的元素用链表连接。当然还有其它几种处理hash冲突的算法,比如建立公共溢...

OpenCV-Python learning-1.安装,图片读取显示

1. OpenCV与OpenGL区别 https://www.zhihu.com/question/20212016 一个是让机器识别东西的,OpenCV是给电脑做眼睛的。 一个是让机器计算出更好画面的,OpenGL用在游戏渲染方面很多。 OpenCV(Open Source Computer Vision Library)是一个基于(开源)发行的跨平台计算机视觉库,OpenGL(全写Open G...

Mycat+Mysql分布式架构改造和性能压力测试

架构实现 Mycat作为数据库高可用中间件具备很多的功能,如负载均衡,分库分表,读写分离,故障迁移等。结合项目的实际情况,分库分表功能对于关联查询有很高的要求,需要从业务角度考虑分库分表后的关联查询SQL的分析,业务代码动作较大,所以在此方案中我们不考虑分库分表。主要应用Mycat的负载均衡及故障迁移的功能即可。 整个架构改造包括两个部分,第一是单例Mysql改为多个Mysql,同时负载均衡,并且...

人脸识别之疲劳检测(二)阈值法、KNN分类和K-means聚类

Table of Contents 1、均值法 2、中值法 3、KNN 4、K-means 结合上一节在获得人眼特征点后需要对睁眼闭眼状态做出判断,方法的选择需要经验结合公平的评价方法,使用大量测试集得到不同方法下的精确度并做出比较: 1、均值法 50帧睁眼数据取均值,得到不同阈值下精确度。 2、中值法 50帧睁眼数据取中值,得到不同阈值下精确度。 3、KNN KNN是一种ML常用分类算法,通过测...

CodeForce Tic-Tac-Toe

Two bears are playing tic-tac-toe via mail. It's boring for them to play usual tic-tac-toe game, so they are a playing modified version of this game. Here are its rules. The game is played on the foll...

猜你喜欢

Python雾里看花-抽象类ABC (abstract base class)

首先认识模块 abc,python中没有提供抽象类与抽象方法,然而提供了内置模块abc来模拟实现抽象类,例如提供泛映射类型的抽象类 abc.MutableMapping 继承abc.MutableMapping构造一个泛映射类型(类似python中的dict) 当然继承abc.Mapping 也可以,毕竟MutableMapping是其子类 dict是python中典型的映射类型数据结构,其接口的...

python 文件操作

2, with open (‘xx.txt’,‘w’,encoding=‘utf-8’) as f: f.write(‘文件内容或对象’)...

【Python基础】使用统计函数绘制简单图形

机器学习算法与自然语言处理出品 @公众号原创专栏作者 冯夏冲 学校 | 哈工大SCIR实验室在读博士生 2.1 函数bar 用于绘制柱状图 2.2 函数barh 用于绘制条形图 2.3 函数hist 用于绘制直方图 直方图与柱状图的区别 函数pie 用于绘制饼图 2.5 函数polor 用于绘制极线图 极线图是在极坐标系上绘出的一种图。在极坐标系中,要确定一个点,需要指明这个点距原点的角...

css:顶部按钮固定,上面内容滑动

这种需求我们平时见到很多的,实现方法也多的参差不齐,下面我说一种简单的。如图: 可以看到只有红线部分滚动,底下按钮是固定的。 代码...

环形公路堵车概率模型(含详细解析)

文章目录 基础理论 代码实现 图形分析 基础理论 路面上有n辆车,以不同的速度向前行驶, 模拟堵车问题。 有以下假设: 假设某辆车的当前速度是v。 若前方可见范围内没车,则它在下一秒的车速提高到v+1,直到达到规定的最高限速。 若前方有车,前车的距离为d,且d < v,则它下 一秒的车速降低到d-1 。 每辆车会以概率p随机减速v-1。、 代码实现 图形分析 图形中颜色越重的地方,说明很多车...