hashtable桶数通常会取一个素数分析

为什么一般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。但是如果选桶的大小为素数是不会有这个问题。

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

赞 (0)

相关推荐

  • Java中HashMap和Hashtable及HashSet的区别

    Hashtable类   Hashtable继承Map接口,实现一个key-value映射的哈希表.任何非空(non-null)的对象都可作为key或者value. 添加数据使用put(key,value),取出数据使用get(key),这两个基本操作的时间开销为常数. Hashtable通过initial   capacity和load   factor两个参数调整性能.通常缺省的load   factor   0.75较好地实现了时间和空间的均衡.增大load   factor可以节省空间但

  • 全面解析java中的hashtable

    Hashtables提供了一个很有用的方法可以使应用程序的性能达到最佳. Hashtables(哈希表)在计算机领域中已不 是一个新概念了.它们是用来加快计算机的处理速度的,用当今的标准来处理,速度非常慢,而它们可以让你在查询许多数据条目时,很快地找到一个特殊的条目. 尽管现代的机器速度已快了几千倍,但是为了得到应用程序的最佳性能,hashtables仍然是个很有用的方法. 设想一下,你有一个包含约一千条记录的数据文件??比如一个小企业的客户记录还有一个程序,它把记录读到内存中进行处理.每个记录

  • java中Hashtable和HashMap的区别分析

    1.Hashtable是Dictionary的子类, 复制代码 代码如下: public class Hashtable<K,V>     extends Dictionary<K,V>     implements Map<K,V>, Cloneable, java.io.Serializable HashMap: 复制代码 代码如下: public class HashMap<K,V>    extends AbstractMap<K,V> 

  • java hashtable实现代码

    复制代码 代码如下: public class HashTable{   private String[] name;    //关键字   private int sum;    //容量   public static void main(String[] args){    //测试        HashTable ht = new HashTable();        ht.add("chenhaitao");        ht.add("zhongcheng&

  • 遍历Hashtable 的几种方法

    方法一: IDictionaryEnumerator enumerator = thProduct.GetEnumerator(); while (enumerator.MoveNext()) { arrKey.Add("@"+enumerator.Key.ToString());         // Hashtable关健字 arrValue.Add(enumerator.Value.ToString());            // Hashtable值 } 方法二: usin

  • 深入PHP中的HashTable结构详解

    深入PHP中的HashTable结构详解

    HashTable是Zend引擎中最重要.使用最广泛的数据结构,它被用来存储几乎所有的东西.1.2.1 数据结构HashTable数据结构定义如下: 复制代码 代码如下: typedef struct bucket { ulong h;    // 存放hash uint nKeyLength; void *pData;   // 指向value,是用户数据的副本 void *pDataPtr; struct bucket *pListNext; // pListNext和pListLast组成

  • 浅析Java中Map与HashMap,Hashtable,HashSet的区别

    HashTable和HashMap区别 第一,继承的父类不同.Hashtable继承自Dictionary类,而HashMap继承自AbstractMap类.但二者都实现了Map接口. 复制代码 代码如下: public class Hashtable<K,V>extends Dictionary<K,V>implements Map<K,V>, Cloneable, Serializable public class HashMap<K,V>extends

  • java中vector与hashtable操作实例分享

    众所周知,java中vector与hashtable是线程安全的,主要是java对两者的操作都加上了synchronized,也就是上锁了.因此 在vector与hashtable的操作是不会出现问题.但是有一种情况:就是将一个hashtable copy到另一个hashtable时,假如使用putAll方法的花,会抛出一个 java.util.ConcurrentModificationException异常.先上代码: TestSync.java 复制代码 代码如下: public clas

  • hashtable桶数通常会取一个素数分析

    为什么一般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的特性,

  • Java爬虫实战抓取一个网站上的全部链接

    Java爬虫实战抓取一个网站上的全部链接

    前言:写这篇文章之前,主要是我看了几篇类似的爬虫写法,有的是用的队列来写,感觉不是很直观,还有的只有一个请求然后进行页面解析,根本就没有自动爬起来这也叫爬虫?因此我结合自己的思路写了一下简单的爬虫. 一 算法简介 程序在思路上采用了广度优先算法,对未遍历过的链接逐次发起GET请求,然后对返回来的页面用正则表达式进行解析,取出其中未被发现的新链接,加入集合中,待下一次循环时遍历. 具体实现上使用了Map<String, Boolean>,键值对分别是链接和是否被遍历标志.程序中使用了两个Map集

  • 用vbs 实现从剪贴板中抓取一个 URL 然后在浏览器中打开该 Web 站点

    问: 嗨,Scripting Guy!我如何从剪贴板中抓取一个 URL 然后在浏览器中打开该 Web 站点? -- CL 答: 您好,CL.这是很有趣的问题,或者我们应当说,这是两个很有趣的问题.因为您实际上问了两个问题.第一个问题很简单:我可以使用脚本打开特定的 Web 站点吗?您大概已经知道答案了,我可以大声地回答您,可以!下面是一个示例脚本,它将"脚本中心"的 URL 存储在一个名为 strURL 的变量中.然后,此脚本会创建 WSH Shell 对象的一个实例,并使用 Run 

  • Python爬虫爬取一个网页上的图片地址实例代码

    Python爬虫爬取一个网页上的图片地址实例代码

    本文实例主要是实现爬取一个网页上的图片地址,具体如下. 读取一个网页的源代码: import urllib.request def getHtml(url): html=urllib.request.urlopen(url).read() return html print(getHtml(http://image.baidu.com/search/flip?tn=baiduimage&ie=utf-8&word=%E5%A3%81%E7%BA%B8&ct=201326592&am

  • Python实现随机取一个矩阵数组的某几行

    废话不多说了,直接上代码吧! import numpy as np array = np.array([0, 0]) for i in range(10): array = np.vstack((array, [i+1, i+1])) print(array) # [[ 0 0] # [ 1 1] # [ 2 2] # [ 3 3] # [ 4 4] # [ 5 5] # [ 6 6] # [ 7 7] # [ 8 8] # [ 9 9] # [10 10]] rand_arr = np.ara

  • golang抓取网页并分析页面包含的链接方法

    1. 下载非标准的包,"golang.org/x/net/html" 2. 先安装git,使用git命令下载 git clone https://github.com/golang/net 3. 将net包,放到GOROOT路径下 比如: 我的是:GOROOT = E:\go\ 所以最终目录是:E:\go\src\golang.org\x\net 注意:如果没有golang.org和x文件夹,就创建 4. 创建fetch目录,在其下创建main.go文件,main.go文件代码内容如下

  • 浅谈vue的第一个commit分析

    为什么写这篇vue的分析文章? 对于天资愚钝的前端(我)来说,阅读源码是件不容易的事情,毕竟有时候看源码分析的文章都看不懂.每次看到大佬们用了1-2年的vue就能掌握原理,甚至精通源码,再看看自己用了好几年都还在基本的使用阶段,心中总是羞愧不已.如果一直满足于基本的业务开发,怕是得在初级水平一直待下去了吧.所以希望在学习源码的同时记录知识点,可以让自己的理解和记忆更加深刻,也方便将来查阅. 目录结构 本文以vue的第一次 commit a879ec06 作为分析版本 ├── build │ └─

  • VBS 两数相加取值问题分析

    一个昵称为预言家晚报的朋友很喜欢玩SOSO问问,等级LV10,已经算比较高了.晚上挂QQ的时候,看到他的问问有更新,就点进去看了一下,问题是: 我写了如下一段VBS 复制代码 代码如下: dim a,b,c a=inputbox("a","please input") b=inputbox("b","please input") c=a+b msgbox(c) 可是最后结果是11,我知道肯定是倒数第二行的"+&quo

  • JavaScript 取一个月的最后一天

    [Ctrl+A 全选 注:如需引入外部Js需刷新才能执行]

  • perl哈希的一个实例分析

    复制代码 代码如下: #!/bin/perluse strict;  use warnings; my %movies;  my $film;  my %reverse_result;  my $director;  my @data; %movies =  (    'The Shining'       => 'Kubrick',    'Ten Commandments'  => 'DeMille',    'Goonies'           => 'Spielberg', 

随机推荐