精华内容
下载资源
问答
  • 哈希表平均查找长度可以为0吗,老师上课说可以,说是不用比较,但我感觉至少也要1啊
  • 哈希表平均查找长度

    万次阅读 多人点赞 2017-08-13 10:53:31
    题目:关键字序列为:{38,25,74,63,52,48},哈希函数为H(k)=k%7,哈希表的长度为7,用线性探测和链地址法处理冲突,分别计算等概率情况下查找成功的平均查找长度。注:没给哈希表长度,给出装填因子时,可求哈希...

    题目:关键字序列为:{38,25,74,63,52,48},哈希函数为H(k)=k%7,哈希表的长度为7,用线性探测和链地址法处理冲突,分别计算等概率情况下查找成功的平均查找长度。

    注:没给哈希表长度,给出装填因子时,可求哈希表长度,
    可根据此公式装填因子=元素个数/表长推:表长=元素个数/装填因子。

    线性探测法

    这里写图片描述

    由上构造的哈希表如下:
    这里写图片描述

    等概率下查找成功的平均查找长度为:
    ASL=(1+3+1+1+2+4)/6=2

    链地址法
    这里写图片描述

    由上构造的哈希表如下:
    这里写图片描述

    等概率下查找成功的平均查找长度为:
    ASL=(1*4+2*2)/6=1.3

    展开全文
  • 哈希表(又名为是散列表) 散列是一个用于唯一标识对象并在一些预先计算的唯一索引(称为“密钥”)存储每个对象的过程。因此,对象以“键值”对的形式存储,这些项的集合被称为“字典”。可以使用该键值搜索每个...

    哈希表(又名为是散列表)
    散列是一个用于唯一标识对象并在一些预先计算的唯一索引(称为“密钥”)存储每个对象的过程。因此,对象以“键值”对的形式存储,这些项的集合被称为“字典”。可以使用该键值搜索每个对象。有多种不同的基于哈希的数据结构,但最常用的数据结构是哈希表。

    哈希表通常使用数组实现。

    哈希数据结构的性能取决于以下三个因素:

    哈希函数
    哈希表的大小
    碰撞处理方法
    下图展示了如何在数组中映射哈希。该数组的索引是通过哈希函数计算的。
    在这里插入图片描述
    今天主要讲一下哈希表平均查找长度ASL计算,也是常见面试题之一
    题目:关键字序列为:{30,25,80,63,52,48},哈希函数为H(k)=k%7,哈希表的长度为7,用线性探测和链地址法处理冲突,分别计算等概率情况下查找成功的平均查找长度。

    注:没给哈希表长度,给出装填因子时,可求哈希表长度,
    可根据此公式装填因子=元素个数/表长推:表长=元素个数/装填因子。

    线性探测法(通过数组保存)
    H(30)=30%7=2
    H(25)=25%7=4
    H(80)=80%7=3,和30冲突,往后移一位:4,又与25冲突,继续后移一位:5
    H(63)=63%7=0
    H(52)=52%7=3,后移三位为6
    H(48)=48%7=6,与52冲突,后移一位为0,再后移一位为1
    结果为:
    30 ——2
    25——4
    80——5
    63——7
    52——6
    48——1
    平均查找长度:查找次数和/数组个数
    (1+1+3+1+4+3)/6=2.2

    链地址法 (以链表形式存储)
    取模后值相同的在同一个链表中,即
    0——63
    1
    2
    3——30——80——52
    4——25
    5
    6——48
    等概率下查找成功的平均查找长度为:
    ASL=(14+21+3*1)/6=1.5

    展开全文
  • #include<stdio.h> #include<malloc.h> #include<stdlib.h> typedef struct //元素类型定义 ...typedef struct //哈希表类型定义 { DataType *data; int l...
    #include<stdio.h>
    #include<malloc.h>
    #include<stdlib.h>
    typedef struct		//元素类型定义
    {
    	int value;		//元素值
    	int hi;			//冲突次数
    }DataType;
    typedef struct		//哈希表类型定义
    {
    	DataType *data;
    	int length;		//哈希表的长度/
    	int num;		//表中元素个数
    }HashTable;
    void CreateHashTable(HashTable *H,int m,int p,int hash[],int n);
    int SearchHash(HashTable H,int k);
    void HashASL(HashTable H,int m);
    void DisplayHash(HashTable H,int m);
    int main()
    {
    	printf("请输入数据个数:\n");
    	int N;
    	scanf("%d",&N);
    	int hash[N];
    	int item;
    	printf("请输入数据:\n");
    	for(int i=0;i<N;i++){
    		scanf("%d",&item);
    		hash[i]=item;
    	} 
    	HashTable H;
    	int m,p,n,pos,v;
    	printf("请输入哈希表的长度,mod及元素个数:\n"); 
    	scanf("%d%d%d",&m,&p,&n);
    	CreateHashTable(&H,m,p,hash,n);
    	DisplayHash(H,m);
    	printf("请输入待查找的元素:\n");
    	scanf("%d",&v);
    	pos=SearchHash(H,v);
    	printf("元素%d在哈希表中的位置:%d\n",v,pos);
    	HashASL(H,m);
    }
    //构造哈希表,并处理冲突
    void CreateHashTable(HashTable *H,int m,int p,int hash[],int n)
    { 
    	int i,sum,addr,di,k=1;
    	//为哈希表分配存储空间
    	(*H).data=(DataType*)malloc(m*sizeof(DataType));
    	if(!(*H).data)	
    		exit(-1); 
    	(*H).num=n;			//初始化哈希表的元素个数
        (*H).length=m;		//初始化哈希表的长度
    	for(i=0;i<m;i++)	//初始化哈希表
    	{
    		(*H).data[i].value=-1;
    		(*H).data[i].hi=0;
    	}
    	//构造哈希表并处理冲突
    	for(i=0;i<n;i++)
    	{
    		sum=0;			//sum记录冲突次数
    		addr=hash[i]%p;	//利用除留余数法求哈希函数地址
    		di=addr;
    		if((*H).data[addr].value==-1)	//如果不冲突则将元素存储在表中
    		{
    			(*H).data[addr].value=hash[i];
    			(*H).data[addr].hi=1;
    		}
    		else			//用线性探测再散列法处理冲突
    		{
    			do 
    			{
    				di=(di+k)%m;
    				sum+=1;
    			} while((*H).data[di].value!=-1);
    			(*H).data[di].value=hash[i];
    			(*H).data[di].hi=sum+1;
    		}
    	}
    }
    int SearchHash(HashTable H,int v)
    //在哈希表H中查找值为v的元素
    {
    	int d,d1,m;
    	m=H.length;
    	d=d1=v%m;				//求v的哈希地址
    	while(H.data[d].value!=-1)
    	{
    		if(H.data[d].value==v)	//如果找到要查找的元素v,则返回v的位置
    			return d;
    		else					//如果不是要找的元素,则继续向后查找
    			d=(d+1)%m;
    		if(d==d1)				//如果找遍了哈希表中的所有位置还没有找到v,则返回0
    			return 0;
    	}
    	return 0;					//该位置不存在元素v
    }
    //求哈希表的平均查找长度
    void HashASL(HashTable H,int m)
    {
    	float average=0;
    	int i;
    	for(i=0;i<m;i++)
    		average=average+H.data[i].hi;
    	average=average/H.num;
    	printf("平均查找长度ASL:%.2f",average);
    	printf("\n");  
    }
    //输出哈希表
    void DisplayHash(HashTable H,int m)
    {
    	int i;
    	printf("哈希表地址:  ");
    	for(i=0;i<m;i++)		//输出哈希表的地址
    		printf("%-5d",i);
    	printf("\n");
    	printf("元素值value: ");
    	for(i=0;i<m;i++)		//输出哈希表的元素值
    		printf("%-5d",H.data[i].value);
    	printf("\n");
    	printf("冲突次数:    ");
    	for(i=0;i<m;i++)		//冲突次数
    		printf("%-5d",H.data[i].hi);
    	printf("\n");
    }

    请输入数据个数:
    8
    请输入数据:
    23 12 14 56 456 27 78 98
    请输入哈希表的长度,mod及元素个数:
    20 7 8
    哈希表地址:  0    1    2    3    4    5    6    7    8    9    10   11   12   13   14   15   16   17   18   19
    元素值value: 14   56   23   456  78   12   27   98   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1
    冲突次数:    1    2    1    3    4    1    1    8    0    0    0    0    0    0    0    0    0    0    0    0
    请输入待查找的元素:
    14
    元素14在哈希表中的位置:0
    平均查找长度ASL:2.63
    展开全文
  • 哈希表查找不成功时的平均查找长度计算和查找成功时的ASL 例如: 关键字集合   { 19, 01, 23, 14, 55, 68, 11, 82, 36 } 设定哈希函数 H(key) = key MOD 11 ( 表长=11 ) 查找成功次数: 1 ...

    哈希表查找不成功时的平均查找长度计算和查找成功时的ASL

    例如:  关键字集合 
            { 19, 01, 23, 14, 55, 68, 11, 82, 36 }

    设定哈希函数 H(key) = key MOD 11 ( 表长=11 )


    查找成功次数:    1      1    2     1    3    6     2       5     1

    查找不成功次数:10    9     8    7    6    5     4       3      2    1    1

    查找成功时的平均查找长度:ASL=(1+1+2+1+3+6+2+5+1)/9=22/9
    查找不成功时的平均查找长度:ASL=(10+9+8+7+6+5+4+3+2+1+1)/11=56/11
    说明:
    第n个位置不成功时的比较次数为,第n个位置到第1个没有数据位置的距离。
      如:第0个位置到第1个没有数据位置(9)的距离为10!





    展开全文
  • 如何计算哈希表查找失败时的平均查找长度

    万次阅读 多人点赞 2020-04-30 18:20:01
    1.请回答采用线性探测再散列和链地址法处理冲突构建的哈希表中,查找失败时的平均查找长度如何计算? 例:已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为:H(key)=keyMOD13,哈希表长为m=15,设每个记录...
  • 哈希表查找 平均查找长度 解析

    万次阅读 2012-05-03 15:23:12
    哈希表的装填因子 α 的定义如下:  α = 哈希表中元素个数 / 哈希表的长度 ...手工计算等概率情况下查找 成功 的平均查找长度公式  规则如下: ASLsucc=   其中 Ci 为置入每
  • 最近复习数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时不太理解,不知道到底是怎么计算出来的。看了几篇博客后终于知道如何计算了,总结如下。 例题: 将关键字序列(7、8、30、11、...
  • 哈希表平均查找长度

    千次阅读 2017-08-03 15:34:17
    查找成功时的平均查找长度 查找不成功时的平均查找长度 http://www.doc88.com/p-903238204265.html
  • ![图片说明](https://img-ask.csdn.net/upload/201602/09/1455031746_265651.png) 这个失败的长度是怎么计算出来的? 分子是怎么来的? 请大家具体讲讲~
  • 首先,推荐两个写的很好的关于哈希表查找——成功和不成功时的平均查找长度的博客,感谢分享! https://blog.csdn.net/longlovefilm/article/details/78009782 ... 尤其需要注意哈希表查找不成功时的平均查找长度。...
  • 哈希算法的平均查找长度计算

    万次阅读 多人点赞 2017-07-29 23:21:54
    将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0...(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。  Ans:  (1).首先明确一个概念装载因子,装载因
  • 对于查找成功时的平均查找长度,书上有明确的定义: 而题目设定条件都是在等概率下查找,所以ASL=(C0+C1+...+Cn)*1/n. 这就说明了查找成功是针对关键字查找的,最后除以关键字的总个数。 我们来看一道书上的例题...
  • 关于什么是哈希表,定义网上太多了,大家可以自行搜索,本文主要讲代码的实现 由于网上大部分是采用链地址法处理冲突,所以刚开使代码总卡着没法运行 在与哈希表的初始化 初始化方法可以自行选择,不初始化,没法...
  • 哈希表查找不成功的平均查找长度

    千次阅读 2017-05-27 10:40:52
    1.查找失败的情况:哈希表中不存在这个元素才会查找失败 2.查找失败的判定;见书 3.因为所查找的数是不确定的,因此可以取遍哈希函数的所有取值,而每一个取值相当于入口,从入口开始查找,当满足失败判定时,确认...
  • Question1: 将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组,散列...(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 Ans: (1).首先明
  • 哈希表等概率情况下查找成功和查找不成功的平均查找长度计算 最近复习了下数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫,不知道到底是怎么计算出来的。现在通过查阅...
  • https://zhidao.baidu.com/question/214308488.html
  • 哈希表查找失败的平均查找长度

    千次阅读 2019-10-09 18:02:18
    “它是中所有可能散列到的位置上要插入新元素时为找到空桶的探查次数的平均值。” 理解: 1. 散列表中已经含有之前插入的元素。 即已经不空了,若为空的话再插入元素的时候查找空位置一次就可以找到。 2. 这...
  • 哈希表查找不成功时的平均查找长度(zz)哈希表查找不成功怎么计算?解答:先建好表,然后可以算出每个位置不成功时的比较次数之和,再除以表空间个数! 例如:散列函数为hash(x)=x MOD 13,用线性探测,建立了哈希表...
  • 哈希表查找平均长度

    万次阅读 多人点赞 2018-08-11 22:24:55
    将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。...(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 一、查找成功平均长度 通过公式计算出存放的位置,如果该位置已经...
  • 继续小结,做到一道求 哈希表查找成功与查找不成功 情况下平均查找长度计算问题,迷惑了好一会,在这里总结下来: 首先,你要明白的是平均查找长度求的是期望,那么你就按照求期望的方法来求平均查找长
  • 编程实现:构造哈希表:在地址空间为0~12,对以下关键字序列:(Jan,Feb,Apr,May,Jun,Jul,Aug,Sep,Oct)建哈希表,并且求出等概率情况下查找成功与不成功的平均查找长度。 实现代码: typedef struct HashTable{ ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 22,235
精华内容 8,894
关键字:

哈希表的平均查找长度怎么计算