数据结构之哈希表以及常用哈希的算法表达(含全部代码)

简介: 数据结构之哈希表以及常用哈希的算法表达(含全部代码)

目录


为什么要有哈希

哈希表

含义

创建哈希表需要注意的点

算法的选择

哈希冲突的处理

线性探测法

再哈希法

链表法

哈希表的实现(代码部分)

确定结构体(节点)

准备一个哈希算法

创建一个哈希表(即开辟空间)

创建节点

数据加入哈希表的具体实现

获取数据,数据加入哈希表

打印哈希表

查找哈希表(重点,这也能帮你理解哈希表的结构与优势所在)

销毁哈希表

主函数


正文


为什么要有哈希


如果要存储一组数据,我们都能想到使用数组或者链表来存储,但是实际生产生活中,数据都是非常庞大的,动辄几十G,几十T,甚至以P来计算。这样一来,数组和链表的优势以劣势就非常明显了。

插入数据 查找数据
数组 劣势 优势
链表 优势 劣势

既然这两种方法都不能完美解决实际问题,那就一定会有一种方法的诞生来处理它,我们的哈希表就这样诞生啦,哈希表集这两种存储形式的优点于一身,接下来就让我们走进哈希表吧。


哈希表


含义


哈希表也叫散列表,哈希表是一种数据结构,它提供了快速的插入操作和查找操作,无论哈希表总中有多少条数据,在有足够优秀的哈希算法时,插入和查找的时间复杂度都是为O(1)。


散列表 ( Hash table  ),是根据键(Key)而直接访问在记忆体储存位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表 。表中存储的是一个地址,我们通过键值计算出来的哈希值得到这个地址,再取这个地址中的数据即可。


创建哈希表需要注意的点


算法的选择


常见的算法形式有,根据键值进行加法运算,减法运算,乘法运算,位移运算。


值得一说的是位移运算,无论是前移还是后移, 都会使键值转换出来的哈希值大小难以确定,可能有键值很大,但是哈希值很小的情况,这就让使用者无法大致确定键值对应的哈希值。但这并不是缺点,看实际生产要求。


而一般都是以上几种运算的复合运算作为哈希算法。例如;

hashvalue = (hashvalue << 4) + hashvalue + *key++;
//hashvalue为哈希值,key为键值


哈希冲突的处理


哈希冲突即为不同键值通过哈希算法得到了相同的哈希值,这种情况,我们肯定不能将数据直接存储到对应的地址去,这样会将原来的数据覆盖。对此常见的 方法有一下三种,我们最推荐使用链表的方式。


线性探测法


在线性探测哈希表中,数据的插入是线性的查找空白单元,例如我们将数88经过哈希函数后得到的数组下标是16,但是在数组下标为16的地方已经存在元素,那么就找17,17还存在元素就找18,一直往下找,直到找到空白地方存放元素。


再哈希法


双哈希是为了消除原始聚集和二次聚集问题,线性探测每次的探测步长都是固定的。双哈希是除了第一个哈希函数外再增加一个哈希函数用来根据关键字生成探测步长,这样即使第一个哈希函数映射到了数组的同一下标,但是探测步长不一样,这样就能够解决聚集的问题。

和第一个哈希函数不一样

不能输出为0,因为步长为0,每次探测都是指向同一个位置,将进入死循环,经过试验得出stepSize = constant-(key%constant);形式的哈希函数效果非常好,constant是一个质数并且小于数组容量


链表法


通过在哈希表中再寻找一个空位解决冲突的问题,还有一种更加常用的办法是使用「链表法」来解决哈希冲突。「链表法」相对简单很多,「链表法」是每个数组对应一条链表。当某项关键字通过哈希后落到哈希表中的某个位置,把该条数据添加到链表中,其他同样映射到这个位置的数据项也只需要添加到链表中,并不需要在原始数组中寻找空位来存储。

345.png


哈希表的实现(代码部分)


确定结构体(节点)


#define HASHSIZE 256 //你的哈希表的元素个数
typedef int mydatatype;
typedef unsigned char uint8;
struct node
{
  //char * key;//键值,最好使用指针,这里为了便捷,使用数组
  char key[128];
  mydatatype data;//这个东西就是你的数据
  struct node * next;    //解决哈希冲突的链表法
};


准备一个哈希算法


/* 
GetHashValue:获取哈希值
  @key:输入的键值
  返回值:
    输入的键值对应的哈希值
 */
uint8 GetHashValue(const char * key)
{
  uint8 hashvalue = 0;
  while(*key)
  {
    hashvalue = (hashvalue << 4) + hashvalue + *key++;  //首先我们应该准备一个哈希算法
                                                            //你可能会要调试多次
  }
  printf("hashvalue = %d\n",hashvalue);
  return hashvalue; 
}


创建一个哈希表(即开辟空间)


/* 
GetHashTable: 得到一个哈希表
  返回值:
    哈希表所需的空间
 */
struct node ** GetHashTable(void)
{
            //这个空间开出来就是为了保存地址的  
            //因此sizeof(struct node *)
  return (struct node **)calloc(sizeof(struct node *) , HASHSIZE);    //calloc会初始化空间为0
}


创建节点


/* 
GetDataNode: 创建节点的函数
  @key:输入的键值
  @data:键值对应的数据
  返回值:
    哈希表的一个节点
 */
static struct node * GetDataNode(const char * key,mydatatype data)  //const关键字对变量加以限定,使它不能被改变
{
  struct node * pnew = malloc(sizeof(struct node));
    strcpy(pnew ->key,key);   //注意,这里不能直接写pnew->key = key;
    pnew ->data = data;
    pmew ->next = NULL;    
  return pnew;
}


数据加入哈希表的具体实现


/* 
InsertDataToHashTable:将数据加入到哈希表
  @ht:哈希表
  @key:键值
  @date:键值对应的数值
 */
static void InsertDataToHashTable(struct node ** ht,const char * key,mydatatype data)
{
    struct node *pnew = GetDataNode(key,data);
    //计算哈希值
    uint8 hashvalue = GethashValue(key);
    if(!ht[hashvalue])  //如果哈希表的下标为hashvalue的元素为空 
              //则这个地方是没有填入数据的 直接填入就可以了
    {
        ht[hashvalue]) = pnew;
    }
    else
    {
        //如果有hashvlaue与key值d都相同的情况 
    //一般有两种做法  1 直接丢弃不用   2 加上一个num计数
    //一般我们用尾插法插入
        struct node * p = ht[hashvalue];
        while(p)
        {
            if(!strcmp(p ->key,key))
            {
                free(pnew);
                printf("键值一样\n");
                return;
            }
            p = p->next;
        }
        p = pnew;    //p已经是最后一个节点的next
    }
}


获取数据,数据加入哈希表


/* 
GetData:获取数据,加入到哈希表中
  @ht:哈希表
 */
void GetData(struct node ** ht)
{
    if(!ht)
        return;
    mydatatype data;
    char key[128] = {0};
    while(1)
    {
        //先输入键值,再输入data
        if(scanf("%s%d",key,data) != 2)//你匹配上的东西不等于2  说明你的匹配失败
        {
            char ha[1024];
            fgets(ha,1024,stdin);    //将标准输入里面的东西拿掉
            printf("输入有误,请重新输入\n");
`            continue;
        }    
        if(!strncmp(key,"##",2))    //输入“##”结束输入
            break;
        InsertDataToHashTable(ht,key,data);
    }
}


打印哈希表


/* 
PrintHashTable:打印这个哈希表
  @ht:哈希表
 */
void PrintHashTable(struct node ** ht)
{
    int i;
    for(i = 0;i < HASHSIZE;i++)
    {
        if(ht[i])
        {
            struct node *p = hr[i];
            while(p)
            {
                printf("HV = %d\tkey = %s\tdata = %d\n",i,p->key,p->data);
                p = p ->next;
            }
        }
    }   
}


查找哈希表(重点,这也能帮你理解哈希表的结构与优势所在)


/* 
FindData:查找哈希表
  @ht:哈希表
  @key:键值
 */
void FindData(struct node ** ht,const char * key)
{
    uint8 hashvalue = GetHashValue(key);
    if(ht[hashvalue])    //哈希表存在
    {
        struct node * p = ht[hashvalue];
        int i = 1;
        while(p)
        {
            if(strcmp(p ->key,key)
            {
                printf("找到了,键值为%d中的第%d个,value = %d\n",hashvalue,i,p->data);
                return;
            }
            i++;
            p = p ->next;
        }
    }
    printf("查找的元素%s不存在\n",key);
}


销毁哈希表


/* 
DestoryHashTable:销毁这个哈希表
  @ht:哈希表
 */
void DestoryHashTable(struct node ** ht)
{
    int i = 0; 
    for(i = 0;i < HASHSIZE;i++)
    {
        struct node * p = ht[i];
        struct node * pre = NULL;
        while(!ht[i])
        {
            if(p ->next)
            {
                free(p);
                pre ->next = NULL;
                p = ht[i];
            }
            else
            {
                pre = p;
                p = p ->next;
            }
        }
    }
}


主函数


int main()
{
  struct node ** ht = GetHashTable();
  GetData(ht);
  PrintHashTable(ht);
  printf("输入你要查找的键值:");
  char buf[128] = {0};
  scanf("%s",buf);
  FindData(ht,buf);
  DestoryHashTable(ht);
  return 0;
}
目录
打赏
0
0
0
0
161
分享
相关文章
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
本文聚焦 MySQL 集群架构中的负载均衡算法,阐述其重要性。详细介绍轮询、加权轮询、最少连接、加权最少连接、随机、源地址哈希等常用算法,分析各自优缺点及适用场景。并提供 Java 语言代码实现示例,助力直观理解。文章结构清晰,语言通俗易懂,对理解和应用负载均衡算法具有实用价值和参考价值。
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
基于 C++ 哈希表算法实现局域网监控电脑屏幕的数据加速机制研究
企业网络安全与办公管理需求日益复杂的学术语境下,局域网监控电脑屏幕作为保障信息安全、规范员工操作的重要手段,已然成为网络安全领域的关键研究对象。其作用类似网络空间中的 “电子眼”,实时捕获每台电脑屏幕上的操作动态。然而,面对海量监控数据,实现高效数据存储与快速检索,已成为提升监控系统性能的核心挑战。本文聚焦于 C++ 语言中的哈希表算法,深入探究其如何成为局域网监控电脑屏幕数据处理的 “加速引擎”,并通过详尽的代码示例,展现其强大功能与应用价值。
74 2
java实现队列数据结构代码详解
本文详细解析了Java中队列数据结构的实现,包括队列的基本概念、应用场景及代码实现。队列是一种遵循“先进先出”原则的线性结构,支持在队尾插入和队头删除操作。文章介绍了顺序队列与链式队列,并重点分析了循环队列的实现方式以解决溢出问题。通过具体代码示例(如`enqueue`入队和`dequeue`出队),展示了队列的操作逻辑,帮助读者深入理解其工作机制。
113 1
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
17 1
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
20 0
这个AI把arXiv变成代码工厂,快速复现顶会算法!Paper2Code:AI论文自动转代码神器,多智能体框架颠覆科研复现
Paper2Code是由韩国科学技术院与DeepAuto.ai联合开发的多智能体框架,通过规划、分析和代码生成三阶段流程,将机器学习论文自动转化为可执行代码仓库,显著提升科研复现效率。
384 19
这个AI把arXiv变成代码工厂,快速复现顶会算法!Paper2Code:AI论文自动转代码神器,多智能体框架颠覆科研复现
内网监控桌面与 PHP 哈希算法:从数据追踪到行为审计的技术解析
本文探讨了内网监控桌面系统的技术需求与数据结构选型,重点分析了哈希算法在企业内网安全管理中的应用。通过PHP语言实现的SHA-256算法,可有效支持软件准入控制、数据传输审计及操作日志存证等功能。文章还介绍了性能优化策略(如分块哈希计算和并行处理)与安全增强措施(如盐值强化和动态更新),并展望了哈希算法在图像处理、网络流量分析等领域的扩展应用。最终强调了构建完整内网安全闭环的重要性,为企业数字资产保护提供技术支撑。
89 2
18个常用的强化学习算法整理:从基础方法到高级模型的理论技术与代码实现
本文系统讲解从基本强化学习方法到高级技术(如PPO、A3C、PlaNet等)的实现原理与编码过程,旨在通过理论结合代码的方式,构建对强化学习算法的全面理解。
193 10
18个常用的强化学习算法整理:从基础方法到高级模型的理论技术与代码实现
员工行为监控软件中的 Go 语言哈希表算法:理论、实现与分析
当代企业管理体系中,员工行为监控软件已逐步成为维护企业信息安全、提升工作效能的关键工具。这类软件能够实时记录员工操作行为,为企业管理者提供数据驱动的决策依据。其核心支撑技术在于数据结构与算法的精妙运用。本文聚焦于 Go 语言中的哈希表算法,深入探究其在员工行为监控软件中的应用逻辑与实现机制。
110 14
基于 Python 哈希表算法的局域网网络监控工具:实现高效数据管理的核心技术
在当下数字化办公的环境中,局域网网络监控工具已成为保障企业网络安全、确保其高效运行的核心手段。此类工具通过对网络数据的收集、分析与管理,赋予企业实时洞察网络活动的能力。而在其运行机制背后,数据结构与算法发挥着关键作用。本文聚焦于 PHP 语言中的哈希表算法,深入探究其在局域网网络监控工具中的应用方式及所具备的优势。
104 7

热门文章

最新文章

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问