精华内容
下载资源
问答
  • 哈希表平均查找长度

    万次阅读 多人点赞 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

    展开全文
  • 题意:给出哈希表的大小size,若不为素数则一直执行size++直至为素数。 给出n个数,进行哈希表的插入...//哈希表查找 平均查找长度 int size,n,m; int has[100005]; void insert(int x) //二次探测正增量方式进行插入

    题意:给出哈希表的大小size,若不为素数则一直执行size++直至为素数。
    给出n个数,进行哈希表的插入,利用二次探测(仅正增量)进行插入
    给出m个数,进行哈希表的查找,利用二次探测(仅正增量)进行查找

    #include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    //哈希表查找 平均查找长度 
    int size,n,m;
    int has[100005];
    void insert(int x) //二次探测正增量方式进行插入
    {
    	for(int i=0;i<=size;i++)
    	{
    		int pos=(x+i*i)%size;
    		if(has[pos]==0) //若此时pos位置为空
    		{
    			has[pos]=x; //x插入到了下标为pos的位置
    			return; 
    		} 
    	}
    	cout<<x<<" cannot be inserted."<<endl;
    }
    bool su(int x)
    {
    	if(x==0 || x==1)
    		return 0;
    	int k=sqrt(x);
    	for(int i=2;i<=k;i++)
    	{
    		if(x%i==0)
    			return 0;
    	}
    	return 1;
    }
    int main()
    {
    	int t[100005];
    	cin>>size>>n>>m;
    	while(!su(size))
    		size++;
    	for(int i=1;i<=n;i++)
    	{
    		cin>>t[i];
    		insert(t[i]);
    	}
    	int x,ans=0;
    	for(int i=1;i<=m;i++)
    	{
    		cin>>x;
    		for(int j=0;j<=size;j++) //二次探测正增量方式进行查找
    		{
    			ans++; //代指查找次数 
    			int pos=(x+j*j)%size;
    			if(has[pos]==0 || has[pos]==x) //查找到为NULL表示查找失败 或者 查找成功 就break 
    				break;
    		}
    	}
    	printf("%.1f\n",1.0*ans/m); 
    }
    
    展开全文
  • 哈希表查找不成功时的平均查找长度 哈希表查找不成功时的平均...例如:散列函数为hash(x)=x MOD 13,用线性探测,建立了哈希表之后,如何查找不成功时的平均查找长度!?  地址: 0 1 2 3 4 5 6 7 8 9

    哈希表查找不成功时的平均查找长度

    哈希表查找不成功时的平均查找长度(zz)哈希表查找不成功怎么计算?解答:先建好表,然后可以算出每个位置不成功时的比较次数之和,再除以表空间个数!
    例如:散列函数为hash(x)=x MOD 13,用线性探测,建立了哈希表之后,如何求查找不成功时的平均查找长度!?
         地址: 0   1   2   3   4   5   6   7   8   9   10   11   12

         数据: 39  12  28  15  42  44   6  25  -  -   36   -   38

      成功次数: 1   3   1   2   2   1   1   9           1        1

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

    查找成功时的平均查找长度:ASL=(1+3+1+2+2+1+1+9+1+1)/10 =2.2

    查找不成功时的平均查找长度:ASL=(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=4.54

    说明:

    查找成功代表找到KEY所在位置所用的次数

    第n个位置不成功时的比较次数为,第n个位置到第1个没有数据位置的距离。

    至少要查询多少次才能确认没有这个值。

    (1) 查询hash(x)=0,至少要查询9次遇到表值为空的时候,才能确认查询失败。

    (2) 查询hash(x)=1,至少要查询8次遇到表值为空的时候,才能确认查询失败。

    (3) 查询hash(x)=2,至少要查询7次遇到表值为空的时候,才能确认查询失败。

    (4) 查询hash(x)=3,至少要查询6次遇到表值为空的时候,才能确认查询失败。

    (5) 查询hash(x)=4,至少要查询5次遇到表值为空的时候,才能确认查询失败。

    (6) 查询hash(x)=5,至少要查询4次遇到表值为空的时候,才能确认查询失败。

    (7) 查询hash(x)=6,至少要查询3次遇到表值为空的时候,才能确认查询失败。

    (8) 查询hash(x)=7,至少要查询2次遇到表值为空的时候,才能确认查询失败。

    (9) 查询hash(x)=8,至少要查询1次遇到表值为空的时候,才能确认查询失败。

    (10)查询hash(x)=9,至少要查询1次遇到表值为空的时候,才能确认查询失败。

    (11)查询hash(x)=10,至少要查询2次遇到表值为空的时候,才能确认查询失败。

    (12)查询hash(x)=11,至少要查询1次遇到表值为空的时候,才能确认查询失败。


    (13)查询hash(x)=12,至少要查询10次遇到表值为空(循环查询顺序表)的时候,才能确认查询失败。

     

    http://hi.baidu.com/dfsfsdfwe/item/35f8f1c79e91f26389ad9e53

    展开全文
  • 哈希表:线性探测法和链地址法查找成功与不成功的平均查找

    哈希表:线性探测法和链地址法求查找成功与不成功的平均查找长度

    了解ASL的公式

    查找成功时:ASL =1n\frac{1}{n} i=1nCi\sum_{i=1}^{n} C_i
      n 为散列表中记录的个数( 不是表的长度 ),
      Ci 为查找成功的第 i 个记录所需要的比较次数( 表中空的记录意味着不成功,是不算在里面滴

    查找不成功时:ASL =1r\frac{1}{r} i=1nCi\sum_{i=1}^{n} C_i
      r 为散列函数取值的个数( 不是表的长度 )。这个就充分解释了为什么散列函数 H(Key) = (key) MOD 11 在计算查找不成功ASL时,r = 11了,是因为这个散列函数的取值为 0~10,可以取11个值,所以 r = 11。
      Ci 为 散列函数取值为 i 时,查找失败时第 i 个记录所需要的比较次数( 表中的有些部分,散列函数根本取不到,自然也就不在计算里了

    我想只要把这两个公式看懂,查找成功与不成功的ASL也就自然会求了。下面线性探测法和链地址法我各举一个例子。

    线性探测法求ASL

    将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中,散列函数为H(Key) = (key x 3) MOD 7,处理冲突采用线性探测再散列法,要求装填因子为0.7

    装填因子 a = \frac{表中装入的记录个数}{散列表的长度} = 0.7,可以求出散列表表长 = 70.7\frac{7}{0.7} = 10
    (7x3)mod 7 = 0,因此散列地址为 0
    (8x3)mod 7 = 3,因此散列地址为 3
    (30x3)mod 7 = 6,因此散列地址为 6
    (11x3)mod 7 = 5,因此散列地址为 5
    (18x3)mod 7 = 5,此时和11冲突,使用线性探测法(地址+1),又和30冲突,地址再次+1,无冲突,散列地址为 7
    (9x3)mod 7 = 6,此时和30冲突,使用线性探测法(地址+1),又和18冲突,地址再次+1,无冲突,散列地址为 8
    (14x3)mod 7 = 0,此时和7冲突,使用线性探测法(地址+1),无冲突,散列地址为 1


    线性探测法处理冲突构造所得的哈希表如下:

    地址 0 1 2 3 4 5 6 7 8 9
    key 7 14 8 11 30 18 9

    根据公式:查找成功时ASL = 1n\frac{1}{n} i=1nCi\sum_{i=1}^{n} C_i
    如果查找7,则需要查找1次。
    如果查找8,则需要查找1次。
    如果查找30,则需要查找1次。
    如果查找11,则需要查找1次。
    如果查找18,则需要查找3次:第一次查找地址5,第二次查找地址6,第三次查找地址7,查找成功。
    如果查找9,则需要查找3次:第一次查找地址6,第二次查找地址7,第三次查找地址8,查找成功。
    如果查找14,则需要查找2次:第一次查找地址0,第二次查找地址1,查找成功。
    所以,查找成功时ASL=(1+2+1+1+1+3+3)/ 7 = 12/ 7

    根据公式:查找不成功时ASL = 1r\frac{1}{r} i=1nCi\sum_{i=1}^{n} C_i
    举个例子来说吧:
      如果要查找key为9的关键字。根据散列函数可以计算H(key)=H(9)=6。
      此时在会检测地址为6的值,发现key=30,不等于9。这就说明在装填的时候发生了冲突
      根据冲突处理方法,会继续检测地址为0的值,之所以没有检测地址7,8,9H(key)的取值取不到这些值。检测地址为0的值,发现key=7,依然不等
      根据冲突处理方法,会继续检测地址为1的值,发现key=14,依然不等
      根据冲突处理方法,会继续检测地址为2的值发现key为空
       这就说明关键字9从应该出现的地址6,一直查找,找到值为空的地址都没有和9相等的,说明散列表中没有9这个值,因此探测次数为4次

    根据上面的例子
    查找地址为0的值所需要的次数为3,
    查找地址为1的值所需要的次数为2,
    查找地址为2的值所需要的次数为1,
    查找地址为3的值所需要的次数为2,
    查找地址为4的值所需要的次数为1,
    查找地址为5的值所需要的次数为5,
    查找地址为6的值所需要的次数为4。
    所以,查找不成功ASL=(3+2+1+2+1+5+4)/ 7 = 18/ 7

    链地址法求ASL

    将关键字序列{1 13 12 34 38 33 27 22} 散列存储到散列表中。散列函数为:H(key)=key mod 11,处理冲突采用链地址法,求在等概率下查找成功和查找不成功的平均查找长度

    1mod11=1,因此散列地址为1
    13mod11=2,因此散列地址为2
    12mod11=1,因此散列地址为1(这个数据是数据1指针的另一个新数据)
    34mod11=1,因此散列地址为1(这个数据是数据12指针的另一个新数据)
    38mod11=5,因此散列地址为5
    33mod11=0,因此散列地址为0
    27mod11=5,因此散列地址为5(这个数据是数据38指针的另一个新数据)
    22mod11=0,因此散列地址为0(这个数据是数据33指针的另一个新数据)

    链地址法处理冲突构造所得的哈希表如下:
    在这里插入图片描述
    根据公式:查找成功时ASL = 1n\frac{1}{n} i=1nCi\sum_{i=1}^{n} C_i
    如果查找1,则需要查找3次。从地址1开始查,第一次查到34,第二次查到12,第三次查到1。
    如果查找13,则需要查找1次。
    如果查找12,则需要查找2次。从地址1开始查,第一次查到34,第二次查到12。
    如果查找34,则需要查找1次。
    如果查找38,则需要查找2次。从地址5开始查,第一次查到27,第二次查到38。
    如果查找33,则需要查找2次。从地址0开始查,第一次查到22,第二次查到33。
    如果查找27,则需要查找1次。
    如果查找22,则需要查找1次。
    所以,查找成功ASL =(3×1+2×3+1×4)/8 = 13/8

    根据公式:查找不成功时ASL = 1r\frac{1}{r} i=1nCi\sum_{i=1}^{n} C_i
    举个例子来说吧:
    如果要查找key为16的关键字。根据散列函数可以计算H(key)=H(16)=5。
      首先从地址5开始查找,第一次查找到的数据是27,和16不相等,继续往后找。
      第二次查找到的数据是38,和16不相等,继续往后找。
      第三次查找到的数据是空,查找结束。 意味着在地址5这一行找不到关键字16,因为如果关键字16在表中存在的话,只可能在地址5这一行,现在在地址5这一行找不到,意味着整个表也找不到。

    如果要查找key为20的关键字。根据散列函数可以计算H(key)=H(20)=9。
      首先从地址9开始查找,第一次查找到的数据是空,查找结束。意味着表中不存在关键字20。

    根据上面的例子
    查找地址为0的值所需要的次数为3,
    查找地址为1的值所需要的次数为4,
    查找地址为2的值所需要的次数为2,
    查找地址为3的值所需要的次数为1,
    查找地址为4的值所需要的次数为1,
    查找地址为5的值所需要的次数为3,
    查找地址为6的值所需要的次数为1,
    查找地址为7的值所需要的次数为1,
    查找地址为8的值所需要的次数为1,
    查找地址为9的值所需要的次数为1,
    查找地址为10的值所需要的次数为1。
    所以,查找不成功ASL = (3+4+2+1+1+3+1+1+1+1+1)/11 = 19/11

    其实不管是线性探测法还是链地址法,在求查找不成功ASL时,都是差不多的。首先根据散列函数找到地址,然后从这个地址往后查,一直查到空结束。

    展开全文
  •  首先,你要明白的是平均查找长度求的是期望,那么你就按照求期望的方法来求平均查找长度吧,千万记着期望怎么求平均查找长度就怎么求啊。  题目: 在地址空间为0~16的散列区中,对以下关键字序列构造两个哈希表...
  •  首先,你要明白的是平均查找长度求的是期望,那么你就按照求期望的方法来求平均查找长度吧,千万记着期望怎么求平均查找长度就怎么求啊。  题目: 在地址空间为0~16的散列区中,对以下关键字序列构造两个...
  • 首先,你要明白的是平均查找长度求的是期望,那么你就按照求期望的方法来求平均查找长度吧,千万记着期望怎么求平均查找长度就怎么求啊。 题目: 在地址空间为0~16的散列区中,对以下关键字序列构造两个哈希...
  • 编程实现:构造哈希表:在地址空间为0~12,对以下关键字序列:(Jan,Feb,Apr,May,Jun,Jul,Aug,Sep,Oct)建哈希表,并且出等概率情况下查找成功与不成功的平均查找长度。 实现代码: typedef struct HashTable{ ...
  • 完整举例: 在地址空间为0~16的散列区中,对以下关键字序列构造两个...查找成功与查找不成功的平均查找长度。 很据:H(x)=i/2;除不尽的,向下取整即可。如下所示: Jan - 5 Feb - 3 Mar -6 Apr -0 May - 6 June -5
  • 题目:关键字序列为:{38,25,74,63,52,48},哈希函数为H(k)=k%7,哈希表的长度为7,用线性探测和链地址法处理冲突,分别计算等概率情况下查找成功的平均查找长度。 注:没给哈希表长度,给出装填因子时,可...
  • 它通过对元素关键字值进行某种运算,直接出元素的地址,即使用关键字到地址的直接转换方法,而不需要反复比较。因此散列查找法又称为杂凑法或散列法散列表中的术语:散列函数和散列地址:在记录的存储位置p和其...
  • 此代码可以正常运行,下附有运行区 ...int GetPrimeNum(int a) //最大素数(质数) { int t=a; while(t>0) //>1也可 { t--; int flag=1; for(int i=2;i<t;i++) { if(t%i==0) { .
  • 比如,给定一组元素78、90、66、70、155、82、123、231,设哈希表长m=11,p=11,n=8,要求构造一个哈希表,并用线性探测再散列法处理冲突,并求平均查找长度。 【哈希表的定义】 哈希表是利用待查找元素与元素的...
  • 设哈希函数H(K)=3Kmod11,哈希地址空间为0~10,对关键字序列(32,13,49,24,38,21,4,12),按下述两种解决冲突的方法构造哈希表,并分别出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和...
  • 做到一道求 哈希表查找成功与查找不成功 情况下平均查找长度的计算问题,迷惑了好一会,在这里总结下来:  首先,你要明白的是平均查找长度求的是期望,那么你就按照求期望的方法来求平均
  • 哈希表查找不成功的ASL问题

    千次阅读 多人点赞 2017-10-24 23:07:31
     首先,你要明白的是平均查找长度求的是期望,那么你就按照求期望的方法来求平均查找长度吧,千万记着期望怎么求平均查找长度就怎么求啊。  题目: 在地址空间为0~16的散列区中,对以下关键字序列构造两个...
  • 链式地址&线性探测的平均查找长度

    千次阅读 2020-08-15 21:59:15
    题目:已知关键字序列为:(75,33,52,41,12,88,66,27),哈希表长为10,哈希函数为:H(k)=kmod7,解决冲突用线性探测再散列法,要求构造哈希表出等概率下查找成功的平均查找长度。 1、首先计算该...
  • 哈希表

    2019-05-04 15:44:34
    给定一组元素的关键字hash[] = {78,90,66,70,155,82,123,231},利用除留余数法和线性再探测散列法将元素存储再哈希表中,并查找给定的关键字,求平均查找长度。 分析:主要考察哈希表的构造和冲突解决办法 代码: #...
  • 就除留取余发来复习一下哈希查找 除留取余发的表达式f(k)=k%p, 其中f(k)为关键字K的地址 P为小于等于哈希表空间长度的...解:1 构造哈希表 2 成功与不成功的平均查找次数ASL 第一步 : 确定哈希函数中的P,因为哈希表
  • 哈希表的实现

    2019-10-14 23:18:18
    哈希表容易造成冲突,为了避免冲突: 1.尽可能的让出来的下标符合均匀分布。 2.负载因子的调节 负载因子=哈希表中的数据个数/...成功的平均查找长度和失败的平均查找长度 代码实现开散列 public class Hash { ...
  • 哈希表习题

    千次阅读 2019-12-05 19:44:15
    选取哈希函数H(k)=(3k)%11,用线性探测散列法和二次探测再散列法分别处理...试在0~10的散列地址空间中,对关键字序列(22,41,53,46,30,13,01,67)构建哈希表,并等概率情况下查找成功的平均查找长度。 线性探测...
  • 线性探测哈希表

    2020-06-22 23:02:07
    5.给定一个关键字序列(13,4,18,20,32,15,9,24),哈希表长度为 11,哈希函数为 H(Key)=Key%11,采用线性探测法解决冲突,画出构造的哈希表(8 分),并出等概率查找查找成功 的 ASL(成功) (1 分),...
  • SCAU 8622 哈希查找

    2020-05-21 16:05:46
    试对输入的关键字序列构造哈希表哈希表长度为length,等概率情况下查找成功的平均查找长度,并设计构造哈希表的完整的算法。本题给出部分代码,请补全Hash函数和解决冲突的collison函数。 #include"malloc.h" / ...
  • 构造哈希表(耿8.12)

    千次阅读 2018-05-24 16:38:05
    试在0-10的散列地址空间中,编写程序,对关键字序列 (22,41,53 46,30,13,01,67)构造哈希表,并等概率情况下查找成功的平均查找长度。Input无Output输出等概率情况下查找成功的平均查找长度。Sample Input 无...

空空如也

空空如也

1 2 3 4 5
收藏数 81
精华内容 32
关键字:

哈希表求平均查找长度