精华内容
下载资源
问答
  • 哈希表设计

    2021-01-03 20:06:32
    实验 哈希表设计 数据结构课设 发出来分享 水平有限 希望各位网友多多交流和指正 一、实验目的 熟练掌握哈希表的构造方法,深刻理解哈希表与其他结构表的实质性差别。 二、实验原理 程序的功能是对一批关键字集合...

    实验 哈希表设计

    数据结构课设 发出来分享 水平有限 希望各位网友多多交流和指正

    一、实验目的
    熟练掌握哈希表的构造方法,深刻理解哈希表与其他结构表的实质性差别。

    二、实验原理
    程序的功能是对一批关键字集合采用除留余数法和线性探测再散列的方法解决冲突来建立相应的哈希表和完成查找过程及平均查找长度的计算。
    【问题描述】
    研究哈希(HAXI)表查找技术的两个重要问题是:构造HAXI函数和处理冲突。现在要求针对某个数据集合中的关键字设计一个哈希表(选择合适的哈希函数和处理冲突的方法),完成HAXI表的建立、查找,并计算HAXI表查找成功的平均查找长度。HAXI函数的构造方法有多种,其中除留余数法是一种最简单和最常用的方法。
    考虑具体问题的关键字集合,如{19,14,23,1,68,20,84,27,55,11,10,79}这样一组数据和给定的哈希表长m 或哈希表的装填因子a,选用除留余数法和线性探测再散列技术解决冲突所形成的哈希表以及该哈希表在查找成功时的平均查找长度ASL。
    三、算法分析与设计
    1、算法分析
    HAXI表是根据设定的HAXI函数和处理冲突的方法将一组关键字映射到一个有限的连续的地址区间上,并以关键字在地址区间的“象”作为记录在表中的存储位置。因此我们可以采用动态分配的顺序存储结构表示HAXI表。
    2、数据结构设计

    typedef struct {
        KeyType key ;
    }ElemType;      //元素类型的定义
    ElemType  *HAXI;//动态分配的哈希表的首地址
    

    3、算法过程设计
    要采用先存入数据后创建哈希表,为了解决冲突的问题
    (1)void InPut(ElemType **ST,int n)输入n个数据存入采用动态分配的数组空间的数据表ST。
    (2)void Creat(ElemType **HAXI,ElemType ST,int n,int m)根据数据表ST,构造哈希表HAXI,n,m分别为数据集合ST和哈希表的长度。在哈希表创建的过程中用线性探测再散列技术确定存放位置,即while( (*HAXI)[j].key!=NULL) j=(j+1)%m;
    (3)int haxi(KeyType key,int m)在创建哈希表的时候为了解决冲突需要找到P,即小于或等于HAXI 表长的最大质数。
    (4)int search(ElemType *HAXI,KeyType key,int m,int &time)在表长为m的哈希表中查找关键字等于key的元素,并用 time记录比较次数,若查找成功,函数返回值为其在哈希表中的位置,否则返回-1。
    四、算法实现
    1、源程序(见附录)
    2、测试结果截图
    在这里插入图片描述

    附录:
    源程序:

    #include <iostream>
    #include <bits/stdc++.h>
    #define NULL 0
    using namespace std;
    typedef int KeyType;//元素的类型 
    typedef struct {
        KeyType key ;
    }ElemType;      //元素类型的定义
    
    int haxi(KeyType key,int m)
    {
    	int i,p,flag=1;
    	for(p=m;p>=2;p--)
    	{
    		for(i=2,flag=1;i<p/2&&flag;i++)
    		{
    			if(p%i==0) flag=0;
    		}
    		if(flag==1) break;
    	}
    	return key%p;
    }
    int search(ElemType *HAXI,KeyType key,int m,int &time)
    {
    	int i;
    	time=1;
    	i=haxi(key,m);
    	while(HAXI[i].key!=0 && HAXI[i].key!=key)
    	{
    		i++;
    		time++;
    	}
    	if(HAXI[i].key==0) return -1;
    	else return i;
    }
    void InPut(ElemType **ST,int n)
    {
    	KeyType key;
    	(*ST)=(ElemType*)malloc(n*sizeof(ElemType));
    	cout<<"请输入各个关键字"<<endl;
    	for(int i=0;i<n;i++)
    	{
    		cin>>(*ST)[i].key;
    	}
    }
    void Creat(ElemType **HAXI,ElemType *ST,int n,int m)
    {
    	int i,j;
    	(*HAXI)=(ElemType*)malloc(m*sizeof(ElemType));
    	for(i=0;i<m;i++)
    	{
    		(*HAXI)[i].key=NULL;
    	}
    	for(i=0;i<n;i++)
    	{
    		j=haxi(ST[i].key,m);
    		while( (*HAXI)[j].key!=NULL)
    		{
    			j=(j+1)%m;
    		}
    		(*HAXI)[j].key=ST[i].key;
    	}
    }
    int main()
    {
    	ElemType *ST,*HAXI;
    	KeyType key;
    	int n,m,stime=0,time=1;
    	cout<<"输入关键字个数和表长(n m且n<=m)"<<endl;
    	cin>>n>>m;
    	InPut(&ST,n);
    	Creat(&HAXI,ST,n,m);
    	for(int i=0;i<m;i++)
    	{
    		printf("%5d",i);
    	}
    	cout<<endl;
    	for(int i=0;i<m;i++)
    	{
    		printf("%5d",HAXI[i].key);
    	}
    	cout<<endl;
    	cout<<"输入要查找的关键字"<<endl;
    	cin>>key;
    	int k;
    	k=search(HAXI,key,m,time);
    	if(k!=-1)
    	{
    		cout<<"查找次数为:"<<time<<endl;
    	}
    	else
    	{
    		cout<<"查找失败"<<endl;
    	}
    	int i;
    	for(stime=0,i=0;i<n;i++)
    	{
    		search(HAXI,ST[i].key,m,time);
    		stime+=time;
    	}
    	cout<<"平均查找长度为:"<<(float)stime/n;
    	return 0;
    }
    /*
    19 14 23 1 68 20 84 27 55 11 10 79
    */
    
    
    
    展开全文
  • 哈希表课程设计数据结构实验报告——哈希表设计 针对某个集体中的人名设计一个哈希表,使得平均查找长度不超过R,完成相应的建立和查表程序. 1.2 人名为汉语拼音形式,最长不超过18个字符(如:庄双双 ...
  • 哈希表设计.exe

    2021-05-05 18:16:58
    哈希表设计.exe
  • 哈希表设计程序设计+数据结构实验报告 1.1 针对某个集体中的人名设计一个哈希表,使得平均查找长度不超过R,完成相应的建立和查表程序. 1.2 人名为汉语拼音形式,最长不超过18个字符(如:庄双双 zhuangshuangshuang)...
  • 对一批关键字集合采用开放定址哈希表的存储结构来建立相应的哈希表和完成查找过程。 (1) 熟练掌握哈希表的构造方法 (2) 理解哈希表与其他结构表的实质性差别。
  • 数据结构课程设计哈希表设计问题.doc
  • 哈希表设计源码HashList
  • 数据结构课程设计++哈希表设计数据结构课程设计++哈希表设计
  • 哈希表设计.rar

    2019-05-22 14:10:05
    针对某个集体(比如你所在的班级)中的“人名”设计一个哈希表,完成相应的建表和查表程序。 【基本要求】 假设人名为中国人姓名的汉语拼音形式。带填入哈希表的人名共有30个。哈希函数用除留余数法构造,用线性...
  • 数据结构 哈希表设计

    千次阅读 2017-12-31 16:10:55
    哈希表设计 一、实验目的 熟练掌握哈希表的构造方法,深刻理解哈希表与其他结构表的实质性差别。   二、实验内容 程序的功能是对一批关键字集合采用除留余数法和线性探测再散列的方法解决冲突来建立相应的哈希...

    实验6 哈希表设计

    一、实验目的

    熟练掌握哈希表的构造方法,深刻理解哈希表与其他结构表的实质性差别。

     

    二、实验内容

    程序的功能是对一批关键字集合采用除留余数法和线性探测再散列的方法解决冲突来建立相应的哈希表和完成查找过程及平均查找长度的计算。

    【问题描述】

        研究哈希(HAXI)表查找技术的两个重要问题是:构造HAXI函数和处理冲突。现在要求针对某个数据集合中的关键字设计一个哈希表(选择合适的哈希函数和处理冲突的方法),完成HAXI表的建立、查找,并计算HAXI表查找成功的平均查找长度。HAXI函数的构造方法有多种,其中除留余数法是一种最简单和最常用的方法。

    考虑具体问题的关键字集合,如{19142316820842755111079}这样一组数据和给定的哈希表长m 或哈希表的装填因子a,选用除留余数法和线性探测再散列技术解决冲突所形成的哈希表以及该哈希表在查找成功时的平均查找长度ASL

     

    【数据描述】

    HAXI表是根据设定的HAXI函数和处理冲突的方法将一组关键字映射到一个有限的连续的地址区间上,并以关键字在地址区间的“象”作为记录在表中的存储位置。因此我们可以采用动态分配的顺序存储结构表示HAXI表。

     

    typedef struct {

        KeyType key ;

    }ElemType;      //元素类型的定义

    ElemType  *HAXI;//动态分配的哈希表的首地址

     

    【算法描述】

    1、选择合适的哈希函数Hkey=key % pP为小于或等于HAXI 表长的最大质数);

    2、计算各个关键字的直接哈希函数值;

    3、根据处理冲突的方法建立哈希表,并输出;

    4、在哈希表中进行查找,输出查找的结果,以及所需和记录关键字比较的次数,并计算和输出在等概率情况下查找成功的平均查找长度。

     

     

    三、参考程序

    #include <stdlib.h>

    #include <stdio.h>

    #include <math.h>

    #include <conio.h>

    #define NULL 0

    typedef int KeyType;

    typedef struct {

      KeyType key ;

    }ElemType;

    int haxi(KeyType key,int m){

    /*根据哈希表长m, 构造除留余数法的哈希函数haxi*/

      int i,p,flag;

      for (p=m ; p>=2  ; p--)          /*p为不超过m的最大素数*/

        { for (i=2,flag=1;i<=p/2 &&flag;i++)

             if (p %i==0) flag=0;

          if (flag==1) break;

         }

     return  key%p;                   /*哈希函数*/

     }

     

    void inputdata(ElemType **ST,int n ){

    /*从键盘输入n个数据,存入数据表ST(采用动态分配的数组空间)*/

      KeyType key;

      int i;

      (*ST)=(ElemType*)malloc(n*sizeof(ElemType));

      printf("\nPlease input %d data:",n);

      for (i=0;i<n;i++)

         scanf("%d",&((*ST)[i].key));

    }

     

    void createhaxi(ElemType **HAXI,ElemType *ST,int n,int m){

      /*根据数据表ST,构造哈希表HAXI*n,m分别为数据集合ST和哈希表的长度*/

    int i,j;

      (*HAXI)=(ElemType*)malloc(m*sizeof(ElemType));

      for (i=0;i<m;i++) (*HAXI)[i].key=NULL;  /*初始化哈希为空表(以0表示空)*/

      for (i=0;i<n;i++){

      j=haxi(ST[i].key,m);                   /*获得直接哈希地址*/

        while ((*HAXI)[j].key!=NULL) j=(j+1)%m;/*用线性探测再散列技术确定存放位置*/

        (*HAXI)[j].key=ST[i].key;              /*将元素存入哈希表的相应位置*/

      }

    }

     

    int search(ElemType *HAXI,KeyType key,int m,int *time){

      /*在表长为m的哈希表中查找关键字等于key的元素,并用 time记录比较次数,

       若查找成功,函数返回值为其在哈希表中的位置,否则返回-1*/

    int i;

      *time=1;

      i=haxi(key,m);

      while (HAXI[i].key!=0 && HAXI[i].key!=key) {i++; ++*time;}

      if (HAXI[i].key==0) return -1;

      else return i;

    }

     

    main(){

      ElemType *ST,*HAXI;

      KeyType key;

      int i,n,m,stime,time;

      char ch;

      printf("\nPlease input n && m(n<=m)");    /*输入关键字集合元素个数和HAXI表长*/

      scanf("%d%d",&n,&m);

      inputdata(&ST,n);                        /*调用函数,输入n个数据*/

      createhaxi(&HAXI,ST,n,m);                /*建立哈希表*/

    /*输出已建立的哈希表*/

      printf("\nThe haxi Table is\n");    

      for (i=0;i<m;i++) printf("%5d",i);

      printf("\n");

      for (i=0;i<m;i++) printf("%5d",HAXI[i].key);

      /*哈希表的查找,可进行多次查找*/

    do {

           printf("\nInput the key you want to search:");

           scanf("%d",&key);

           i=search(HAXI,key,m,&time);

           if (i!=-1) {printf("\nSuccess,the position is %d ",i);/*查找成功*/

               printf("\nThe time of compare is %d",time);

              }

           else{ printf("\nUnsuccess");                 /*查找失败*/

        printf("\nThe time of compare is %d",time);

              }

           printf("\nContinue(y/n):\n");                /*是否继续查找yes or no*/

           ch=getch();

           }

    while (ch=='y' || ch=='Y') ;     

    /*计算表在等概率情况下的平均查找长度,并输出*/

         for (stime=0,i=0;i<n;i++) {

           search(HAXI,ST[i].key,m,&time);

           stime+=time;

        };

        printf("\nThe Average Search Length is%5.2f",(float)stime/n);

        ch=getch();

    }

    测试数据:

    按运行提示输入数据(关键字集合)ST,建立HAXI表,然后进行多次查找。

    Please input n && m(n<=m)12  15

    19 14 23 01 68 20 84 27 55 11 10 79

    The haxi Table is

    0  1    2    3    4   5   6   7   8   9   10   11  12   13   14

    14    1   68  27  55  19  20  84  79  23   11  10

    Input the key you want to search:27

    Success,the position is 4

    The time of compare is 4;

    Continue(y/n):y

    Input the key you want to search:68

    Success,the position is 3

    The time of compare is 1;

    Continue(y/n):n

    The Average Search Length is 2.5

     

    展开全文
  • 数据结构课程设计-哈希表设计 代码,报告,灰常完美
  • 山东科技大学学生课程设计 实习6哈希表设计 需求分析 1. 问题描述 针对某个集体比如你所在的班级中的人名设计一个哈希表使得平均查找长度均不超过R完成相应的建表和查表顺序 2. 基本要求 假设人名为中国人姓名的汉语...
  • 哈希表设计:针对某个集体中人名设计一个哈希表,使得平均查找长度不超过2,并完成相应的建表和查表程序。

    1 课题描述

    针对某个集体中人名设计一个哈希表,使得平均查找长度不超过2,并完成相应的建表和查表程序。

    2 问题分析和任务定义

    1)假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2。
    2)哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。
    3) 在输入人名过程中能自动识别非法输入,并给与非法输入的反馈信息要求重新输入。
    4)查找成功时,显示姓名及关键字,并计算和输出查找成功的平均查找长度

    3 逻辑设计

    1)数据类型:

    对于名字中包含的信息,名字的拼音使用字符串类型保存,由拼音字母ascll构成的关键字使用整数型保存。对于哈希表所包含的信息,姓名使用字符串类型保存,关键字使用整数型保存,哈希表中的元素使用整数类型保存。
    struct name///名字结构体
    {
    char s[30];
    int v;///ascll码值之和
    } NAME[N];
    struct hashs///哈希表结构体
    {
    char name[30];///名字
    int key;///关键字
    int sum;///哈希表中含有的元素个数
    } HASH[M];

    2)抽象数据类型:

    ADT Hash {
    数据对象D:D是具有相同特征的数据元素的集合。各数据元素均含有类型相同,可唯一标识数据元素的关键字。
    数据关系R:数据元素同属一个集合。
    init()
    操作结果:初始化姓名表。
    creathash()
    操作结果:建立哈希表。
    displayhash()
    操作结果:显示哈希表。
    display()
    操作结果:显示姓名表。
    searchhash()
    操作结果:查找姓名。
    }ADT Hash

    3)模块功能:

    功能上主要分为初始化姓名表,构建哈希表,显示姓名表,显示哈希表,从哈希表中
    查找姓名这五大功能。其中构建哈希表使用除留余数法构建,并用线性探测再散列的方法解决冲突。

    4 详细设计

    const int N=30;
    const int M=50;
    struct name///名字结构体
    {
    char s[30];
    int v;///ascll码值之和
    } NAME[N];
    struct hashs///哈希表结构体
    {
    char name[30];///名字
    int key;///关键字
    int sum;///哈希表中含有的元素个数
    } HASH[M];

    <1>初始化函数:void init()
    读取姓名信息,初始化成姓名表。

    <2>创建哈希表函数:void creathash()
    将读取信息建立的姓名表建立哈希表。

    <3>演示哈希表函数:void displayhash()
    打印哈希表中的信息。

    <4>演示姓名表函数:void display()
    打印姓名表中的信息。

    <5>查找哈希表中的姓名函数 void searchhash()
    按照输入的姓名查找其在哈希表中的位置,并打印信息。

    5 程序编码

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int N=30;
    const int M=50;
    struct name   //名字结构体
    {
        char s[30];
        int v;   //ascll码值之和
    } NAME[N];
    struct hashs   //哈希表结构体
    {
        char name[30];   //名字
        int key;   //关键字
        int sum;   //哈希表中含有的元素个数
    } HASH[M];
    void init()   //初始化
    {
        int i,j,sum;
        for(i=0; i<N; i++)
        {
            NAME[i].v=0;
        }
        strcpy(NAME[0].s,"houhuiyu");//侯慧玉
        strcpy(NAME[1].s,"liutongxuan");//刘同轩
        strcpy(NAME[2].s,"liujiyuan");//刘继源
        strcpy(NAME[3].s,"wuzhe");//吴哲
        strcpy(NAME[4].s,"yaofanqi");//姚蕃淇
        strcpy(NAME[5].s,"sunchuwen");//孙楚旻
        strcpy(NAME[6].s,"songmingxue");//宋明雪
        strcpy(NAME[7].s,"zhangyongfei");//张勇飞
        strcpy(NAME[8].s,"zhangnanshuang");//张楠爽
        strcpy(NAME[9].s,"xumingyan");//徐明燕
        strcpy(NAME[10].s,"zengguangxun");//曾广巡
        strcpy(NAME[11].s,"liyong");//李勇
        strcpy(NAME[12].s,"liwenyao");//李文瑶
        strcpy(NAME[13].s,"lichenchuangyi");//李陈创一
        strcpy(NAME[14].s,"yangbinxu");//杨滨旭
        strcpy(NAME[15].s,"sangtianqi");//桑天奇
        strcpy(NAME[16].s,"lianghongting");//梁宏婷
        strcpy(NAME[17].s,"wangfuqiang");//王富强
        strcpy(NAME[18].s,"wanghongyuan");//王洪远
        strcpy(NAME[19].s,"wangtongshu");//王童姝
        strcpy(NAME[20].s,"wangpeng");//王鹏
        strcpy(NAME[21].s,"aizhanpeng"); //艾展鹏
        strcpy(NAME[22].s,"yuanyuan");//袁媛
        strcpy(NAME[23].s,"hexinlin");//贺薪霖
        strcpy(NAME[24].s,"xinghongxuan");//邢鸿轩
        strcpy(NAME[25].s,"guofanshu");//郭芃妤
        strcpy(NAME[26].s,"chenxuyan");//陈旭艳
        strcpy(NAME[27].s,"hanyutao");//韩玉涛
        strcpy(NAME[28].s,"lushiteng");//鹿世腾
        strcpy(NAME[29].s,"huangqichang");//黄启昌
        for(i=0; i<N; i++)
        {
            sum=0;
            for(j=0; j<strlen(NAME[i].s); j++)
            {
                sum=sum+(NAME[i].s[j]-'a');
            }
            NAME[i].v=sum;   //名字字母ascll码之和
        }
    }
    void creathash()    //构造哈希表
    {
        int i;
        int n,m,counts;
        for(i=0; i<M; i++)
        {
            strcpy(HASH[i].name,"0");
            HASH[i].key=0;
            HASH[i].sum=0;
        }
        for(i=0; i<N; i++)
        {
            counts=1;
            n=(NAME[i].v)%47;
            m=n;
            if(HASH[n].sum==0)   //不冲突
            {
                strcpy(HASH[n].name,NAME[i].s);
                HASH[n].key=NAME[i].v;
                HASH[n].sum=1;
            }
            else   //如果发生了冲突
            {
                while(1)
                {
                    m=(m+1)%47;
                    counts++;
                    if(HASH[m].key==0)
                    {
                        break;
                    }
                }
                strcpy(HASH[m].name,NAME[i].s);
                HASH[m].key=NAME[i].v;
                HASH[m].sum=counts;
            }
        }
        return ;
    }
    void searchhash()
    {
        char name[30];
        int i,sum,n,m,counts;
        sum=0;
        n=0;
        counts=1;
        printf("请输入要查找人的姓名拼音:\n");
        scanf("%s",name);
        for(i=0; i<strlen(name); i++)
        {
            sum+=(name[i]-'a');
        }
        n=sum%47;
        m=n;
        if(strcmp(HASH[n].name,name)==0)
        {
            printf("姓名:%s 关键字:%d 查找长度:1\n",HASH[n].name,sum);
        }
        else if(HASH[n].sum==0)
        {
            printf("没有找到这条记录!!!\n");
        }
        else
        {
            while(1)
            {
                m=(m+1)%47;
                counts++;
                if(strcmp(HASH[m].name,name)==0)
                {
                    printf("姓名:%s 关键字:%d 查找长度:%d\n",HASH[m].name,sum,counts);
                    break;
                }
                if(HASH[m].key==0)
                {
                    printf("没有找到这条记录!!!\n");
                    break;
                }
            }
        }
    }
    void displayhash()   //演示哈希表
    {
        int i,sum;
        float ave;
        ave=0.0;
        sum=0;
        printf("\n地址\t关键字\t\t搜索长度\t姓名\n");
        for(i=0; i<M; i++)
        {
            printf("%d",i);
            printf("\t%d",HASH[i].key);
            printf("\t\t%d",HASH[i].sum);
            printf("\t%s",HASH[i].name);
            printf("\n");
        }
        for(i=0; i<M; i++)
        {
            sum+=HASH[i].sum;
        }
        ave=((sum)*1.0)/N;
        printf("\n");
        printf("平均查找长度ASL(%d)=%.3lf\n",N,ave);
        return ;
    }
    void display()
    {
        int i;
        for(i=0; i<30; i++)
        {
            printf("\n\t关键字\t\t姓名\n");
            printf("\t%d",NAME[i].v);
            printf("\t%s",NAME[i].s);
        }
        return ;
    }
    int menu()
    {
        printf("\n\n");
        printf("\t汉字姓名拼音哈希表展示查找系统\n");
        printf("\t1.展示姓名拼音和关键字\n");
        printf("\t2.展示哈希表\n");
        printf("\t3.查找关键字\n");
        printf("\t4.退出\n");
        printf("\n");
        printf("\n");
        return 0;
    }
    int main()
    {
        int n;
        int flag;
        flag=1;
        while(1)
        {
            menu();
    
            if(flag==1)
            {
                init();
                creathash();
                flag=0;
            }
            scanf("%d",&n);
            getchar();
            if(n<1||n>4)
            {
                printf("输入有误,请重新输入!!!\n");
                continue;
            }
            else
            {
                if(n==1)
                {
                    printf("展示所准备的姓名拼音及其所组成的关键字:\n");
                    display();
                }
                else if(n==2)
                {
                    displayhash();
                }
                else if(n==3)
                {
                    searchhash();
                }
                else if(n==4)
                {
                    return 0;
                }
            }
    
        }
        return 0;
    }
    

    6 程序调试与测试

    1)打印姓名表:

    在这里插入图片描述

    2)打印哈希表

    在这里插入图片描述

    3)查找姓名:

    在这里插入图片描述

    7 结果分析

    时间复杂度在没有冲突时是O(1),实际上要根据冲突多少来确定,最差情况下会退化成O(n)。空间复杂度是O(n)。

    展开全文
  • 算法与数据结构 哈希表设计 有调试可运行的代码,需求分析,概要设计,详细设计
  • 石家庄铁道大学 刘立嘉 算法与数据结构 实验五 哈希表设计
  • 哈希表设计问题.CPP

    2020-01-28 17:36:48
    功能描述:针对自己的班同学名单设计一个哈希表,使得平均查找长度不超过2,完成相应的建表和查表程序。 设计要求:假设人名为中国姓名的汉语拼音形式,哈希函数用除留余数法构造,用链表法处理冲突。
  • 哈希表设计思想及实现

    千次阅读 2018-09-02 20:07:53
    哈希表设计思想及实现 定义 哈希表在《算法4》这本书中是这么介绍的:哈希表其实又叫散列表,是算法在时间和空间上做出权衡的经典例子。如果一个表所有的键都是小整数,我们就可以用一个数组来实现无序的符号表...

    哈希表设计思想及实现

    定义

    哈希表在《算法4》这本书中是这么介绍的:哈希表其实又叫散列表,是算法在时间和空间上做出权衡的经典例子。如果一个表所有的键都是小整数,我们就可以用一个数组来实现无序的符号表,将键作为数组的索引而数组中i出存储的值就是它对应的值。其实散列表的思想也是这样的,只不过他的键的类型更加复杂,是这种简易方法的一种扩展。

    使用散列查找分为两步:

    1. 用散列函数将被查找的键转换为数组的一个索引。理想情况下,不同的键值都会转换成为不同的索引值,但是一般情况下我们会遇到多个键对应相同的索引值,这也就是所谓的散列冲突。
    2. 处理碰撞冲突的情况,常用得方法有两种:拉链法(链地址法)和线性探测法,下面也会介绍这两种方法。

    哈希函数

    其实要设计一个哈希表首先要做的就是散列函数的计算,通过散列函数就可以将键转换为数组的索引。其实哈希函数的设计是一个非常常见的一个研究方向,就像在我们的网络安全的密码设计的过程中,散列函数就是一个非常重要的理论。但是这里介绍的是最一般的哈希函数的设计思想。

    哈希函数其实就是将键准换为索引,那么这里的键可以用什么数据类型呢?其实常见的基本数据类型都可以,甚至是我们自己定义的数据类型也是可以的。下面将分开展开介绍。

    正整数

    对于小正整数的话直接用就可以了,对于小负整数的话进行一定的偏移就可以了,例如-100 - 100 —> 0 - 200

    对于大整数散列最常用的方法是除留余数法。

    例如一个身份证号:332112200007076666这个的话取模,让他模10000,取后4位6666作为索引,这样带来好处是节省空间,因为我们显然不可能开辟那么大的空间去让身份证号称为索引,太浪费空间了。但是这样也带来了一定的问题就是碰撞冲突的问题。还有一个问题就是直接取模的话容易造成键值的分布不均匀。所以一般采用的方式是模一个大素数,为什么是模一个素数就可以避免不均匀的情况,这个其实是数论里的问题,不探讨,知道方法就可以了。

    关于上面的情况举个例子介绍下:

    10 % 4 = 2         10 % 7 = 3
    20 % 4 = 0         20 % 7 = 6
    30 % 4 = 2         30 % 7 = 2
    40 % 4 = 0         40 % 7 = 5
    50 % 4 = 2         50 % 7 = 1

    那素数怎么取呢?给出一般的参考的取值

    这里写图片描述

    浮点数

    浮点数的话其实也是转换成为整数,然后使用除留余数法。

    那浮点数怎么转换成为整数呢?我们知道浮点数其实在计算机中是二进制数存在的,将二进制数变为整数就可以了。

    这里写图片描述

    字符串

    其实字符串我们也可以将其看成是大整数来处理。

    举个例子:

    166=1102+6101+6100 166 = 1 ∗ 10 2 + 6 ∗ 10 1 + 6 ∗ 10 0

    code=cB3+oB2+dB1+eB0 c o d e = c ∗ B 3 + o ∗ B 2 + d ∗ B 1 + e ∗ B 0

    hash(code)=(cB3+oB2+dB1+eB0)%M h a s h ( c o d e ) = ( c ∗ B 3 + o ∗ B 2 + d ∗ B 1 + e ∗ B 0 ) % M

    hash(code)=((((cB)+o)B+d)B+e))%M h a s h ( c o d e ) = ( ( ( ( c ∗ B ) + o ) ∗ B + d ) ∗ B + e ) ) % M

    hash(code)=((((c%M)B+o)%MB+d)%MB+e))%M h a s h ( c o d e ) = ( ( ( ( c % M ) ∗ B + o ) % M ∗ B + d ) % M ∗ B + e ) ) % M

    其实左后就准换成为上面公式的样子,其中B表示进制,M表示模的素数。

    其实转换成代码就是下面这样的:

    int hash = 0;
    for(int i = 0; i < s.length(); i++ )
        hash = (hash * B + s.charAt(i))%M

    组合类型

    所谓的组合类型也就是自定义的数据类型,也是可以转换成为大整数来处理。

    例如我定义了一个Student的数据类型

    Student:name , number,score:

    计算student的散列值如下:

    hash(student)=(((student.name%M)B+student.number)%MB+student.socre)%M h a s h ( s t u d e n t ) = ( ( ( s t u d e n t . n a m e % M ) ∗ B + s t u d e n t . n u m b e r ) % M ∗ B + s t u d e n t . s o c r e ) % M

    链地址法(拉链法)

    链地址法的原理时如果遇到冲突,他就会在原地址新建一个空间,然后以链表结点的形式插入到该空间。下面从百度上截取来一张图片,可以很清晰明了反应下面的结构。比如说我有一堆数据{1,12,26,337,353…},而我的哈希算法是H(key)=key mod 16,第一个数据1的哈希值f(1)=1,插入到1结点的后面,第二个数据12的哈希值f(12)=12,插入到12结点,第三个数据26的哈希值f(26)=10,插入到10结点后面,第4个数据337,计算得到哈希值是1,遇到冲突,但是依然只需要找到该1结点的最后链结点插入即可,同理353。

      这里写图片描述

    把一个值得hash值转换为一个数组的索引的代码如下:

    private int hash(K key){
        return (key.hashCode() & 0x7ffffff)%M;
    }

    通过& 0x7ffffff这种方式就可以将符号位屏蔽,也就是说我们就算是传入负数也没有关系。

    上面的图是每个地址存的是一个链表,在java8中当冲突达到一定的数量的时候就会将链表转换为红黑树,我们下面的实现用地址存一个TreeMap(java中的TreeMap的底层其实就是用红黑树来实现的)来具体的实现。

    这里写图片描述

    import java.util.TreeMap;
    
    public class HashTable<K, V> {
    
        private TreeMap<K, V>[] hashtable;
        private int size;
        private int M;
    
        public HashTable(int M){
            this.M = M;
            size = 0;
            hashtable = new TreeMap[M];
            for(int i = 0 ; i < M ; i ++)
                hashtable[i] = new TreeMap<>();
        }
    
        public HashTable(){
            this(97);
        }
    
        private int hash(K key){
            return (key.hashCode() & 0x7fffffff) % M;
        }
    
        public int getSize(){
            return size;
        }
    
        public void add(K key, V value){
            TreeMap<K, V> map = hashtable[hash(key)];
            if(map.containsKey(key))
                map.put(key, value);
            else{
                map.put(key, value);
                size ++;
            }
        }
    
        public V remove(K key){
            V ret = null;
            TreeMap<K, V> map = hashtable[hash(key)];
            if(map.containsKey(key)){
                ret = map.remove(key);
                size --;
            }
            return ret;
        }
    
        public void set(K key, V value){
            TreeMap<K, V> map = hashtable[hash(key)];
            if(!map.containsKey(key))
                throw new IllegalArgumentException(key + " doesn't exist!");
    
            map.put(key, value);
        }
    
        public boolean contains(K key){
            return hashtable[hash(key)].containsKey(key);
        }
    
        public V get(K key){
            return hashtable[hash(key)].get(key);
        }
    }

    动态空间处理

    我们上实现的时候把M的值取成了固定值,这个时候我们来分析下他的时间复杂度:

    如果放入哈希表中的元素的个数使N,每个地址中存放的元素的个数是N/M的,然后每个地址中存放的是TreeMap,也就是底层是红黑树,对于一个红黑树的查询一个元素的时间复杂度是O(logN/M)的。然而对于哈希表其实是查询的复杂度应该是O(1)的复杂度,因为底层就是数组,直接索引一个数组中的值也就是O(1)的复杂度。

    但是这里明显不符合啊?其实就是开辟的空间是固定的导致的,我们需要进行动态空间处理。怎么处理呢?其实就是把和动态数组的处理是一样的。当元素的个数大于阈值的时候就扩大空间,小于阈值时就压缩空间,具体如下:

    当平均每个地址承载的元素多过一定程度时就扩容:n/M >= upperTol;

    当平均每个地址承载的元素少于一定程度时就缩容:n/M < lowerTol;

    扩容的时候怎么去扩大,扩大成多少呢?因为空间的大小其实也就是我们要模的那个值,所以选取扩大空间大小是有要求的。其实扩大的参考值就是上面给出素数取值时一般参考的取值。

    具体的实现如下:

    private void resize(int newM){
            TreeMap<K, V>[] newHashTable = new TreeMap[newM];
            for(int i = 0 ; i < newM ; i ++)
                newHashTable[i] = new TreeMap<>();
    
            int oldM = M;
            this.M = newM;
            for(int i = 0 ; i < oldM ; i ++){
                TreeMap<K, V> map = hashtable[i];
                for(K key: map.keySet())
                    newHashTable[hash(key)].put(key, map.get(key));
            }
    
            this.hashtable = newHashTable;
        }

    开放地址法

    实现哈希表的另一种方式就是用大小为M的数组保存N个键值对,其中M > N。我们需要依靠数组中的空位解决碰撞冲突。基于这种策略的所有方法给统称为开放地址散列表。

    其实就是使用开放地址法来解决碰撞冲突的问题。具体的开放地址法是怎么来解决碰撞冲突的,书上给出的解释是这样的:

    这里写图片描述

    完整代码

    import java.util.TreeMap;
    
    public class HashTable<K extends Comparable<K>, V> {
    
        private final int[] capacity
                = {53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
                49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
                12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741};
    
        private static final int upperTol = 10;
        private static final int lowerTol = 2;
        private int capacityIndex = 0;
    
        private TreeMap<K, V>[] hashtable;
        private int size;
        private int M;
    
        public HashTable(){
            this.M = capacity[capacityIndex];
            size = 0;
            hashtable = new TreeMap[M];
            for(int i = 0 ; i < M ; i ++)
                hashtable[i] = new TreeMap<>();
        }
    
        private int hash(K key){
            return (key.hashCode() & 0x7fffffff) % M;
        }
    
        public int getSize(){
            return size;
        }
    
        public void add(K key, V value){
            TreeMap<K, V> map = hashtable[hash(key)];
            if(map.containsKey(key))
                map.put(key, value);
            else{
                map.put(key, value);
                size ++;
    
                if(size >= upperTol * M && capacityIndex + 1 < capacity.length){
                    capacityIndex ++;
                    resize(capacity[capacityIndex]);
                }
            }
        }
    
        public V remove(K key){
            V ret = null;
            TreeMap<K, V> map = hashtable[hash(key)];
            if(map.containsKey(key)){
                ret = map.remove(key);
                size --;
    
                if(size < lowerTol * M && capacityIndex - 1 >= 0){
                    capacityIndex --;
                    resize(capacity[capacityIndex]);
                }
            }
            return ret;
        }
    
        public void set(K key, V value){
            TreeMap<K, V> map = hashtable[hash(key)];
            if(!map.containsKey(key))
                throw new IllegalArgumentException(key + " doesn't exist!");
    
            map.put(key, value);
        }
    
        public boolean contains(K key){
            return hashtable[hash(key)].containsKey(key);
        }
    
        public V get(K key){
            return hashtable[hash(key)].get(key);
        }
    
        private void resize(int newM){
            TreeMap<K, V>[] newHashTable = new TreeMap[newM];
            for(int i = 0 ; i < newM ; i ++)
                newHashTable[i] = new TreeMap<>();
    
            int oldM = M;
            this.M = newM;
            for(int i = 0 ; i < oldM ; i ++){
                TreeMap<K, V> map = hashtable[i];
                for(K key: map.keySet())
                    newHashTable[hash(key)].put(key, map.get(key));
            }
    
            this.hashtable = newHashTable;
        }
    }
    展开全文
  • 内部排序算法比较、哈希表设计 数据结构

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 124,213
精华内容 49,685
关键字:

哈希表设计