散列 与 java

学过算法的朋友都知道，散列可以在一定程序上提高查找效率，甚至可以压缩一些序列。Java中也有些集合都用到了它。

下面先介绍一下散列。

散列，也叫hash，即经常听到的哈希表。

一般都是由一个固定长度的数组组成，经常会结合链表来实现。其实就是把任意长度的输入（即预映射，pre-image），通过特定的散列算法，变成固定长度的输出。最常用在信息安全领域的加密算法上面，但这里我们不讨论这个。

 　　在散列时，结构中存在关键字K，则把它映射到f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为 散列函数(Hash function)，按这个思想建立的表为散列表。

对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象称 冲突。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象” 作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。

若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数(Uniform Hash function)，这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

常用的构造散列函数的方法

散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位ǐ

1. 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a•key + b，其中a和b为常数（这种散列函数叫做自身函数）

2. 数字分析法

3. 平方取中法

4. 折叠法

5. 随机数法

6. 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。

处理冲突的方法

1. 开放寻址法；Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法：

1) di=1,2,3,…, m-1，称线性探测再散列； 即这位置有人，就查看下一个位置，没有就填入，否则……以此类推。

2) di=1^2, (-1)^2, 2^2,(-2)^2, (3)^2, …, ±(k)^2,(k<=m/2)称二次探测再散列;

3) di=伪随机数序列，称伪随机探测再散列。

          ……

2. 再散列法：Hi=RHi(key), i=1,2,…,k RHi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。

3. 链地址法(拉链法)

4. 建立一个公共溢出区

查找的性能分析

散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。

查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：

1. 散列函数是否均匀；

2. 处理冲突的方法；

3. 散列表的装填因子。

散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度

α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。

Java中的几个类：HashTable，HashMap，HashSet（下面简称hash类）就用到了这些散列算法。

首先第一个问题是，这些类中的f(key)是怎么产生的？

其实java中的所有类都有HashCode()的方法，它们都是从祖先：Object中继承来的。这个函数能对每一个实体对象都产生一个序列值，然后hash类就根据这个序列值来排定整个散列表。那么第二个问题出现了：按什么规则来存入值呢？这就要看eqauls方法了，它也是从Object中继承来的。我们可以通过重写这个方法来改变散列表的生成规则。

Java对于eqauls方法和hashCode方法是这样规定的：

1、如果两个对象相同，那么它们的hashCode值一定要相同；

2、如果两个对象的hashCode相同，它们并不一定相同。

第二句可能比较难理解，为什么hashCode相同的两个对象可以不同呢？很简单，因为我们可以重写hashCode()方法，我们可以让它return同一个值。这样的话就会造成混乱，散列算法也会失去它的作用，因为这时已经是一个单纯的链表了。所以Java API文档中提倡：Note   that   it   is   generally   necessary   to   override   the   hashCode   method   whenever  the  equal  method   is   overridden,   so   as   to   maintain   the   general   contract   for   the   hashCode   method,   which   states   that   equal   objects   must   have   equal   hash   codes. 即这两个方法必须同时重写。

下面来具体地看一下HashTable，HashMap，HashSet 这三个类。

1、HashTable

（下面内容摘自一篇博客：http://www.cnblogs.com/perhaps/archive/2006/01/06/312335.aspx ）

看一个程序：

public class TestHashtable {

publicstaticvoidmain(String[]args){

Hashtable<String,String>ht=newHashtable<String,String>();

ht.put("sichuan","chengdu");//改变以下四行代码的顺序，可能会改变输出内容的顺序

ht.put("hunan","changsha");

ht.put("beijing","beijing");

ht.put("anhui","hefei");

Enumeration<String>e=ht.keys();

while(e.hasMoreElements()){

Objectkey=e.nextElement();

Objectvalue=ht.get(key);

System.out.println(key+""+value+""+key.hashCode()+""+value.hashCode());

}

}

}

结果如下：

hunan changsha 99640558 1432430903

anhuihefei9296222399156333

sichuanchengdu2084411463742637738

beijing beijing -227176258 -227176258

改变一下那四行的顺序，如

ht.put("beijing","beijing");

ht.put("anhui","hefei");

ht.put("hunan","changsha");

 　   ht.put("sichuan","chengdu");

则结果变成：

hunan changsha 99640558 1432430903

sichuanchengdu2084411463742637738

anhuihefei9296222399156333

beijing beijing -227176258 -227176258

为了讲述Hashtable键排序的问题，我们先来看Hashtable的结构图：

        从上面的结构图可以看出，Hashtable的实质就是一个数组＋链表。图中的Entry就是链表的实现，Entry的结构中包含了对自己的另一个实例的引用next，用以指向另外一个Entry。而图中标有数字的部分是一个Entry数组，数字就是这个Entry数组的index。那么往Hashtable增加键值对的时候，index会根据键的hashcode、Entry数组的长度共同决定，从而决定键值对存放在Entry数组的哪个位置。从这种意义来说，当键一定，Entry数组的长度一定的情况下，所得到的index肯定是相同的，也就是说插入顺序应该不会影响输出的顺序才对。然而，还有一个重要的因素没有考虑，就是计算index出现相同值的情况。譬如代码中 "sichuan" 和 "anhui"，所得到的index是相同的，在这个时候，Entry的链表功能就发挥作用了：put方法通过Entry的next属性获得对另外一个Entry的引用，然后将后来者放入其中。根据debug得出的结果，"sichuan", "anhui"的index同为2，"hunan"的index为6，"beijing"的index为1，在输出的时候，会以index递减的方式获得键值对。很明显，会改变的输出顺序只有"sichuan"和"anhui"了，也就是说输出只有两种可能："hunan" - "sichuan" - "anhui" - "beijing"和"hunan" - "anhui" - "sichuan" - "beijing"。以下是运行了示例代码之后，Hashtable的结果：

            以上的讨论基于Java展开的，在C#中的Hashtable实现会有所不同，但是我相信两者的设计应该是差不多的。

        [补充]：在Hashtable的实现代码中，有一个名为rehash的方法用于扩充Hashtable的容量。很明显，当rehash方法被调用

以后，每一个键值对相应的index也会改变，也就等于将键值对重新排序了。这也是往不同容量的Hashtable放入相同的键值对会输出不同的键值对序列的原因。在Java中，触发rehash方法的条件很简单：hahtable中的键值对超过某一阀值。默认情况下，该阀值等于hashtable中Entry数组的长度×0.75。

2、HashMap

它的构造思想和用法 与HashTable差不多，只是 它是不同步且允许使用 null 这两点有点差异。

下面我摘抄了它的设计思路供大家看看： 

设计思路

此实现假定哈希函数将元素正确分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。迭代集合视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）的和成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。 HashMap 的实例有两个参数影响其性能：初始容量 和加载因子。容量 是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，通过调用 rehash 方法将容量翻倍。 通常，默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地降低 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。 如果很多映射关系要存储在 HashMap 实例中，则相对于按需执行自动的 rehash 操作以增大表的容量来说，使用足够大的初始容量创建它将使得映射关系能更有效地存储。 注意，此实现不是同步的。如果多个线程同时访问此映射，而其中至少一个线程从结构上修改了该映射，则它必须 保持外部同步。（结构上的修改是指添加或删除一个或多个映射关系的操作；仅改变与实例已经包含的键关联的值不是结构上的修改。）这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedMap 方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射进行意外的不同步访问，如下所示： Map m = Collections.synchronizedMap(new HashMap(...)); 由所有此类的“集合视图方法”所返回的迭代器都是快速失败 的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器自身的 remove 或 add 方法，其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒在将来不确定的时间任意发生不确定行为的风险。 注意，迭代器的快速失败行为不能得到保证，一般来说，存在不同步的并发修改时，不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此，编写依赖于此异常程序的方式是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。

(其实有些我也看不懂！呵呵……)

3、HashSet

先看一个程序：

    Set<String> setA=(Set<String>)new HashSet();

setA.add(newString("ABC"));

setA.add(newString("CC"));

setA.add(newString("ABC"));

setA.add(newString("BB"));

    setA.add(new String("ABC"));

    System.out.println("size="+setA.size()); //3, 相同的项不存储

Iterator<String>ite=setA.iterator();

while(ite.hasNext()){

 　　　　System.out.println(ite.next());//CC BB ABC

    }  

从结果中可以看出，HashSet不存储相同项。至于它是遇到相同项时覆盖原来项，还是直接丢弃 我就不清楚 了。

我想，HashSet最后构造出来的表可以看成一个数组，没有链表对数组结点进行扩充。

这三个类的基本原理都是一样 的，只是它们在处理的过程中的一些机制有所不同而矣。