hashMap算法的兑现_读书人
hashMap算法的兑现
&来源：读书人网&【读书人网()：综合教育门户网站】
hashMap算法的实现昨天项目发布间隙，看了下hashmap的算法。关键在于：static int hash(int h) {// This func
hashMap算法的实现 && 昨天项目发布间隙，看了下hashmap的算法。关键在于：static int hash(int h) {&&&&&&& // This function ensures that hashCodes that differ only by&&&&&&& // constant multiples at each bit position have a bounded&&&&&&& // number of collisions (approximately 8 at default load factor).&&&&&&& h ^= (h &&& 20) ^ (h &&& 12);&&&&&&& return h ^ (h &&& 7) ^ (h &&& 4);}&&&&&&&& 和static int indexFor(int h, int length) {&&&&&&& return h & (length-1);}这2个方法。注意，这2个方法一定要配合使用，否则就比较难理解了。这里我解答几个问题，1.hash方法里传入的是对象的hashCode，而对象的hashCode是对象的内存地址，已经保证了唯一性，为什么还要再进行hash计算？回答：由于hash表的大小有限，不可能无限大，以hashmap实现中的indexFor方法来讲，是以与操作来计算的。那么假如hashCode转换成二进制以后，末尾相同的话，那么计算出来的index也就一样了，造成散列度不够。2.indexFor方法为什么针对length-1做与操作？回答：与操作将会把超出数组长度的部分截断，另外map初始化的时候会做如下操作：while (capacity & initialCapacity)&&&&&&&&&&& capacity &&= 1;这样，length肯定为2的N次方，好处是length-1转换成2进制每一位都是1，在做&操作的时候每一个坑都有机会得到值，否则假如有1位为0的情况，那一位就会浪费。&& &&& 3.我这里对hash函数有个疑问，这个算法的目的是把原始数据分成3断进行异或操作达到散列，但是我感觉最后结果的前4位是不会发生变。假如有数据前4位不一样，刚好hash表的长度是后面的28位，那么这个时候就会出现hash冲突了。不知道我这个理解对不对，请大家指正，谢谢。为什么要哈希函数使用一个素数模？-language-agnostic,数据结构data-structures,哈希hash-CodeGo.net
为什么要哈希函数使用一个素数模？
很久以前，我买了一个数据结构的书掉讨价还价表1.25美元。在这里面，一散列函数的解释说，它应最终由许多“数学的本质”MOD。
你怎么从1.25美元的书期待？
反正，我已经有几年去思考数学的本质，仍然无法弄明白。
是数分布更真实地甚至当有许多的桶？或者这是一个古老的故事，每个人都接受别人接受它？
本文地址 ：CodeGo.net/67529/
-------------------------------------------------------------------------------------------------------------------------
1. 通常一个简单的散列函数的工作原理是服用“组成部分”的输入（在一个字符串的大小写字符），并把它们通过不断的权力相乘，相加，然后在整数类型。因此，例如，一个典型的（尽管不是特别好）的字符串的哈希值可能是：
(first char) + k * (second char) + k^2 * (third char) + ...
然后，如果一串字符串中所有具有优先个字符是美联储在 CodeGo.net，那么结果都将是模K，至少要等到整型溢出。
[举例来说，Java的字符串的hashCode是极其相似这一点-它的字符逆序排列，其中k=31。所以，你得到显着的关系模31结尾的字符串方式之间，以及显着的关系模2 ^ 32是除了靠近端线之间。这不起来哈希表的行为。]
哈希表的工作原理是取哈希超过桶的数量。
重要的是在哈希表中不产生冲突的可能的情况下，由于collision减少哈希表的效率。
现在，假设把一大堆的值到一个哈希表有项目，像所有具有优先个字符之间的关系。这是一个相当图案，我会说，所以我们不希望它产生太多的冲突。
事实证明“的数学的本质”，如果在散列，和桶的数量，然后冲突最小化的常见情况。如果它们不那么有为其collision不会最小化输入之间的相当简单的关系。所有散列值等于出模factor，他们会全部落入1 / n个具有该值模factor桶。你得到n作为多次collision，其中n是系数。由于n至少为2，我会说这是一个相当的情况下，以产生至少两倍的collision是正常的。如果用户是要打破我们的分销成桶，我们希望它是一个奇怪的事故，而不是简单的
现在，哈希表有超过投入其中的项目没有控制权。它们不能防止其受到相关。所以要做的是，确保恒定，斗数是这样，你不依靠“last”成分单独确定桶相对于factor。据我所知他们没有要做到这一点，只是
但如果散列函数和哈希表是独立编写的，那么哈希表不知道怎么哈希函数的工作原理。它可能常数小的factor。如果你幸运的话它可能会不同，是非线性的。如果散列足够好，那么任何桶计数是蛮好的。而是偏执哈希表不能一个好的散列函数，所以一些桶。同样偏执哈希函数largeish恒定，减少了使用数字存储桶的这恰好具有因子与恒定的机会。
在实践中，我认为这是相当正常的2的幂作为桶的数量。这是方便，省去了到处搜索或预先选择一些合适的大小。所以，你靠的散列函数甚至没有multiplication器，这通常是一个安全的假设上。但你仍然可以得到基于类似上面的散列函数偶尔的坏散列行为，桶计数可以进一步帮助。
把关于“一切都要原理是，据我所知有足够的，但不是必要条件良好的分布在哈希表，它让所有人无需认为别人都跟着规则互操作。
[编辑：还有另外一个，更专业的原因，斗数，这是如果你处理冲突与线性探测。然后你计算从哈希码一大步，并且如果该步幅出来是水桶的factor计算，那么你只能做（bucket_count /步幅）探测你才回来，你开始。你最想避免的情况是步幅=0，当然，这必须是特例，，但要避免也特殊shellbucket_count /阔步等于一个小整数，你可以让bucket_count并不在乎什么步幅是，只要它不为0。]
究其原因，数字是如此，当你重复了一组空间，你要提供一个均匀分布在整个哈希空间。
例如，超过1的空间52中，使用31作为key：
s = 7 + key % 52 = 34
s = 34 + key % 52 = 13
s = 13 + key % 52 = 44
s = 44 + key % 52 = 23
s = 49 + key % 52 = 28
s = 28 + key % 52 = 7
正如你可以看到，这个数字最终将通过1到52（模环）的数目的整个空间循环确保所有的值都打在那个空间。
插入/从哈希表retreiving当你做的优先件事是计算的hashCode对于给定的键，然后通过trim的hashCode到Hashtable中做的hashCode％table_length大小找到正确的桶。下面是2'，你很可能已经阅读
如果是2的幂为table_length，发现（的hashCode（键）％2 ^ n）是简单和快捷（的hashCode（键）及（2 ^ N-1））。但如果你的函数来计算的hashCode对于给定的键不是很好，你一定会从几个哈希桶多键受苦。
但是，如果由于table_length数字，计算出的哈希码可以映射到不同的散列桶，即使你有一个稍微愚蠢的hashCode函数。
这里是证明。
如果假设你的hashCode函数的结果（其中包括）下列哈希码{X，2X，3X，4X，5X，6X ...}，那么所有这些都将是在短短的m个区段，其中m=table_length / GreatestCommonFactor数（ table_length，x）的。 （这是微不足道的验证/导出这一点）。现在，您可以执行下列操作之一，以避免
请确保您不会产生太多的哈希码是另一种的hashCode数倍，如在{X，2X，3X，4X，5X，6X ...}，但是这可能是一种困难的，如果你的哈希表中应该有数以百万计的条目。
或简单地通过使GreatestCommonFactor（table_length中，x）等于1，即，通过使table_length随x使米等于table_length。如果x可以是几乎任何数量然后确保table_length是一个数字。
很清楚的解释，用图片了。
编辑：作为一个总结，你有当所选择的数量相乘值，并增加他们全部获得unique价值的最佳机会。例如，给定一个字符串，每个字母价值与数量相乘，然后加入它们统统加起来会给你它的哈希值。
一个更好的问题是，到底为什么31号？
只需提供一个备份的观点有这个网站：
它争辩说你，而不是数量最多的桶可能以四舍五入到几个桶。这似乎是一个合理的概率。直观地说，我当然可以看到桶数量较多会更好，但我无法作出一个数学这一点。
你已经获得了一个典型的散列函数多项式的unique价值的好机会模P。
说，这样的哈希函数长度&=N的字符串，和你有一个collision。这2个不同的多项式产生的值取模P.那些多项式的差异是再次的次数n（或更少）的多项式。它没有N多根以上（这是这里的数学显示本身的性质，因为这种说法的一个多项式在一个字段=&号是唯一的真实）。因此，如果N是低于P少得多，则有可能不具有冲突。在此之后，或许可以表明，37足够大，以避免collision为具有长度5-10字符串的哈希表，并进行计算足够小。
这取决于哈希函数的选择。
许多哈希中通过将它们与系数相乘的数据的模2对应于计算机的字长（也就是自由通过只让计算溢出）的功率。
你不希望一个乘数因子之间的数据和哈希表的大小，那么就可能发生的变化的数据不超过整个表传播数据。如果您选择的表该factor的大小是极不可能的。
在另一方面，从奇由这些factor使你也应该是2的幂，你的哈希表（例如31时，它生成Java的hashCode（）方法）。
TL博士index[hash(input)%2]将导致一半所有可能的散列值和值的范围冲突。index[hash(input)%prime]结果在&2所有可能的哈希collision。固定的除数，以表的大小也确保了数不能大于表。
是唯一的号码。他们是
unique之处在于，一个产品
与任何其它数目的具有最好的
的是unique的（而不是作为唯一的机会
作为道）因本身
一个事实，即至
组成它。此属性在
哈希函数。
给出一个字符串“塞缪尔”，你可以
通过multiplication生成一个唯一的哈希
各成份的数字或
以数字字母和添加
它们。这就是为什么
技术。这里的关键在于理解
只要你可以生成一个
充分唯一键可以移动
其他散列技术了。去
这里以取得更多有关这个主题有关
对于一个哈希函数它不仅是重要的普遍减少colisions但让不可能留在哈希它，而chaning几个字节。
假设你有一个公式：(x + y*z) % key = x同0&x&key和0&z&key。
如果键是* Y=键是真实的每n在N和虚假的每一个其他号码。
一个例子，其中的关键不是一个例子：
X=1，Z=2，关键=8
键/ Z=4仍然是一个自然数，4为方程的解决方案，并在此情况下（N / 2）* Y=关键是真正对每一个n N中的方程解的金额已practially一倍8 ISN 'T A
如果我们的攻击者已经知道8是方程，他可以从生产8改变文件到4个可能的解决方案，仍然得到的散列。
本文标题 ：为什么要哈希函数使用一个素数模？
本文地址 ：CodeGo.net/67529/
Copyright (C) 2014 CodeGo.netJava核心技术卷一 Object，反射，泛型，拷贝 - 简书
<div class="fixed-btn note-fixed-download" data-toggle="popover" data-placement="left" data-html="true" data-trigger="hover" data-content=''>
写了9811字，被0人关注，获得了0个喜欢
Java核心技术卷一 Object，反射，泛型，拷贝
1.equals2.hashcode3.clone中的深拷贝，浅拷贝。如何实现重写子类中的clone。
4.获得class类型的类型实例（注意和实例对象分开）的方法5.反射6.泛型
这是Object类中提供的一种方法。这个方法作为比较的是两个对象是否引用指向同一个对象地址，实际用处不大（引用地址相同那不就是在用同一个对象了么。。能有不同么-。-）我们在子类中，为了实现其他相等测试时（例如两个对象的某个成员变量是否相等/两个对象是否为同一个类。。等等）时重写这个方法，最好首先时候父类中的equals方法，然后再根据自己需要的功能进行实现。同时还应遵守下一五个特性
2.hashcode
原先hashcod（哈希值，散列值，散列码）是由一种特殊算法输出的值，输入的对象不同，输出的值基本不可能相同。在这里Java中一般每个对象都有一个默认的hashcode，这个值时对象的存储地址。散列表（Hash table，也叫哈希表），是根据（Key）而直接访问在内存存储位置的。也就是说，它通过计算一个关于键值的函数，将所需查询的数据到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做，存放记录的数组称做散列表如果重写了equals方法就必须重写hashcode方法，他们两个定义必须一致（？？这是什么，不太懂）。然而字符串类型的hashcode是不一样的，他们如果字符串内容相同，则hashcode相同。算是上面的例子吗3.clone中的深拷贝，浅拷贝。如何实现重写子类中的clone。
clone是Object类中提供的另一种方法，由protected修饰，不能直接运用（里面也没写为什么不能直接运用，我理解是Object类这个方法不若是被使用时不能理解你所传的对象中的成员变量是否都为基本数值类型，如成员变量含有其他对象则拷贝方法不同）。
我们一般只是将对象引用赋予给另一个变量，例如
Student A = new Student（）；
Student B = A；//这里A和B都是指向同一个对象，因为只是将引用地址传给了另一个变量，这里A或者B对他们所指的对象进行修改时，另外一个变量所指的对象其实也在改变。
完全复制一个对象到一个新的空间，使得原对象和复制完的对象相互独立，互不影响时，就要使用到clone（）方法，不过需要我们自己实现。
clone 希望实现的效果
如何才能在子类或者其他类中使用clone方法呢？（object提供的clone是浅拷贝，经下列处理不重写也能用）
就算不重写，只是用原来的clone也需要这么做，不过只需要在实现中写成return super.clone(Object obj);
在这里Cloneable接口其实只是一个标志接口，里面并不需要我们实现任何方法，只是提醒我们这个类已经知道要进行克隆处理。
什么是深拷贝，浅拷贝呢？
假设有我们需要进行克隆的对象是A，按照A克隆出来的对象为B。在我们需要克隆的对象中，如果全部都是基本数值类型（int，double。。等等）。那么就没有问题，A或B其中一个对象发生改变，并不会影响另一个对象B或A。
若是A中的成员变量不是基本类型，而是对象类型。以为这有一个成员变量指向另一个对象。那么前拷贝并不会重新分配一个空间去进行这个成员变量的拷贝。而只是将引用地址传给了B中的成员变量。若是A或者B更改了这个引用类型的成员变量，那么另外一个都是受到影响，意味着其实他们在共用一个成员变量。（如是不可变的对象则没有关系，例如String的一旦构造完就不会改变。若类中方法对对象中的成员变量不作改变的，那么这个类实例化出来的就是不可变对象）
所以若需要深拷贝则需要我们自己重写，并理清其中的关系。4.获得class类对象（注意和实例对象分开）的方法
一。class myclass = obj.getClass（）；//使用getClass（）
意味着我们可以使用一些特殊的函数（方法）来查看一个类的成员变量类型，方法的返回类型，构造器甚至是参数类型等，这些都是利用反射机制来分析类的结构。6.泛型
当使用 Collection 时，我们经常要做的一件事情就是要进行类型转换，当转换成所需的类型以后，再对它们进行处理。很明显，这种设计给编程人员带来了极大的不便，同时也容易引入错误。
泛型提供了编译时类型安全检测机制，该机制允许程序员在编译时检测到非法的类型。意味着它的本质是参数化类型，也就是说所操作的数据类型被指定为一个参数。
如果觉得我的文章对您有用，请随意打赏。您的支持将鼓励我继续创作！
打开微信“扫一扫”，打开网页后点击屏幕右上角分享按钮
如果觉得我的文章对您有用，请随意打赏。您的支持将鼓励我继续创作！
选择支付方式：一个数学简单问题. 2化成分数可以是：1/2,2/4.吧?那么,1/2-2=?如果把2化成1/2,也就是1/2-1/2=0如果把2化成4/2,也就是1/2-4/2=-3/2两次的结果不一样啊.为什么啊.3q
2只能化成2/1,这才表示一分之二,你说的1/2表示二分之一,当然算起不一样咯
为您推荐：
扫描下载二维码问题：为什么对于同样的字符串str,strGetHashCode结果不同
描述:今天做了一个实验.在x86的PC上对于一个字符串使用GetHashCode()获取一个字符串的Hash(在PC上试验了WinForm和Asp.Net,结果是一样的)在Xscale CPU的WinCE上边对于同样的字符串也使用GetHashCode()获取Hash(在WinCE设备上和PPC2003、WM5、WM6模拟器的模拟器上结果都相同)然后比较发现他们俩不一样!这是为什么呢?刚才Google了一下，有说对于同样一个对象X86和X64平台下GetHashCode()的结果是不一样的。为什么不一样没说。我想问下为什么不一样呢？难道跟CPU有关？Google使用关键字GetHashCode CPU 结果令人失望！谁能给个解释啊？解决方案1:反编译String的GetHashCode看了看，其中需要用到实例的指针地址来计算HashCode,估计和这个有关系。呵呵，问题挺有意思的。
以上介绍了“为什么对于同样的字符串str,strGetHashCode结果不同”的问题解答，希望对有需要的网友有所帮助。
本文网址链接：/itwd/1081854.html
上一篇： 下一篇：}