精华内容
下载资源
问答
  • 2018-04-25 18:12:03

    题目:哈希表(链地址法处理冲突)

    连地址处理冲突:将产生冲突的值以链表的形式连起来

    好处:不会产生堆积,适合无法确定表长的情况,但是会增加空间消耗(指针需要空间)

    方法:采用结构体数组的方式,首先将结构体内每一个元素赋值 -1 NULL,然后采用插入的方式产生链表,同一个函数值得元素在一条链表上

    上代码:

    #include<iostream>
    using namespace std;
    typedef struct Ha
    {
    	int data;
    	struct Ha *next;
    }Ha;
    void insert(Ha ha[],int k,int num)
    {
    	Ha *p=&ha[k];
    	while(p->next !=NULL)  //始终存在 -1,NULL的节点
    	{
    		p=p->next ;
    	}
    	p->data =num;
    	Ha *q=new Ha;
    	q->data =-1;
    	q->next =NULL;
    	p->next=q ;     //注意先申请空间,然后再赋给上一节点
    }
    void serch(Ha ha[],int k,int num)
    {
    	Ha *p=&ha[k];
    	int sum=0;
    	while(p!=NULL)
    	{
    		sum++;
    		if(p->data ==num)
    		break;
    		p=p->next ;
    	}
    	if(p==NULL)cout<<"-1";  //整条链表没有所要找的值
    	else cout<<k<<","<<sum;
    }
    int main()
    {
    	int n;
    	cin>>n;
    	Ha ha[n];
    	for(int i=0;i<n;i++)
    	{
    		ha[i].data =-1;
    		ha[i].next =NULL;
    	}
    	int m;
    	cin>>m;
    	while(m--)
    	{
    		int num;
    		cin>>num;
    		insert(ha,num%n,num);
    	}
    	int x;
    	cin>>x;
    	serch(ha,x%n,x);
    	return 0;
    }

    更多相关内容
  • hash表一般都采用取余构造(将一个数对n取余然后根据余数来查找是否存在该数),当两个数的余数相同时仅仅凭借余数作为下标来查找就会发生错误即hash冲突,那么链地址法其实就是将余数相同的数用链表储存起来,那么...
  • 链地址法处理Hash冲突

    2019-04-11 01:24:48
    NULL 博文链接:https://128kj.iteye.com/blog/1683641
  • 1012: 哈希表(链地址法处理冲突) 题目描述 采用除留余数法(H(key)=key %n)建立长度为n的哈希表,处理冲突用链地址法。建立链表的时候采用尾插法。 输入 第一行为哈西表的长度m; 第二行为关键字的个数n; 第三...

    1012: 哈希表(链地址法处理冲突)

    题目描述
    采用除留余数法(H(key)=key %n)建立长度为n的哈希表,处理冲突用链地址法。建立链表的时候采用尾插法。
    输入
    第一行为哈西表的长度m;
    第二行为关键字的个数n;
    第三行为关键字集合;
    第四行为要查找的数据。
    输出
    如果查找成功,输出该关键字所在哈希表中的地址和比较次数;如果查找不成功,输出-1。
    样例输入
    13
    13
    16 74 60 43 54 90 46 31 29 88 77 78 79
    16
    样例输出
    3,1

    思路:
    哈希表(以下内容重在理解)

    1. 哈希表的基本概念: 哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
    • (tips:我对哈希表的浅显理解是将他比作图书馆书架,我们以后处理的数据的量少则十几万多则上亿,这个时候就用类似图书馆里的分类方法,分类后将数据存放在我们的电脑里,这样就会使得数据的查找较为简单。)
    1. 哈希表的构建方法
      ① 直接定址法:(了解就好)
      是以关键字 k 本身或关键字加上某个常量c 作为哈希地址的方法。直接定 址法的哈希函数 h(k)为: h(h)=k+c 例如,图 9. 30 所示的哈希表就是采用了这种方法。 这种方法的特点是哈希函数计算简单。当关键字的分布基本连续时, 可用直接定址法的哈希函数;否则,若关键字的分布不连续将造成内存单 视频讲解 元的大量浪费。

      ②除留取余法:(重点)
      是用关键字k除以某个不大于哈希表长度m的整数p所得的余数作为哈 希地址。除留余数法的哈希函数 h(k)通常为: h(h)= k mod p(mod 为求余运算,p≤m) 除留余数法的计算比较简单,适用范围广,是最经常使用的一种哈希函数。这种方法的 关键是选好 p,使得元素集合中的每一个关键字通过该函数转换后映射到哈希表范围内的 任意地址上的概率相等,从而尽可能减少发生冲突的可能性。例如,p 取奇数就比取偶数 好。理论研究表明,p 取不大于m的素数时效果最好。

      ③数字分析法:(了解就好)
      该方法是提取关键字中取值较均匀的数字作为哈希地址,它适用于所有关键字值都已知的情况,并需要对关键字中每一位的分布情况进行分析。

    2. 哈希表的冲突解决
      ①开放地址法
      开放定址法(open adresing 就是在出现哈希冲突时在哈希表中找一个新的空刚位! 存放元素。例如要存放关键字为A的元素,d=k(k),而地址为d的单元已经被其他元占用了,那么就在d地址的前后找空闲位置。

    • 就像某个人买了一张电影票,他晚到了电影院,他的位置被其他人占了,他就在周围找一个空座位坐下来。那么怎么找空闲单元呢?据开放定址法找空闲单元的方式又分为线性探测法和平方探测法等。

    a.线性探测法
    是从发生冲突的地址(设为 d)开始,依次探测 d,的下一个地 址(当到达下标为m-1的哈希表表尾时,下一个探测地址是表首地址 O),直到找到一个空闲 单元为止(当m>n时一定能够找到一个空闲单元)。

    • 以前面的看电影为例,假设 电影院座位只有一排(共 20 个座位),他的座位是 8(被其他人占了),线性探测法就是依次 查看 9.10.…,20 的座位是否为空的,有空就坐下,否则再查看 1,2,…,7 的座位是否为空 的,如此这样,他总可以找到一个空座位坐下。
      在这里插入图片描述

    b.平方探测法
    设发生冲突的地址为 d,平方探测法(square probing)的探测序列为 d+1, d一1, d十2^1 , d一2^1,…。平方探测法的数学描述公式为: d,= h(k) d,=(d,±i) mod m (1≤i≤m-1)

    • 仍以前面的看电影为例,平方探测法就是在他被占用的座位前后来回找空座位。 前后一个没找到就前后两个,找到为止。

    ②拉链法:
    把具有相同散列地址的关键字(同义词)值放在同一个单链表中,称为同义词链表。有m个散列地址就有m个链表,同时用指针数组T[0…m-1]存放各个链表的头指针,凡是散列地址为i的记录都以结点方式插入到以T[i]为指针的单链表中。T中各分量的初值应为空指针。
    在这里插入图片描述

    • 看似复杂的拉链法,其实就是用一个“数组”把几个链表串起来罢了。

    在这里插入图片描述
    【例】原本应该放在a[2]的数据a发现a[2]被占了,他就在a[2]接一个链表成为a[2]的“小弟”,后面相同类型的数据a1也是如此,他发现a[2]被占了,还发现的a[2]的“第一小弟”被占了,那就在“第一小弟数据a”后面接一个链表成为“a[2]的第二小弟”,注:xxxx为空。
    在这里插入图片描述

    1. 【拓展】哈希表的优缺点

      优点:
      无论数据有多少,处理起来都特别的快
      能够快速地进行 插入修改元素 、删除元素 、查找元素 等操作
      代码简单(其实只需要把哈希函数写好,之后的代码就很简单了)
      缺点:
      哈希表中的数据是没有顺序的
      数据不允许重复

    法一、拉链法
    采用除留余数法(H(key)=key %n)建立长度为n的哈希表,处理冲突用链地址法。建立链表的时候采用尾插法。

    #include<bits/stdc++.h>
    using namespace std;
    struct HTNode//储存值和下一个结点的结构体 
    {
    	int key;
    	struct HTNode *next;
    };
    struct HashTable//储存头结点的结构体 
    {
    	struct HTNode *head;
    };
    void InstHT(HashTable ha[],int n)
    {
    	for(int i=0;i<n;i++)
    	{
    		ha[i].head=NULL;
    	}
    }
    void CreateHT(HashTable ha[],int n,int data)//创建哈希表 
    {
    	int t=data%n;//计算哈希地址序号 
    	if(ha[t].head==NULL)//如果该序号的头结点为空 
    	{
    		HTNode *p;
    		p=(struct HTNode*)malloc(sizeof(struct HTNode));//p=new HTNode ();
    		p->key=data;//储存数据 
    		p->next=NULL;//将下一个结点设置为空 
    		ha[t].head=p;//赋值给头结点 
    	}
    	else//如果头结点不为空,则从头结点一直往后找到最后一个结点 
    	{
    		HTNode *p,*q;
    		p=ha[t].head;
    		while(p->next!=NULL) p=p->next;//查找到最后一个结点 
    		q=(struct HTNode*)malloc(sizeof(struct HTNode));//q=new();
    		q->key=data;
    		q->next=NULL;
    		p->next=q;//将新的结点接到最后 
    	}
    }
    void SearchHT(HashTable ha[],int n,int data)//查找哈希表 
    {
    	int t=data%n;//计算哈希地址序号 
    	HTNode *p;
    	p=ha[t].head;
    	for(int i=0; ;i++)//查找对应序号的链表 
    	{
    		if(p==NULL)//如果为空,则没有,输出-1
    		{
    			printf("-1");//cout<<"-1";
    			break;
    		}
    		else if(p->key==data)//如果有,则输出答案,并且跳出循环 
    		{
    			printf("%d,%d",t,i+1);//cout<<t<<i+1;
    			break;
    		}
    		else p=p->next;//否则继续向后查找 
    	}
    }
    int main()
    {
    	int n,k,data;
    	scanf("%d",&n);//cin>>n;
    	scanf("%d",&k);//cin>>k;
    	HashTable ha[n];
    	InstHT(ha,n);
    	for(int i=0;i<k;i++)
    	{
    		scanf("%d",&data);//cin>>data;
    		CreateHT(ha,n,data);
    	}
    	scanf("%d",&data);//cin>>data;
    	SearchHT(ha,n,data);
    }
     
    

    (代码出自孤雪胜悲鸣

    法二、奇淫技巧之二维数组

    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
     int i,j=0,a[50][10]={0},m,n,key,b[50]={0};    //m为哈希表长度,n为关键字的个数
     scanf("%d %d",&m,&n);//cin >> m >>n;
     for(i=0;i<n;i++)
     {
      scanf("%d",&key);//cin>>key;
      a[key%m][b[key%m]++]=key;               //将同一类型关键字放入同一行。
     }
     scanf("%d",&key);//cin>>key;
     for(i=0;i<n;i++)
     {
      if(a[key%m][i]==key){
       printf("%d,%d",key%m,i+1);  //cout << key%m <<i+1;                   //查找对应的关键字时直接遍历该行数,并输出在二维数组中所在位置与查找次数
       j++;
       break;
      }
     }
     if(j==0) printf("-1"); //cout << "-1";                          //如果没有找到,则输出-1
     return 0;
    }
    
    

    以上方法仅供参考,欢迎互联网的广大朋友们提出指正。

    展开全文
  • 采用除留余数(H(key)=key %n)建立长度为n的哈希表,处理冲突链地址法。建立链表的时候采用尾插。 输入 第一行为哈西表的长度m; 第二行为关键字的个数n; 第三行为关键字集合; 第四行为要查找的数据。 ...

    题目描述
    采用除留余数法(H(key)=key %n)建立长度为n的哈希表,处理冲突用链地址法。建立链表的时候采用尾插法。

    输入
    第一行为哈西表的长度m;
    第二行为关键字的个数n;
    第三行为关键字集合;
    第四行为要查找的数据。

    输出
    如果查找成功,输出该关键字所在哈希表中的地址和比较次数;如果查找不成功,输出-1。

    样例输入

    13
    13
    16 74 60 43 54 90 46 31 29 88 77 78 79
    16
    

    样例输出

    3,1
    

    题目给的样例输出好像不对,应该是3,2

    #include<stdio.h>
    #include<malloc.h>
    #include<string.h>
    #define MaxSize 1000
    typedef struct node
    {
        int key;
        struct node *next;
    }NodeType;
    typedef struct
    {
        NodeType*first;
    }HashTable;
    HashTable ha[MaxSize];//哈希表
    int keys[MaxSize];//存键值
    void Insert(HashTable ha[],int m,int key)
    {
        int adr;
        adr=key%m;//关键字%哈希表长度
        NodeType *q;
        q=(NodeType*)malloc(sizeof(NodeType));
        q->key=key;
        q->next=NULL;
        //通过链接形成某地址的哈希表
        if(ha[adr].first==NULL)
        {
            ha[adr].first=q;
        }else//头插法
        {
            q->next=ha[adr].first;
            ha[adr].first=q;
        }
    }
    void Seek(HashTable ha[],int m,int k)
    {
        int i=0,adr;
        adr=k%m;
        //判断是哪一个地址的哈希表
        NodeType *q;
        q=ha[adr].first;
        //q为当前地址的哈希表的头指针
        while(q!=NULL)
        {
            i++;
            if(q->key==k) break;
            q=q->next;
        }
        if(q!=NULL)
        printf("%d,%d",adr,i);
        else
        printf("-1");
    }
    int main()
    {
        int m,n,k;
        scanf("%d",&m);//哈希表长度
        scanf("%d",&n);//关键字个数
        for(int i=0;i<n;i++)
        {
            scanf("%d",&keys[i]);//关键字集合
        }
        for(int i=0;i<m;i++)
        {
            ha[i].first=NULL;
        }
        for(int i=0;i<n;i++)
        {
            Insert(ha,m,keys[i]);///插入哈希表
        }
        scanf("%d",&k);
        Seek(ha,m,k);
    }
    
    
    展开全文
  • Hash (链地址法处理冲突) Hash,一般翻译做散列、杂凑,或音译为哈希,是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值...

    Hash (链地址法处理冲突)

    Hash,一般翻译做散列、杂凑,或音译为哈希,是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。(百度百科)

    HashTable通过key来查找信息,极大提高了时间效率,但不同的信息可能拥有相同的key值,这就是冲突,这里用链地址法来解决冲突,即有冲突的信息具有相同的key值,将它们按顺序链接在同一地址下(尾插法)。
    来源于百度
    (百度图片)

    这里还有:Hash 哈希表 (开放地址法解决冲突)

    代码如下:

    in:
    13
    13
    16 74 60 43 54 90 46 31 29 88 77 78 79
    16
    out:
    3,1
    
    #include"bits/stdc++.h"
    using namespace std;
    
    #define MAX 24
    #define INIFINITE 201201//定义无限大 
    typedef char DataType;//定义数据类型 
    typedef int KeyType;//定义关键字类型 
    typedef struct node{
    	int key;//储存关键字信息 
    	struct node *next; 
    }HashListNode; 
    typedef struct{
    	DataType data; 
    	KeyType key;
    	HashListNode *firstare;//指向的第一片区域 
    }HashTable[MAX],Hash;
    
    int H(int key,int n){//除留余数 
    	return key%n;
    }
    void Init(Hash test[],int n){//初始化 
    	for(int i=0;i<n;i++){
    		test[i].key=INIFINITE;
    		test[i].firstare=NULL;//注意这的初始化 
    	}
    }
    void CreatHashList(HashListNode *&link,int key){//创建链地址 (尾插法) 
    	HashListNode *p;
    	p=new HashListNode;
    	p->key=key;
    	p->next=NULL;
    	if(!link){
    		link=p;
    	}
    	else{
    		while(link->next){
    			
    			link=link->next;
    		}
    		link->next=p;
    	}
    		
    }
    void CreateHash(Hash test[],int num,int n){//创建哈希表 
    	bool flag[MAX]={false};//冲突标记 
    	for(int i=0;i<num;i++){
    		int temp,k;
    		cin>>temp;//关键字信息 
    		k=H(temp,n);
    		if(!flag[k]){//若未冲突 
    			test[k].key=temp;
    			flag[k]=true; 
    		}
    		else{//处理冲突 
    			CreatHashList(test[k].firstare,temp);
    		}
    	}
    } 
    void SearchNode(Hash test[],int n){//查找结点,查找失败输出-1
    	int aim,count=0;
    	cin>>aim;//目标 
    	int k=H(aim,n);
    	bool flag=false;//查找到的标记 
    	if(test[k].key==INIFINITE){
    		cout<<"-1";
    		return;
    	}
    	
    	if(test[k].key==aim){
    		flag=true;
    		count++;
    	}
    	else{
    		count++;//下面直接从下一片区域找起  这要加一次   
    		while(test[k].firstare){
    			count++;
    			if(test[k].firstare->key==aim){
    				flag=true;
    				break;
    			}
    			test[k].firstare=test[k].firstare->next;
    		}
    	}
    	if(!count||!flag){
    		cout<<"-1";
    	}
    	else{
    		cout<<k<<","<<count;
    	}
    	
    }
    int main(){
    	HashTable test;
    	int n,num;
    	cin>>n>>num;
    	Init(test,n);
    	CreateHash(test,num,n);
    	SearchNode(test,n);
    	
    	return 0;
    }
    
    

    请多指教

    展开全文
  • 采用链地址法处理冲突构造哈希表

    千次阅读 2018-01-25 23:00:28
     通常用于处理冲突的方法有:开放定址、再哈希法、链地址法、建立一个公共溢出区等。。。  (3)在哈希表上进行查找的过程和哈希造表的过程基本一致。给定K值,根据造表时设定的哈希函数求得哈希地址,若表中...
  • 主要介绍了java开放地址法链地址法解决hash冲突的方法示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
  • ,并采用链地址法处理冲突。 试对关键字序列(22,41,53,46,30,13,01,67)构造哈希表, 求等概率情况下查找成功的查找长度,并设计构造哈希表的完整算法。 CODE: /* 使用哈希函数:H(k)=3k MOD 11 ,并采用...
  • 采用除留余数(H(key)=key %n)建立长度为n的哈希表,处理冲突链地址法。建立链表的时候采用尾插
  • 哈希表(链地址法处理冲突)c语言方法 采用除留余数法(H(key)=key %n)建立长度为n的哈希表,处理冲突用链地址法。建立链表的时候采用尾插法。 输入 第一行为哈西表的长度m; 第二行为关键字的个数n; 第三行为...
  • 哈希表 用链地址法解决冲突:(哈希函数是按名字第一个大写字母分的) 输入内容:学生的姓名跟成绩 操作:插入、修改、查找、删除学生;以及输出哈希表
  • 哈希表(链地址法处理冲突) 1000(ms) 10000(kb) 2526/6473 采用除留余数法(H(key)=key %n)建立长度为n的哈希表,处理冲突用链地址法。建立链表的时候采用尾插法。 输入 第一行为哈西表的长度m; 第二...
  • 哈希表(链地址法处理冲突) 1000(ms) 10000(kb) 2676 / 6911 采用除留余数法(H(key)=key %n)建立长度为n的哈希表,处理冲突用链地址法。建立链表的时候采用尾插法。 输入 第一行为哈西表的长度m; 第二行为...
  • 思路:因为给的数太大,开100000000的一个数组显然是会超内存的,但是100000个数让我们不得不用哈希思想,因为其他方法恐怕会TLE吧>>>>>>>>>>>>>>>>线性探测我感觉很麻烦,还很乱,于是就写链地址法吧。...
  • 并采用链地址法处理冲突。试对关键字序列(22,41,53,46,30,13,01,67)构造散列表,求等概率情况下查找成功的平均查找长度,并设计构造散列表的完整的算法。 分析 代码 核心代码: /* ht[]指的是散列表结点数组...
  • 这其实就是一种处理冲突的方法开放定址。 开放定址 所谓的开放定址就是一旦发生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入。 公式为: fi(key) = (f(key)+...
  • 哈希表处理。。。用链地址法处理。。。建立关键字的头指针,然后依次插入。。。
  • 链地址法处理冲突,构建哈希表:假设哈希表长为m,哈希函数为H(x),用链地址法处理冲 #include #include #define SIZE 12 typedef struct _HashNode { int data ; struct _HashNode *next; }...
  • 链地址法来解决冲突

    千次阅读 2020-07-06 21:51:04
    https://www.nowcoder.com/questionTerminal/858d5d6b72e24cf4b2ffc36aae04d433?orderByHotValue=0&pos=6&mutiTagIds=585
  • HASH地址冲突解决之链地址法

    千次阅读 2019-05-28 22:46:21
    原文地址《HASH地址冲突解决之链地址法》 1、什么是链地址法 在hash冲突产生时,将相同具有相同hash值的对象以链表的形式存储,更直白的表述就是数组中的每个元素不在是具体的每个要存储的对象了,每个元素代表具有...
  • 链地址法作为解决冲突

    千次阅读 2020-05-21 09:36:11
    设散列表的长度为10,散列函数H(n)=n mod 7,初始关键字序列为 (33,24,8,17,21,10),用链地址法作为解决冲突的方法,平均查找长度是 1.5 33%7 = 5 24%7 = 3 //第一次出现3 8%7 = 1 17%7 = 3 //第二次出现3,...
  • 采用除留余数(H(key)=key %n)建立长度为n的哈希表,处理冲突链地址法。建立链表的时候采用尾插。 Input 第一行为哈西表的长度;第二行为关键字的个数n; 第三行为关键字集合; 第四行为要查找的数据。 ...
  • 散列表在进行映射的时候经常会发生冲突,这里采用链接来解决链接映射冲突带来的问题
  • 本题请使用链冲突法解决冲突,即散列到相同地址后以建立子的方式解决元素冲突,因此本题不考虑总元素大于散列表大小而溢出的情况。重复元素只存一个。 Input 第一行数字表示要建立的散列表的大小,第二行表示要...
  • hashMap对各位小伙们来说,没有不知道的了,使用过的人想必或多或少的都了解一点hashMap的底层实现原理,总结来说就是,数组+链表,至于源码的实现,大家可参看源码,今天想说的是hashMap是怎么解决hash冲突的呢?...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 54,308
精华内容 21,723
关键字:

链地址法处理冲突

友情链接: KEY.zip