java散列实现

散列 是一种无需查找、只用元素的查找键确定元素索引的方法。（数组本身就是一个散列）。

散列函数 使用一个查找键，在散列表中产生一个元素的整数索引。

完美的散列函数 将每个查找键映射为一个不同整数，以改整数作为散列表的索引正恰当。

典型的散列函数 不是完美的，因为它们可以允许不只一个查找键映射到同一个索引，导致散列表的冲突。

  任何函数都可以作为散列函数，但是不一定是一个好的散列函数，好的散列函数必须，使冲突最少、计算快。（为了减少冲突的几率，应该选择使元素均匀地分布在散列表中的散列函数）

计算散列码

类类型散列码

JAVA的积累Object有一个方法hashCode返回一个整数散列码。如果每一个类不覆盖hashCode，该方法就返回由调用对象的内存地址导出的一个int值。为了对词典之类的实现有用，散列必须将相等的对象映射到散列表中的相同位置。因此应定义自己版本的hashCode ；

方法hashCode的准则：

如果一个类覆盖了方法equals，则应该覆盖hashCode

如果方法equals认为两个对象相等，则hashCode对这两个对象必须返回相同的值

如果在程序执行过程中一个对象不只一次调用hashCode，并且如果在这一段时间内对象的数据保持不变，则hashCode必须返回相同的散列码。

在同一程序的两次执行过程中，对象的散列码可以不同。

字符串的散列码

 通常，首先为字符串的每一个字符分配一个整数，然后相加。但是这样会造成很多冲突，同时散列表也是非常稀疏的。

 更好的办法使将每个字符的Unicode值乘以一个基于该字符在字符串中位置的因子，再相加。

具体的说：

字符串s含有n个字符，并且u i u_iu

i

是s中第i个字符的Unicode值，则对某个正整数g，散列码可以有如下形式：u 0 g n − 1 + u 1 g n − 2 + . . . + u n − 2 g + u n − 1 u_0g^{n-1}+u_1g^{n-2}+...+u_{n-2}g^+u_{n-1}u

0

​

g

n−1

+u

1

​

g

n−2

+...+u

n−2

​

g

+

u

n−1

​

这个计算可能导致溢出，特别是对于长字符串更是如此。但Java忽略这些溢出，并且对于适当选择g，其结果是合理的散列码。Java类String中目前的方法hashCode使用这个公职并以31作为g值。但是应意识到，移出可能导致负的结果。不过可以在将散列码压缩为散列表的恰当索引时加以处理。

基本类型的散列码

 对于位数在int型一下的可以用查找键本身转换成int作为散列。对于其他位数多余int的类型 ，可以利用它们内部二进制表示。如果查找键是long类型的整数，一种是直接转换成int，但是会忽略掉高32为带来的影响。另一种是将它分为若干部分，然后再使用假发或者抑或这样的按位布尔运算将这些部分结合起来，这个过程称为折叠。

将散列码压缩为散列表的索引

 缩放一个整数使之位于一个给定取值范围内通常使用取模运算。取模后的奇偶性，c % n c % nc%n 如果n为偶数那么结果的奇偶性于c的奇偶性相同。（注意：基于呢村子之的散列码通常是偶数）散列表的索引就会有相同的偏向。因此n只能是奇数，索引才能使均匀的。

散列表的长度应该是素数n，则如果使用c % n c%nc%n将正的散列码c压缩为索引，索引将在0到n-1之间均匀粉不。

如果c是负数，那么结果僵尸1-n到0之间，结果为0没关系，但如果结果为负，令它加上n，就可以使之在1到n-1之间。

冲突处理

线性探测开放定址

 通过从初始散列索引开始考察散列中连续位置，并寻找下一个可用位置，以解决散列过程中的冲突。

 线性探测可以检测散列表中每一个位置。因此只要散列表不是满的，这种探测就可以确保add操作的成功。

删除 从一个位置删除元素的最简单的方式是将null放进这个为置。虽然散列表中在探测到从未使用过的位置应该终止查找，但是已用过且现在可重新使用的位置不应该终止查找。

 因此需要区分散列中三种位置：

被占用—该位置引用了词典中一个元素

空闲—该位置含有null并历来如此

可用—该位置的元素从词典中删除

开放定址处理冲突时词典操作所需的查找

为了检测一个位置，getValu(key)在探测序列中查找key。它检测现有的元素，忽略处于可用状态的位置，查找终止于key被周到时或遇到null时。

操作remove(key)使用于检索操作相同逻辑查找探测序列。如果找到key，他就将该位置标记为可用。

操作add(key,value)使用与检索操作类似的逻辑查找探测序列，但它也记录遇到的第一个处于可用状态位置的索引就，如果key未找到，则使用这个位置放置新元素。

聚集 用线性探测处理冲突导致散列表中成组的连续位置被占用，每个组成为一个聚群，这种现象陈给一次聚集 随着聚群长度的增加，他们可能合并为更大的聚群。

二次探测开放定址

&emsb;给定的查找键散列到索引k，线性探测将查看从索引k开始的连续位置，而二次探测则另辟途径，考虑索引k + j 2 ( j ≥ 0 ) k+j^2(jgeq0)k+j

2

(j≥0)处的位置，换句话说，它使用索引k、k+1、k+4、k+9…

&emsb;尽管二次探测避免了一次聚集，它可能导致另一种不同的聚集，成为二次聚集 但二次聚集通常不是一个严重的问题。

二次探测

对于j ≥ 0 jgeq0j≥0 检查散列表中位于原来的散列索引加上j 2 j^2j

2

处的位置，已解决散列过程中的冲突；

如果散列表的长度时素数，则可达到散列表中一半的位置；

避免了一次聚集但可导致二次聚集。

双散列开放定址

使用第二个散列函数，以依赖于查找键的方式计算这些增量，因此既避免了一次聚集又避免了二次聚集。

双散列

散列过程中处理冲突的方法为，检查散列表中位于初始散列索引加上由第二个散列函数生成的增量处的位置。第二个散列函数应该：与第一个散列函数不同；依赖于查找键；具有非0值；

+如果散列表的长度是素数，则可探测到散列表中所有位置。

+既避免了一次聚集又避免了二次聚集。

开放定址存在的问题

&ensb;前三种处理冲突的开放定址方案假定每个散列表都处于三种状况之一：被占据、空闲或可用，其中只有空闲位置才含有null。频繁的插入或删除可能导致散列表中的每一个位置或引用一个当前位置，或引用一个以前的位置。也就是说散列中只含有少量的词典元素，却没有null的位置。

链地址

&ensb;使每个位置可以表示不只一个值。这样的位置称为桶。一旦新的查找键被映射到一个特定位置，就简单的将这个键和他相关联的值放入桶中。为了找到这个键进行散列，找到桶，然后查看桶中的键-值对。在删除一个元素时，从它的桶中找到并删除。

链地址提供了一种高效且简单的处理冲突的方法，然而因为改变了散列的结构，所以链地址比开放定址需要更多的内存。