精华内容
下载资源
问答
  • python3的pymysql模块会inception发送SHOW WARNINGS语句,导致inception返回个"Must start as begin statement"错误被archer捕捉到报在日志里 使用src/docker/pymysql目录下的文件替换/path/to/python3/lib/...
  • 什么一般hashtable的桶会取个素数

    万次阅读 多人点赞 2013-11-07 20:28:16
    什么一般hashtable的桶数会取个素数  设有个哈希函数 H( c ) = c % N; ...当N取个合数时,最简单的例子取2^n,...这时候c的二进制4从右向左数)就”失效”了,也就是说,无论c的4什么值,
    为什么一般hashtable的桶数会取一个素数 


    设有一个哈希函数
    H( c ) = c % N;
    当N取一个合数时,最简单的例子是取2^n,比如说取2^3=8,这时候
    H( 11100(二进制) ) = H( 28 ) = 4
    H( 10100(二进制) ) = H( 20 )= 4


    这时候c的二进制第4位(从右向左数)就”失效”了,也就是说,无论第c的4位取什么值,都会导致H( c )的值一样.这时候c的第四位就根本不参与H( c )的运算,这样H( c )就无法完整地反映c的特性,增大了导致冲突的几率.


    取其他合数时,都会不同程度的导致c的某些位”失效”,从而在一些常见应用中导致冲突.
    但是取质数,基本可以保证c的每一位都参与H( c )的运算,从而在常见应用中减小冲突几率..


    (个人意见:有时候不取质数效率也不会太差..但是无疑取质数之比较保险的..)


    以上就是我的理解


    补充一点,这里是说在常见应用中,往往有些数据会比较相近,这时候用质数比较好,比如要存放的数据是压缩的状态,比如存储一个描述当前搜索状态的表,的这时候哈希不用质数冲突机率就比较大。


    如果是随机分布的整数,那么哈希模数只要取到足够大,在概率上来说都是一样的,但是这显然脱离实际应用。


    你说的情况 是比较特殊的,因为选取了比较小的一个质数,当选去大质数N时,就可以仅在N进制的某一位失效,结合计算机系统的特性,N进制位表示法往往是不关键的,而常用的2^N进制比较关键,所以可以避免冲突。


    其实,偶用一些大数做过测试,用来存放一个压缩为二进制的邻接矩阵,当模数足够大时,即便是合数也能有很接近质数的效果,但在某些(几十个)合数上会造成效率严重下降,所以质数是比较保险的。


    你不妨自己做实验,不要去选随机整数,而要考虑一些常见应用,用质数和合数进行测试,主要考察平均装载因子,你得到的结论可能和我一样:合数绝大多数时候效果也不错,但在一部分合数上效果差得出奇,而质数几乎全部都有很好的效果。
     
    我个人认为更普遍意义的理解,如果不取素数的话是会有一定危险的,危险出现在当假设所选非素数m=x*y,如果需要hash的key正好跟这个约数x存在关系就惨了,最坏情况假设都为x的倍数,那么可以想象hash的结果为:1~y,而不是1~m。但是如果选桶的大小为素数是不会有这个问题。
    展开全文
  • 什么一般hashtable的桶数会取个素数 假如有个哈希函数:H( c ) = c % N; 当N取个合数时,最简单的...这时候c的二进制4从右向左数)就”失效”了,也就是说,无论c的4什么值,都会导致H( c )...

    为什么一般hashtable的桶数会取一个素数

    假如有一个哈希函数:H( c ) = c % N;

    当N取一个合数时,最简单的例子是取2^n,比如说取2^3=8,这时候

    H( 11100(二进制) ) = H( 36 ) = 4
    H( 10100(二进制) ) = H( 28)= 4

    这时候c的二进制第4位(从右向左数)就”失效”了,也就是说,无论第c的4位取什么值,都会导致H( c )的值一样.这时候c的第四位就根本不参与H( c )的运算,这样H( c )就无法完整地反映c的特性,增大了导致冲突的几率

    取其他合数时,都会不同程度的导致c的某些位”失效”,从而在一些常见应用中导致冲突.

    在实际中往往关键字有某种规律,例如大量的等差数列,那么公差和模数不互质的时候发生碰撞的概率会变大,而用质数就可以很大程度上回避这个问题。基本可以保证c的每一位都参与H( c )的运算,从而在常见应用中减小冲突几率.

     

    2、

    Hash碰撞冲突

    我们知道,对象Hash的前提是实现equals()和hashCode()两个方法,那么HashCode()的作用就是保证对象返回唯一hash值,但当两个对象计算值一样时,这就发生了碰撞冲突。如下将介绍如何处理冲突,当然其前提是一致性hash。

    1.开放地址法

    开放地执法有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)
    其中,m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,…m-1,称线性探测再散列。
    如果di取1,则每次冲突之后,向后移动1个位置.如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,…k*k,-k*k(k<=m/2),称二次探测再散列。
    如果di取值可能为伪随机数列。称伪随机探测再散列。

    2.再哈希法

    当发生冲突时,使用第二个、第三个、哈希函数计算地址,直到无冲突时。缺点:计算时间增加。
    比如上面第一次按照姓首字母进行哈希,如果产生冲突可以按照姓字母首字母第二位进行哈希,再冲突,第三位,直到不冲突为止

    3.链地址法(拉链法)

    将所有关键字为同义词的记录存储在同一线性链表中。

    优点:

    ①拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;
    ②由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;
    ③开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;
    ④在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表,删除结点不能简单地将被删结 点的空间置为空,否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中,空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作,只能在被删结点上做删除标记,而不能真正删除结点。

    缺点:

    指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度。

    4.建立一个公共溢出区

    假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表,另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。

    展开全文
  • 顺序表中第一个元素的储存地址100,每个元素的长度为2,则第5个元素的地址() A.100 B.108 C.100 D.120 B 100+(5-1)*2==108 线性表若采用链式存储结构,要求内存中可用存储单元的地址() A.部分...
  • 强制类型转换规则:1、字符转数值,【parseInt()】从左向右一次转换,能转则转,不能转停止,【Math.round()】严格转换,不允许出现...如果第一位就不能转,直接NaN;不识别小数点。parseFloat();等同于parseIn...

    强制类型转换规则是:1、字符转数值,【parseInt()】从左向右一次转换,能转则转,不能转停止,【Math.round()】严格转换,不允许出现任何非数字的字符;2、数值转字符,【toString()】直接转换。

    595cbeb8c113169686cb00949552261a.png

    强制类型转换规则是:

    字符转数值

    parseInt();从左向右一次转换,能转则转,不能转停止;如果第一位就不能转,直接NaN;不识别小数点。

    parseFloat();等同于parseInt,同时可以识别小数点

    Math.round();严格转换,不允许出现任何非数字的字符,否则NaN;取最接近的整数

    Number();严格转换,不允许出现任何非数字的字符,否则NaN;直接转换

    var str = "123";

    var str = "123abc";

    var str = "123abc456";

    var str = "a123";

    var str = "adasd";

    var str = "123.45";

    var n = parseInt(str);

    console.log(str);

    console.log(typeof str);

    console.log(n);

    console.log(typeof n);

    var str = "a567.892";

    var n = parseFloat(str);

    console.log(str);

    console.log(typeof str);

    console.log(n);

    console.log(typeof n);

    var str = "-456.789";

    var n = Math.round(str);

    console.log(str);

    console.log(typeof str);

    console.log(n);

    console.log(typeof n);

    var str = "-456.789a";

    var n = Number(str);

    console.log(str);

    console.log(typeof str);

    console.log(n);

    console.log(typeof n);

    数值转字符

    toString();直接转换,相当于给要转换的数值,加引号

    保留n为小数

    toFixed();加引号的同时,四舍五入保留n位小数,不够,补零

    var n = 10.3543;

    var s = n.toString();

    console.log(n);

    console.log(typeof n);

    console.log(s);

    console.log(typeof s);

    var n = 10;

    var s = n.toFixed(2);

    console.log(n);

    console.log(typeof n);

    console.log(s);

    console.log(typeof s);

    console.log(123.567000000)

    数值转字符

    var n = 123;

    var s = n + "";

    console.log(s)

    字符转数值

    var s = "123";

    var n = s - 0;

    console.log(n)

    其他转数值

    true为1,false为0

    console.log(1 + true); //2

    console.log(1 + false); //1

    console.log(1 + undefined); //NaN

    console.log(1 + NaN); //NaN

    console.log(1 + null); //1相关学习推荐:编程视频

    展开全文
  • 【单选题】关于 Python 循环结构,以下选项中描述错误的 ( )【单选题】字符串是一个字符序列,例如,字符串s,右侧向左第3个字符用什么索引?【其它】编写函数,判断是否为“水仙花”,所谓“水仙花...

    【其它】编写函数,判断用户传入的字符串参数长度是否大于 5 。

    【单选题】关于 Python 循环结构,以下选项中描述错误的是 ( )

    【单选题】字符串是一个字符序列,例如,字符串s,从右侧向左第3个字符用什么索引?

    【其它】编写函数,判断一个数是否为“水仙花数”,所谓“水仙花数”是指一个三位数,其各位数字立方和等于改数本身。例如 153 是一个“水仙花数”,因为 153=1 3 +5 3 +3 3 。 然后利用该函数输出所有的“水仙花数”。

    【简答题】请来看看村庄

    【单选题】下列程序共输出_______个值: 1. age = 23 2. start = 2 3. if age % 2 != 0: 4. start = 1 5. for x in range(start, age + 2, 2): 6. print(x)

    【简答题】我和我的

    【单选题】给出如下代码 , 可以输出“ python ”的是 ( ) s = 'Python is beautiful!'

    【简答题】游击队歌

    【简答题】Java2006试卷.doc 1、请提供每题的详细分析; 2、有疑问的题目,请及时提出来。

    【单选题】关于Python语言的浮点数类型,以下选项中描述错误的是 ( )

    【简答题】2014年22JAVA_B场参考答案.doc

    【单选题】与x > y and y > z 语句等价的是()

    【单选题】在读写文件之前,必须通过以下哪个方法创建文件对象:

    【单选题】以下选项中不是 Python 对文件的写操作方法的是 ( )

    【单选题】执行以下两条语句后,lst的结果是 1. lst = [3, 2, 1] 2. lst.append(lst)

    【其它】实现multi()函数,参数个数不限,返回所有参数的乘积。

    【单选题】于 Python 的列表,描述错误的选项是 ( )

    【其它】实现isprime()函数,参数为整数,如果整数是素数,返回True,否则返回False。

    【简答题】源语复述 7.2 教育与城镇化.avi 7.4 Teaching and the Internet.avi

    【其它】假设一年定期利率为 3.25% ,计算一下需要过多少年,一万元的一年定期存款连本带息能翻番?

    【单选题】关于 Python 注释,以下选项中描述错误的是 ( )

    【其它】重复元素判定。编写一个函数,接受列表作为参数,如果一个元素在列表中出现了不止一次,则返回True(但不要改变原来列表的值),否则返回False。同时编写调用这个函数和测试结果的程序。

    【其它】有家电影院根据观众的年龄收取不同的票价: 不到 3 岁的观众免费; 3~12 岁的观众为 10 美元; 超过 12 岁的观众为 15 美元。请编写一个循环, 在其中一直询问用户的年龄, 并指出其票价;当用户输入“ quit ”时,程序结束运行。

    【单选题】使用()函数接收用输入的数据

    【单选题】关于a or b的描述错误的是( )。

    【简答题】数蛤蟆

    【单选题】下面程序的运行结果为( )。 def swap(list): temp=list[0] list[0]=list[1] list[1]=temp list=[1,2] swap(list) print(list)

    【简答题】山楂树

    【简答题】小白菜

    【单选题】给出如下代码 , 可以输出“ python ”的是 ( ) s = 'Python is beautiful!'

    【单选题】下面代码的输出结果是 ( ) d ={" 大海 ":" 蓝色 ", " 天空 ":" 灰色 ", " 大地 ":" 黑色 "} print(d[" 大地 "], d.get(" 大地 ", " 黄色 "))

    【单选题】对于函数ask,以下调用错误的是哪一项? 1. def ask(prompt = "Do you like Python? ", hint = "yes or no"): 2. while True: 3. answer = raw_input(prompt) 4. if answer.lower() in ('y', 'yes'): 5. print "Thank you" 6. return True 7. if answer.lower() in ('n', 'no'): 8. print "Why not " 9. return False 10. else: 11. print hint

    【其它】一家商场在降价促销。如果购买金额50-100元(包含50元和100元)之间,会给10%的折扣,如果购买金额大于100元会给20%折扣。编写一程序,询问购买价格,再显示出折扣(%10或20%)和最终价格。

    【简答题】2018年上海市计算机等级考试(Java).pdf 1、客观题请详细写出分析过程; 2、编程题请提供完整代码和输出结果。

    【简答题】2015年22B操作题参考答案.doc 2016年22B参考答案.doc 1、运行并改进参考程序,截结果图; 2、对运行通过后的程序加上行注释。

    【单选题】下面( )不是有效的变量名。

    【单选题】关于 Python 组合数据类型,以下选项中描述错误的是 ( )

    【其它】随机生成 20 个学生的成绩(百分制),判断这 20 个学生成绩的等级。标准如下 【 90,100 】 A 【 80-89 】 B 【 70-69 】 C 其它 D

    【其它】从键盘输入三个数,输出其中的最大值和最小值。

    【单选题】若 a = 'abcd' ,若想将 a 变为 'ebcd' ,则下列语句正确的是

    【其它】编写程序,生成一个包含 50 个随机整数(0-99)的列表,然后删除其中所有奇数。(提示:从后向前删)

    【单选题】以下哪条语句定义了一个Python字典

    【简答题】哦苏珊娜

    【单选题】关于 Python 程序格式框架的描述,以下选项中错误的是 ( )

    【其它】判断 101 到 200 之间有多少个素数并输出其中的素数。

    【其它】用 Python 创建一个新文件,产生十个 0 到 9 的整数 , 每个数字占一行。

    【简答题】Java2004答案.doc java2005答卷.doc Java2004试卷.doc java2005试卷.doc

    【单选题】关于 Python 循环结构,以下选项中描述错误的是 ( )

    【单选题】关于Python赋值语句,以下选项中不合法的是 ( )

    展开全文
  • 题目地址: ...给定mmm和nnn,题目保证0≤m≤n≤...考虑mmm和nnn的二进制表示中,从左向右第一个不同的那一位,例如在起第kkk位(那么mmm的这一位一定000,nnn的这一位一定111,因为m≤nm\le nm≤n),构造一个x
  • 2.1.2 从右的可计算性测试 13 2.1.3 操作的新式用法 14 2.2 结合逻辑操作的加减运算 16 2.3 逻辑与算术表达式中的不等式 17 2.4 绝对值函数 18 2.5 两平均值 19 2.6 符号扩展 20 2.7 用无符号右移...

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 145
精华内容 58
关键字:

从右向左数第一位是什么位