解决哈希表的冲突-开放地址法和链地址法 ---二次探测再散列的一个人名的例子

本文主要是介绍解决哈希表的冲突-开放地址法和链地址法 ---二次探测再散列的一个人名的例子,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在实际应用中,无论如何构造哈希函数,冲突是无完全避免的。

1 开放地址 


这个方基本思想是:当发生地址冲突时,按照某种方继续探测哈希表中的其他存储单元,直到找到空位置为止。

这个过程可用下式描述: 
H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… , k ( k ≤ m – 1)) 
其中: H ( key ) 为关键字 key 的直接哈希地址, m 为哈希表的长度, di 为每次再探测时的地址增量。 
采用这种方时,首先计算出元素的直接哈希地址 H ( key ) ,如果该存储单元已被其他元素占用,则继续查看地址为 H ( key ) + d 2 的存储单元,如此重复直至找到某个存储单元为空时,将关键字为 key 的数据元素存放到该单元。 
增量 d 可以有不同的取,并根据其取有不同的称呼: 
( 1 ) d i = 1 , 2 , 3 , …… 线性探测再散列; 
( 2 ) d i = 1^2 ,- 1^2 , 2^2 ,- 2^2 , k^2, -k^2…… 二次探测再散列; 
( 3 ) d i = 伪随机序列 伪随机再散列; 

例1设有哈希函数 H ( key ) = key mod 7 ,哈希表的地址空间为 0 ~ 6 ,对关键字序列( 32 , 13 , 49 , 55 , 22 , 38 , 21 )按线性探测再散列和二次探测再散列的方分别构造哈希表。 
解:
( 1 )线性探测再散列: 
32 % 7 = 4 ; 13 % 7 = 6 ; 49 % 7 = 0 ; 
55 % 7 = 6 发生冲突,下一个存储地址( 6 + 1 )% 7 = 0 ,仍然发生冲突,再下一个存储地址:( 6 + 2 )% 7 = 1 未发生冲突,可以存入。 
22 % 7 = 1 发生冲突,下一个存储地址是:( 1 + 1 )% 7 = 2 未发生冲突; 
38 % 7 = 3 ; 
21 % 7 = 0 发生冲突,按照上面方继续探测直至空间 5 ,不发生冲突,所得到的哈希表对应存储位置: 
下标: 0 1 2 3 4 5 6 
49 55 22 38 32 21 13 
( 2 )二次探测再散列: 
下标: 0 1 2 3 4 5 6 
49 22 21 38 32 55 13 
   注意:对于利用开放地址处理冲突所产生的哈希表中删除一个元素时需要谨慎,不能直接地删除,因为这样将会截断其他具有相同哈希地址的元素的查找地址,所以,通常采用设定一个特殊的标志以示该元素已被删除。 
2 链地址 

链地址解决冲突的做:如果哈希表空间为 0 ~ m - 1 ,设置一个由 m 个指针分量组成的一维数组 ST[ m ], 凡哈希地址为 i 的数据元素都插入到头指针为 ST[ i ] 的链表中。这种方有点近似于邻接表的基本思想,且这种方适合于冲突比较严重的情况。 

 例 2 设有 8 个元素 { a,b,c,d,e,f,g,h } ,采用某种哈希函数得到的地址分别为: {0 , 2 , 4 , 1 , 0 , 8 , 7 , 2} ,当哈希表长度为 10 时,采用链地址解决冲突的哈希表如下图所示。 


// hash_test.cpp : Defines the entry point for the console application.

//


#include "stdafx.h"
/*
int main(int argc, char* argv[])
{
printf("Hello World!\n");
return 0;
}
*/


#include<iostream>
#include<string>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<windows.h>
using namespace std;
#define HASH_LENGTH 40               //哈希表的长度
#define M  33                        //随机数
#define NAME_NO 30                   //人名的个数
typedef struct
{
    char *py;//名字的拼音
    char *name;
    int k;       //拼音所对应的整数
} NAME;
NAME NameList[HASH_LENGTH];    //全局变量NAME


typedef struct    //哈希表
{
    char *py;   //名字的拼音
    char *name;
    int k;      //拼音所对应的整数
    int si;     //查找长度/标记被占
} HASH;
HASH HashList[HASH_LENGTH];        //全局变量HASH
void InitNameList() //姓名(结构体数组)初始化
{
    char *f;
    int r,s0,i;
    for (i=0; i<HASH_LENGTH; i++)//★
    {
        NameList[i].py=(char*)malloc(sizeof(char)*20);//★开辟内存
        NameList[i].name=(char *)malloc(sizeof(char)*30);
        NameList[i].py[0] = 0;//★
    }
    /*FILE *pFile;
    if((pFile=fopen("D:\\Hash.txt","r"))==NULL)
       {
           printf("error\n");
           exit(1);
       }
    for(i=0;i<3;i++)
    {
        fscanf(pFile,"%s",NAME[i].py);
    }*/
    strcpy(NameList[0].py, "wangmin");//★
    strcpy(NameList[1].py, "yinqiang");//★
    strcpy(NameList[2].py, "dijuntao");//★
    strcpy(NameList[3].py, "sunhaitian");//★
    strcpy(NameList[4].py, "gaowendong");//★
    strcpy(NameList[5].py, "huoliya");//★
    strcpy(NameList[6].py, "yanbing");//★
    strcpy(NameList[7].py, "lusida");//★
    strcpy(NameList[8].py, "gebilaowang");//★
    strcpy(NameList[9].py, "tangqiuhu");//★
    strcpy(NameList[10].py, "yangchao");//★
    strcpy(NameList[11].py, "wangran");//★
    strcpy(NameList[12].py, "jishaopei");//★
    strcpy(NameList[13].py, "zhaobingkun");//★
    strcpy(NameList[14].py, "hehang");//★
    strcpy(NameList[15].py, "liyang");//★
    strcpy(NameList[16].py, "chengjingya");//★
    strcpy(NameList[17].py, "zhangmeng");//★
    strcpy(NameList[18].py, "wangzhenhua");//★
    strcpy(NameList[19].py, "zhangliyang");//★
    strcpy(NameList[20].py, "zhangyong");//★
    strcpy(NameList[21].py, "hehe"); //★
    strcpy(NameList[22].py, "jiangmei");//★
    strcpy(NameList[23].py, "zhangkexin");//★
    strcpy(NameList[24].py, "niuyajue");//★
    strcpy(NameList[25].py, "huodan");//★
    strcpy(NameList[26].py, "luoqijing");//★
    strcpy(NameList[27].py, "zhaocaiyu");//★
    strcpy(NameList[28].py, "chenglefeng");
    strcpy(NameList[29].py, "huanglaoshi");//*/


    strcpy(NameList[0].name, "王敏");//★
    strcpy(NameList[1].name, "尹强");//★
    strcpy(NameList[2].name, "第军涛");//★
    strcpy(NameList[3].name, "孙海天");//★
    strcpy(NameList[4].name, "高文东");//★
    strcpy(NameList[5].name, "霍立亚");//★
    strcpy(NameList[6].name, "闫兵");//★
    strcpy(NameList[7].name, "卢思达");//★
    strcpy(NameList[8].name, "隔壁老王");//★
    strcpy(NameList[9].name, "唐秋虎");//★
    strcpy(NameList[10].name, "杨超");//★
    strcpy(NameList[11].name, "王然");//★
    strcpy(NameList[12].name, "姬少培");//★
    strcpy(NameList[13].name, "赵丙坤");//★
    strcpy(NameList[14].name, "贺航");//★
    strcpy(NameList[15].name, "李阳");//★
    strcpy(NameList[16].name, "陈金亚");//★
    strcpy(NameList[17].name, "张萌");//★
    strcpy(NameList[18].name, "王振华");//★
    strcpy(NameList[19].name, "张理洋");//★
    strcpy(NameList[20].name, "张勇");//★
    strcpy(NameList[21].name, "赫赫"); //★
    strcpy(NameList[22].name, "江妹");//★
    strcpy(NameList[23].name, "张可心");//★
    strcpy(NameList[24].name, "牛亚娟");//★
    strcpy(NameList[25].name, "霍丹");//★
    strcpy(NameList[26].name, "罗绮靖");//★
    strcpy(NameList[27].name, "赵彩宇");//★
    strcpy(NameList[28].name, "程乐芬");
    strcpy(NameList[29].name, "黄老师");


    for(i=0; i<NAME_NO; i++)
    {
        s0=0;
        f=NameList[i].py;
        for(r=0; *(f+r)!='\0'; r++)
            /* 方法:将字符串的各个字符所对应的ASCII码相加,所得的整数做为哈希表的关键字*/
            s0=*(f+r)+s0;
        NameList[i].k=s0;
    }


}
void CreateHashList() //建立哈希表
{
    int i;
    for(i=0; i<HASH_LENGTH; i++)
    {
        HashList[i].py=(char*)malloc(sizeof(char)*20);
        HashList[i].name=(char*)malloc(sizeof(char)*30);
        HashList[i].py[0] = 0;
        HashList[i].name[0]=0;
        HashList[i].k=0;
        HashList[i].si=0;
    }
    for(i=0; i<NAME_NO; i++)//____________________修改处--壹--
    {
        int sum=0;
        int adr=(NameList[i].k)%M;
        //哈希函数
        int d=adr;
        if(HashList[adr].si==0)     //如果不冲突
        {
            HashList[adr].k=NameList[i].k;
            HashList[adr].py=NameList[i].py;
            HashList[adr].name=NameList[i].name;
            HashList[adr].si=1;
        }
        else   //冲突
        {
            int j=1;
            int h=1;
            int b=d;
            while ((HashList[d].k!=0)&&(h<=HASH_LENGTH/2))
            {
                if(j%2==1)//j为奇数时
                {
                    d=(b+h*h)%HASH_LENGTH;
                }
                else
                {
                    d=(b-h*h)%HASH_LENGTH;
                    h++;
                }
                j++;
                sum=sum+1;
                //查找成功所需查找次数加1
            };
            HashList[d].k=NameList[i].k;
            HashList[d].py=NameList[i].py;
            HashList[d].name=NameList[i].name;
            HashList[d].si=sum+1;
        }
    }
}
void FindList() //查找
{
    char name_1[20];
    int s0=0,r,sum=1,adr,d;
    printf("请输入姓名的拼音:\n");
    scanf("%s",name_1);
    for(r=0; name_1[r]!='\0'; r++) //求出姓名的拼音所对应的整数(关键字)
    {
        s0+=name_1[r];
    }
    printf("根据ASCII码值计算关键字为:%d\n",s0);
    adr=s0%M;   //使用哈希函数
    d=adr;
    if(HashList[adr].k==s0)          //分3种情况进行判断
    {
        printf("进入表中位置%d进行查找...\n",adr);
        //printf("数据匹配!查找成功!输出...\n");
        printf("姓名:%s   关键字:%d   查找长度:%d    哈希表中所存在的位置:%d\n",HashList[d].name,s0,sum,d);
    }
    else if(HashList[adr].k==0)
    {
        printf("进入表中位置%d进行查找...\n",adr);
        printf("哈希表中该位置无数据!查找失败!\n");
        printf("无此记录!\n");
    }
    else
    {
        printf("进入表中位置%d进行查找...\n",d);
        printf("数据不匹配!继续查找...\n");
        int g=0;
        int b=d;
        int j=1;
        int h=1;
        while(g==0)
        {
            if(j%2==1)//j为奇数时,+l*l
            {
                d=(b+h*h)%HASH_LENGTH;
            }
            else
            {
                d=(b-h*h)%HASH_LENGTH;
                h++;
            }
            //printf("第 %d 次解决冲突\n",j);
            //printf("进入表中位置%d进行查找...\n",d);
            printf("%d->",d);
            j++;
            sum=sum+1;
            if(HashList[d].k==0)
            {
                printf("哈希表中该位置无数据!查找失败!\n");
                printf("无此记录!\n");
                g=1;
            }
            else if(HashList[d].k==s0)
            {


                printf("数据匹配!查找成功!输出...\n");
                printf("★**************************************************************★\n");
                printf("姓名:%s   关键字:%d   查找长度:%d    哈希表中所存在的位置:%d\n",HashList[d].name,s0,sum,d);
                g=1;
            }
            else
            {
                //printf("数据不匹配!继续查找...\n");
                g=0;
            }
        }
    }
}
void   Display() // 显示哈希表
{
    int i;
    float average=0;
    printf("\n地址\t关键字\t\t查找长度\tH(key)\t 姓名\n");
    for(i=0; i<HASH_LENGTH; i++)
    {
        printf("%d",i);
        printf("\t%d",HashList[i].k);
        printf("\t\t%d",HashList[i].si);
        printf("\t\t%d",HashList[i].k%M);
        printf("\t%s",HashList[i].name);
        printf("\n");
    }
    for(i=0; i<HASH_LENGTH; i++)
        average+=HashList[i].si;
    average/=NAME_NO;
    printf("平均查找长度:ASL(%d)=%.2f\n",NAME_NO,average);


}
int main()
{
    char x;
    //system("color 0C");
    printf("\n");
    printf("\n");
    printf("\n");
    //printf("★********************************************************************★\n");
    printf("\n");
    printf("                           【二次探测再散列哈希表】         \n");
    printf("\n");
    //printf("★********************************************************************★\n");
    printf("\n");
    printf("\n");
    printf("\n");
    printf("\n");
    printf("\n");
    printf("                                                        信息工程学院");
    printf("                                                                    王敏\n");
    printf("                                                        学号:2010012851\n");
    printf("\n");
    printf("\n");
    printf("\n");
    printf("\n");
    printf("_______________");
    system("PAUSE");
    system("cls");
    /*printf("★********************************************************************★\n");
    printf("★**********          【二次探测再散列哈希表】         ***************★\n");
    printf("★********************************************************************★\n");*/
    printf("\n");
    printf("\n");
    InitNameList();
    CreateHashList ();
    printf("                       ★★****************★★\n");
    printf("                       ★    1.显示哈希表    ★\n");
    printf("                       ★    2.查找          ★\n");
    printf("                       ★    0.退出          ★                            \n");
    printf("                       ★    请选择...       ★                            \n");
    printf("                       ★★****************★★                            \n");


    while(cin>>x)
    {
        system("cls");
        if(x=='1')
        {
            printf("\n");
            printf("****************************哈希表********************************\n");
            printf("\n");
            printf("★**哈希表长:    %d    **★\n",HASH_LENGTH);
            printf("★**表中数据个数:%d    **★\n",NAME_NO);
            printf("★**随机函数:    %d    **★\n",M);
            Display();
            printf("★**************************************************************★\n");
            printf("请再次选择...");
        }
        else if(x=='2')
        {
            FindList();
            printf("★**************************************************************★\n");
            printf("★★****************★★\n");
            printf("★    1.显示哈希表  ★★\n");
            printf("★    2.查找        ★★\n");
            printf("★    0.退出        ★★                            \n");
            printf("★    请选择...     ★★                            \n");
            printf("★★****************★★                            \n");
        }
        else if(x=='0')
        {
            printf("欢迎下次使用!再见!");
            exit(1);
        }
        else
        {
            printf("请按提示操作!谢谢!不要调戏我的智商!谢谢!\n");
        }
    }
    for (int i=0; i<HASH_LENGTH; i++)
    {
        free(NameList[i].py);
        free(HashList[i].py);
        free(NameList[i].name);
        free(HashList[i].name);
    }
    return 0;
}

这篇关于解决哈希表的冲突-开放地址法和链地址法 ---二次探测再散列的一个人名的例子的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/821942

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

常用的jdk下载地址

jdk下载地址 安装方式可以看之前的博客: mac安装jdk oracle 版本:https://www.oracle.com/java/technologies/downloads/ Eclipse Temurin版本:https://adoptium.net/zh-CN/temurin/releases/ 阿里版本: github:https://github.com/

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路: 1. 用一个 hash[ ] 数组存放输入的数字,令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ,检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999,第二行数从 10到99。 4. 剪枝。 代码: /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h

如何解决线上平台抽佣高 线下门店客流少的痛点!

目前,许多传统零售店铺正遭遇客源下降的难题。尽管广告推广能带来一定的客流,但其费用昂贵。鉴于此,众多零售商纷纷选择加入像美团、饿了么和抖音这样的大型在线平台,但这些平台的高佣金率导致了利润的大幅缩水。在这样的市场环境下,商家之间的合作网络逐渐成为一种有效的解决方案,通过资源和客户基础的共享,实现共同的利益增长。 以最近在上海兴起的一个跨行业合作平台为例,该平台融合了环保消费积分系统,在短

整数Hash散列总结

方法:    step1  :线性探测  step2 散列   当 h(k)位置已经存储有元素的时候,依次探查(h(k)+i) mod S, i=1,2,3…,直到找到空的存储单元为止。其中,S为 数组长度。 HDU 1496   a*x1^2+b*x2^2+c*x3^2+d*x4^2=0 。 x在 [-100,100] 解的个数  const int MaxN = 3000

pip-tools:打造可重复、可控的 Python 开发环境,解决依赖关系,让代码更稳定

在 Python 开发中,管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等,都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools? pip-tools 是一组命令行工具,旨在简化 Python 依赖关系的管理,确保项目环境的稳定性和可重复性。它主要包含两个核心工具:pip-compile 和 pip

【VUE】跨域问题的概念,以及解决方法。

目录 1.跨域概念 2.解决方法 2.1 配置网络请求代理 2.2 使用@CrossOrigin 注解 2.3 通过配置文件实现跨域 2.4 添加 CorsWebFilter 来解决跨域问题 1.跨域概念 跨域问题是由于浏览器实施了同源策略,该策略要求请求的域名、协议和端口必须与提供资源的服务相同。如果不相同,则需要服务器显式地允许这种跨域请求。一般在springbo

webapp地址

F:\LSP\.metadata\.plugins\org.eclipse.wst.server.core\tmp0\wtpwebapps

哈希表的底层实现(1)---C++版

目录 哈希表的基本原理 哈希表的优点 哈希表的缺点 应用场景 闭散列法 开散列法 开放定值法Open Addressing——线性探测的模拟实现 超大重点部分评析 链地址法Separate Chaining——哈希桶的模拟实现 哈希表(Hash Table)是一种数据结构,它通过将键(Key)映射到值(Value)的方式来实现快速的数据存储与查找。哈希表的核心概念是哈希

速盾高防cdn是怎么解决网站攻击的?

速盾高防CDN是一种基于云计算技术的网络安全解决方案,可以有效地保护网站免受各种网络攻击的威胁。它通过在全球多个节点部署服务器,将网站内容缓存到这些服务器上,并通过智能路由技术将用户的请求引导到最近的服务器上,以提供更快的访问速度和更好的网络性能。 速盾高防CDN主要采用以下几种方式来解决网站攻击: 分布式拒绝服务攻击(DDoS)防护:DDoS攻击是一种常见的网络攻击手段,攻击者通过向目标网