关于散列表中除留余数法构造的散列函数,除数选择素数的疑问

正在学习数据结构里的散列相关知识,书里一般都会提到,如果用除留余数的散列函数,最好选择素数作为除数。但没有对此详细的证明。

对此不太理解,个人理解是,无论素数还是合数,在取模的一个周期内都是均匀分布的单射的,并不会因为除数有质因数改变分布和冲突情况。

看了一些其他文章,也没有具有普遍性的证明。有的文章中会用一个特例来说明素数作除数更好,但特例不能证明一般性(例如有的文章中会拿一个具有公因数3的数列为key,然后mod6,结果表明这些key都被散列在0、3、6的地址上,以此来说明除数不应该用合数。但这个观点显然站不住脚,因为我也可以举一个具有公因数7的序列为key来mod7,也会造成严重冲突,而7是素数)

对于平常的应用中,如果散列的key通常不具有普遍的规律(例如都是某个数的倍数)而更倾向于随机性(比如储存一些号码,没有特殊规律),在这种随机输入的情况下是不是除数是否是素数不影响散列产生冲突的情况?如果依然有影响,能否有详细的具有普适性的证明

本人才疏学浅,想不通这个问题,特来请教

2个回答

我们知道素数和合数的区别在于: 素数只有 1它本身 两个约数, 而合数则另有其他约数.

weixin_44377608
10sir 不对吧。举个例子,比如10和6就有公约数2,但他的取值10%6=4
4 个月之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
需求:用随机数生成一篇除法练习题。要求能设定除数的位数,设定被除数的位数,商不能有余数。

大家好,我想随机生成一些除法练习题,可以设置好除数的位数(如6位)、被除数的位数(如3位),商要求是不能有余数的,必须整除。 1. 质数只能被1和自身整除,我已经考虑到了。 2. 反着来,设置商和被除数的位数,也考虑过,这不符合要求。 希望大家能给一些可行的建议,或则现有的方案。谢谢,谢谢!

调用函数IsPrimeNumber统计10000以内素数个数。

函数IsPrimeNumber的功能是判断m是否为素数(质数),若m不是素数,返回FALSE;若m是素数,则返回TRUE #include<stdio.h> #include<math.h> #define FALSE 0 #define TRUE 1 int IsPrimeNumber(int m); int main(void) { int i, count=0; for (i=2; i<=10000; i++) { /*********Found************/ if (____________________) { count++; } } printf("count=%d\n", count); return 0; } int IsPrimeNumber(int m) { int i, k; /*********Found************/ int ret; k = (int)sqrt(m); for (i=2; i <=k; i++) { if (m % i == 0) { ret = FALSE; break; } } /*********Found************/ return ; } 在found下改错哟

JAVA中关于素数问题的布尔函数

public static boolean isPrime(int num) { int i; int temp=0; for(i=2;i<num;i++) { while((num%i)==0) { temp++; } } if (num != 1 && temp<2) // 如果只有一次整除,那么该数为素数 { System.out.print(true); } if(temp>=2) { System.out.print(false); } return false; } 为什么不是素数不会输出false;但是是素数会输出true;

编写函数,判断该数组中哪些是素数,并统计素数的个数,在主函数中输出素数的个数和这些素数,函数原型不能变,怎么我一直输出不来,求大神指教!?

#include<stdio.h> int len ; int IsPrime(int *data, int *primes,int len) { int y=1; for (int j = 0; j < 5; j++)/*判断素数*/ { for (int i = 2; i < data[j]; i++) { y *= data[j] % i; } if (y != 0) { primes = &data[j]; len++; primes++; } } /*for (int i = 0; i < len; i++) printf("%3d\n", *--primes);*/ return len; } void main() { int data[5], *primes, primes_[5] = {1,2,3,4,5}, len = 0; primes = primes_; for (int i = 0; i < 5; i++) { scanf("%3d", &data[i]); } printf("共有%d个素数", len = IsPrime(data, primes, 0)); printf("这些素数分别为:\n"); for(int i=0;i<len;i++) printf("%3d\n", primes_[len]); }

c++中如何输入4个数然后另一个数值为起始值一个数值为终止值,两个除数整除

# 4.编写程序计算能同时被两个或者三个整数整除的数值。选择两个整数整除,输入四个数值,一个起始数值,一个终止数值,两个除数整数,输出两个数值之间的所有能同时被两个整数整除的数值, 每行输出4个数;或者选择三个整数整除,输入五个数值,一个起始数值,一个终止数值,三个除数整数,输出两个数值之间的所有能同时被三个整数整除的数值, 每行输出4个数;?。 比如,输入 起始数值:1 终止数值:20 选择两个整数整除 输入两个除数整数:2,3 选择两个整数整除输出:6 12

用c语言编程,用筛选法求2到100之间的素数

用筛选法求2到100之间的素数。方法如下:首先2是素数,凡2的倍数都不是素数,于是把这些数从数表中筛去,2以后没有被筛去的第一个数是3,然后把3的倍数都从数表中筛去,3以后没被筛去的第一个数是5,然后把5的倍数都从数表中筛去。如此下去,直到遇到某数K(≤N),其后没有数可筛选为止,这时保留下的未被筛去的数就是2到N的素数。

C++用筛法求100内素数

用筛法求100以内素数,什么叫筛法????????????????????????????????????????????????????

写一函数判断某数是否“水仙花数”,

写一函数判断某数是否“水仙花数”,所谓“水仙花数”是指一个三位数, 其各位数字 立方和等于该数本身。例如 153是一个水仙花数,因为 153=1533 3 3

判断一个数是不是素数

判断一个数n是不是素数,需要判断2—(n-1),为什么只需要判断2—sqrt(n)呢?

如何构造一个范围内所有的回文数?

列如构造出5-100000所有的回文数。不是要顺序查找的方法!!是自己一个一个的构造来提高效率!

素数判定法输入规模和基本操作个数

![图片说明](https://img-ask.csdn.net/upload/201903/04/1551712181_763933.jpg) 这个基本操作的个数要怎么表达成函数啊……

用python3查找1-20之间的素数,append函数和remove函数的效果为什么不同?

查找1-20之间的素数,用append函数和remove函数的效果为什么不同? ``` def test1(n):# 判断n是不是素数 if n==1: return 1 for i in range(2,n): if n%i==0: return n ``` num=list(range(1,21)) num1=[] ``` def test2():# 将一段区间内的所有素数存入一个列表 for i in num: if None==test1(i): num1.append(i) print(num1) ``` test2() 返回[2, 3, 5, 7, 9] 为什么下面的程序保留的是奇数,包括9这样的合数? ``` def test3(): for i in num: if i==test1(i): num.remove(i) print(num) ``` test3() 返回[2, 3, 5, 7, 9, 11, 13, 15, 17, 19]

判断一个数是不是素数的方法

用比这个数字小的所有素数去整除它就可以知道这个数是不是素数.这是为什么

两个数,求两个数之间素数的个数,数据非常大。

题目描述 给你两个数,求两个数之间素数的个数。 输入: 输入有两个数,一个a,一个b,求a到b之间素数的个数 其中1<=a<=b<=1e12 其中b-a<=1e7 输出: 一个数,表示a-b之间素数的个数。 样例输入: 1 10 样例输出: 4

区间筛法求区间内素数的个数

for(ll i = 2;i*i <=b;i++) is_prime_small[i] = true; for(ll i = 0;i <=b-a;i++) is_prime[i] = true; for(ll i = 2;i*i <=b;i++) { if(is_prime_small[i]) { for(ll j = 2*i;j*j <=b;j += i) is_prime_small[j] = false; for(ll j = max(2LL,(a+i-1)/i)*i;j <=b;j += i) //就是这一句看不懂,还有就是2LL是啥意思~~ { if(is_prime[j-a]) { ans++; is_prime[j-a] = false; } } } }

答复:python中解决孪生素数?

题目:3、 利用上题中判断素数的函数,编写程序找出1~100之间的所有孪生素数(若两个素数之差为2,则这两个素数就是一对孪生素数)。例如:3和5、5和7、11和13等都是孪生素数。 以下是我自己写的代码: def isprime(n): import math a=int(math.sqrt(n))+1 for i in range(2,a): if n%i==0: flag=False return flag def main(): flag=True for n in range(1,101): primelist=[] if flag: primelist.append(n) for b in range(0,len(primelist)): if primelist[b+1]-primelist[b]==2: print(primelist[b+1],primelist[b]) main() 运行后,提示我:list index out of range 我不会改,求教

筛法求素数表,输出全是0?

``` import java.util.Scanner; public class B1013_2 { /*求素数表第m到第n个中间的所有素数*/ public static void main(String[] args) { Scanner in = new Scanner(System.in); int M = in.nextInt(); int N = in.nextInt(); boolean []num = new boolean[10001]; for (int x = 1; x < 10001; x++) /* num[1] ~ num[10001] 均不是质数*/ { num[x] = true; } int []prime = new int[N+1];/*若是N,则不到27, 27越界了,所以N+1 */ int z = 0; for (int i = 2; i < 10001; i++) /*把小于10000的素数都求了一遍*/ { if (num[i] == true) /*是质数*/ { prime[z++] = i; /*若是prime[i] = i z是第几个质数*/ if (z > N) { break; } for (int j = i + i; j < 10001; j += i) /*筛掉它的所有倍数*/ { num[j] = false; /*不是质数*/ } if (z >= M && z <= N) { if ((z-M+1) % 10 > 0 && z != N) { System.out.print(prime[z] + " "); } else if ( z % 10 == N) { System.out.print(prime[z]); } else { System.out.print(prime[z]); System.out.print("\n"); } } } } in.close(); } } ``` 令Pi表示第i个素数。现任给两个正整数M <= N <= 104,请输出PM到PN的所有素数。 输入格式: 输入在一行中给出M和N,其间以空格分隔。 输出格式: 输出从PM到PN的所有素数,每10个数字占1行,其间以空格分隔,但行末不得有多余空格。 输入样例: 5 27 输出样例: 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103

请编写一个函数void fun(int m,int k,int xx[]),该函数的功能是:将大于整数m且紧靠m的k各素数存入xx所指的数组中

为什么我的程序没有运行结果呢? //请编写一个函数void fun(int m,int k,int xx[]),该函数的功能是:将大于整数m且紧靠m的k各素数存入xx所指的数组中。// #include <stdio.h> void fun(int m,int k,int xx[]); void main() { int m,k,xx[10]; scanf("%d%d",&m,&k); fun(m,k,xx); } void fun(int m,int k,int xx[]) { int i,j=0; while(j<k) { for(i=2;i<m;i++) { if(m%i==0) { m++; break; } else if(m==(i+1)) { xx[j++]=m; m++; } } } for(i=0;i<k;i++) printf("%d",xx[i]); }

x是素数,且其各位数字以及各位数字之和都是素数

用C语言编写程序找出2到5000中满足条件的素数x,x是素数且其各位数字以及各位数字之和都为素数

在中国程序员是青春饭吗?

今年,我也32了 ,为了不给大家误导,咨询了猎头、圈内好友,以及年过35岁的几位老程序员……舍了老脸去揭人家伤疤……希望能给大家以帮助,记得帮我点赞哦。 目录: 你以为的人生 一次又一次的伤害 猎头界的真相 如何应对互联网行业的「中年危机」 一、你以为的人生 刚入行时,拿着傲人的工资,想着好好干,以为我们的人生是这样的: 等真到了那一天,你会发现,你的人生很可能是这样的: ...

程序员请照顾好自己,周末病魔差点一套带走我。

程序员在一个周末的时间,得了重病,差点当场去世,还好及时挽救回来了。

技术大佬:我去,你写的 switch 语句也太老土了吧

昨天早上通过远程的方式 review 了两名新来同事的代码,大部分代码都写得很漂亮,严谨的同时注释也很到位,这令我非常满意。但当我看到他们当中有一个人写的 switch 语句时,还是忍不住破口大骂:“我擦,小王,你丫写的 switch 语句也太老土了吧!” 来看看小王写的代码吧,看完不要骂我装逼啊。 private static String createPlayer(PlayerTypes p...

和黑客斗争的 6 天!

互联网公司工作,很难避免不和黑客们打交道,我呆过的两家互联网公司,几乎每月每天每分钟都有黑客在公司网站上扫描。有的是寻找 Sql 注入的缺口,有的是寻找线上服务器可能存在的漏洞,大部分都...

上班一个月,后悔当初着急入职的选择了

最近有个老铁,告诉我说,上班一个月,后悔当初着急入职现在公司了。他之前在美图做手机研发,今年美图那边今年也有一波组织优化调整,他是其中一个,在协商离职后,当时捉急找工作上班,因为有房贷供着,不能没有收入来源。所以匆忙选了一家公司,实际上是一个大型外包公司,主要派遣给其他手机厂商做外包项目。**当时承诺待遇还不错,所以就立马入职去上班了。但是后面入职后,发现薪酬待遇这块并不是HR所说那样,那个HR自...

女程序员,为什么比男程序员少???

昨天看到一档综艺节目,讨论了两个话题:(1)中国学生的数学成绩,平均下来看,会比国外好?为什么?(2)男生的数学成绩,平均下来看,会比女生好?为什么?同时,我又联想到了一个技术圈经常讨...

总结了 150 余个神奇网站,你不来瞅瞅吗?

原博客再更新,可能就没了,之后将持续更新本篇博客。

副业收入是我做程序媛的3倍,工作外的B面人生是怎样的?

提到“程序员”,多数人脑海里首先想到的大约是:为人木讷、薪水超高、工作枯燥…… 然而,当离开工作岗位,撕去层层标签,脱下“程序员”这身外套,有的人生动又有趣,马上展现出了完全不同的A/B面人生! 不论是简单的爱好,还是正经的副业,他们都干得同样出色。偶尔,还能和程序员的特质结合,产生奇妙的“化学反应”。 @Charlotte:平日素颜示人,周末美妆博主 大家都以为程序媛也个个不修边幅,但我们也许...

如果你是老板,你会不会踢了这样的员工?

有个好朋友ZS,是技术总监,昨天问我:“有一个老下属,跟了我很多年,做事勤勤恳恳,主动性也很好。但随着公司的发展,他的进步速度,跟不上团队的步伐了,有点...

我入职阿里后,才知道原来简历这么写

私下里,有不少读者问我:“二哥,如何才能写出一份专业的技术简历呢?我总感觉自己写的简历太烂了,所以投了无数份,都石沉大海了。”说实话,我自己好多年没有写过简历了,但我认识的一个同行,他在阿里,给我说了一些他当年写简历的方法论,我感觉太牛逼了,实在是忍不住,就分享了出来,希望能够帮助到你。 01、简历的本质 作为简历的撰写者,你必须要搞清楚一点,简历的本质是什么,它就是为了来销售你的价值主张的。往深...

外包程序员的幸福生活

今天给你们讲述一个外包程序员的幸福生活。男主是Z哥,不是在外包公司上班的那种,是一名自由职业者,接外包项目自己干。接下来讲的都是真人真事。 先给大家介绍一下男主,Z哥,老程序员,是我十多年前的老同事,技术大牛,当过CTO,也创过业。因为我俩都爱好喝酒、踢球,再加上住的距离不算远,所以一直也断断续续的联系着,我对Z哥的状况也有大概了解。 Z哥几年前创业失败,后来他开始干起了外包,利用自己的技术能...

优雅的替换if-else语句

场景 日常开发,if-else语句写的不少吧??当逻辑分支非常多的时候,if-else套了一层又一层,虽然业务功能倒是实现了,但是看起来是真的很不优雅,尤其是对于我这种有强迫症的程序"猿",看到这么多if-else,脑袋瓜子就嗡嗡的,总想着解锁新姿势:干掉过多的if-else!!!本文将介绍三板斧手段: 优先判断条件,条件不满足的,逻辑及时中断返回; 采用策略模式+工厂模式; 结合注解,锦...

深入剖析Springboot启动原理的底层源码,再也不怕面试官问了!

大家现在应该都对Springboot很熟悉,但是你对他的启动原理了解吗?

离职半年了,老东家又发 offer,回不回?

有小伙伴问松哥这个问题,他在上海某公司,在离职了几个月后,前公司的领导联系到他,希望他能够返聘回去,他很纠结要不要回去? 俗话说好马不吃回头草,但是这个小伙伴既然感到纠结了,我觉得至少说明了两个问题:1.曾经的公司还不错;2.现在的日子也不是很如意。否则应该就不会纠结了。 老实说,松哥之前也有过类似的经历,今天就来和小伙伴们聊聊回头草到底吃不吃。 首先一个基本观点,就是离职了也没必要和老东家弄的苦...

2020阿里全球数学大赛:3万名高手、4道题、2天2夜未交卷

阿里巴巴全球数学竞赛( Alibaba Global Mathematics Competition)由马云发起,由中国科学技术协会、阿里巴巴基金会、阿里巴巴达摩院共同举办。大赛不设报名门槛,全世界爱好数学的人都可参与,不论是否出身数学专业、是否投身数学研究。 2020年阿里巴巴达摩院邀请北京大学、剑桥大学、浙江大学等高校的顶尖数学教师组建了出题组。中科院院士、美国艺术与科学院院士、北京国际数学...

男生更看重女生的身材脸蛋,还是思想?

往往,我们看不进去大段大段的逻辑。深刻的哲理,往往短而精悍,一阵见血。问:产品经理挺漂亮的,有点心动,但不知道合不合得来。男生更看重女生的身材脸蛋,还是...

为什么程序员做外包会被瞧不起?

二哥,有个事想询问下您的意见,您觉得应届生值得去外包吗?公司虽然挺大的,中xx,但待遇感觉挺低,马上要报到,挺纠结的。

当HR压你价,说你只值7K,你该怎么回答?

当HR压你价,说你只值7K时,你可以流畅地回答,记住,是流畅,不能犹豫。 礼貌地说:“7K是吗?了解了。嗯~其实我对贵司的面试官印象很好。只不过,现在我的手头上已经有一份11K的offer。来面试,主要也是自己对贵司挺有兴趣的,所以过来看看……”(未完) 这段话主要是陪HR互诈的同时,从公司兴趣,公司职员印象上,都给予对方正面的肯定,既能提升HR的好感度,又能让谈判气氛融洽,为后面的发挥留足空间。...

面试:第十六章:Java中级开发(16k)

HashMap底层实现原理,红黑树,B+树,B树的结构原理 Spring的AOP和IOC是什么?它们常见的使用场景有哪些?Spring事务,事务的属性,传播行为,数据库隔离级别 Spring和SpringMVC,MyBatis以及SpringBoot的注解分别有哪些?SpringMVC的工作原理,SpringBoot框架的优点,MyBatis框架的优点 SpringCould组件有哪些,他们...

面试阿里p7,被按在地上摩擦,鬼知道我经历了什么?

面试阿里p7被问到的问题(当时我只知道第一个):@Conditional是做什么的?@Conditional多个条件是什么逻辑关系?条件判断在什么时候执...

你期望月薪4万,出门右拐,不送,这几个点,你也就是个初级的水平

先来看几个问题通过注解的方式注入依赖对象,介绍一下你知道的几种方式@Autowired和@Resource有何区别说一下@Autowired查找候选者的...

面试了一个 31 岁程序员,让我有所触动,30岁以上的程序员该何去何从?

最近面试了一个31岁8年经验的程序猿,让我有点感慨,大龄程序猿该何去何从。

大三实习生,字节跳动面经分享,已拿Offer

说实话,自己的算法,我一个不会,太难了吧

程序员垃圾简历长什么样?

已经连续五年参加大厂校招、社招的技术面试工作,简历看的不下于万份 这篇文章会用实例告诉你,什么是差的程序员简历! 疫情快要结束了,各个公司也都开始春招了,作为即将红遍大江南北的新晋UP主,那当然要为小伙伴们做点事(手动狗头)。 就在公众号里公开征简历,义务帮大家看,并一一点评。《启舰:春招在即,义务帮大家看看简历吧》 一石激起千层浪,三天收到两百多封简历。 花光了两个星期的所有空闲时...

《Oracle Java SE编程自学与面试指南》最佳学习路线图2020年最新版(进大厂必备)

正确选择比瞎努力更重要!

《Oracle Java SE编程自学与面试指南》最佳学习路线图(2020最新版)

正确选择比瞎努力更重要!

字节跳动面试官竟然问了我JDBC?

轻松等回家通知

面试官:你连SSO都不懂,就别来面试了

大厂竟然要考我SSO,卧槽。

终于,月薪过5万了!

来看几个问题想不想月薪超过5万?想不想进入公司架构组?想不想成为项目组的负责人?想不想成为spring的高手,超越99%的对手?那么本文内容是你必须要掌握的。本文主要详解bean的生命...

自从喜欢上了B站这12个UP主,我越来越觉得自己是个废柴了!

不怕告诉你,我自从喜欢上了这12个UP主,哔哩哔哩成为了我手机上最耗电的软件,几乎每天都会看,可是吧,看的越多,我就越觉得自己是个废柴,唉,老天不公啊,不信你看看…… 间接性踌躇满志,持续性混吃等死,都是因为你们……但是,自己的学习力在慢慢变强,这是不容忽视的,推荐给你们! 都说B站是个宝,可是有人不会挖啊,没事,今天咱挖好的送你一箩筐,首先啊,我在B站上最喜欢看这个家伙的视频了,为啥 ,咱撇...

立即提问
相关内容推荐