Java数据结构和算法（十三）——哈希表

　　Hash表也称散列表，也有直接译作哈希表，Hash表是一种根据关键字值（key - value）而直接进行访问的数据结构。它基于数组，通过把关键字映射到数组的某个下标来加快查找速度，但是又和数组、链表、树等数据结构不同，在这些数据结构中查找某个关键字，通常要遍历整个数据结构，也就是O(N)的时间级，但是对于哈希表来说，只是O(1)的时间级。

　　注意，这里有个重要的问题就是如何把关键字转换为数组的下标，这个转换的函数称为哈希函数（也称散列函数），转换的过程称为哈希化。

1、哈希函数的引入

　　大家都用过字典，字典的优点是我们可以通过前面的目录快速定位到所要查找的单词。如果我们想把一本英文字典的每个单词，从 a 到 zyzzyva(这是牛津字典的最后一个单词)，都写入计算机内存，以便快速读写，那么哈希表是个不错的选择。

　　这里我们将范围缩小点，比如想在内存中存储5000个英文单词。我们可能想到每个单词会占用一个数组单元，那么数组的大小是5000，同时可以用数组下标存取单词，这样设想很完美，但是数组下标和单词怎么建立联系呢？

　　首先我们要建立单词和数字（数组下标）的关系：

　　我们知道 ASCII 是一种编码，其中 a 表示97，b表示98，以此类推，一直到122表示z，而每个单词都是由这26个字母组成，我们可以不用 ASCII 编码那么大的数字，自己设计一套类似 ASCII的编码，比如a表示1，b表示2，依次类推，z表示26，那么表示方法我们就知道了。

　　接下来如何把单个字母的数字组合成代表整个单词的数字呢？

　　①、把数字相加

　　首先第一种简单的方法就是把单词的每个字母表示的数字相加，得到的和便是数组的下标。

　　比如单词 cats 转换成数字：

　　cats = 3 + 1 + 20 + 19 = 43

　　那么单词 cats 存储在数组中的下标为43，所有的英文单词都可以用这个办法转换成数组下标。但是这个办法真的可行吗？

　　假设我们约定一个单词最多有 10 个字母，那么字典的最后一个单词为 zzzzzzzzzz ，其转换为数字：

　　zzzzzzzzzz = 26*10 = 260

　　那么我们可以得到单词编码的范围是从1-260。很显然，这个范围是不够存储5000个单词的，那么肯定有一个位置存储了多个单词，每个数组的数据项平均要存储192个单词（5000除以260）。

　　对于上面的问题，我们如何解决呢？

　　第一种方法：考虑每个数组项包含一个子数组或者一个子链表，这个办法存数据项确实很快，但是如果我们想要从192个单词中查找到其中一个，那么还是很慢。

　　第二种方法：为啥要让那么多单词占据同一个数据项呢？也就是说我们没有把单词分的足够开，数组能表示的元素太少，我们需要扩展数组的下标，使其每个位置都只存放一个单词。

　　对于上面的第二种方法，问题产生了，我们如何扩展数组的下标呢？

　　②、幂的连乘

　　我们将单词表示的数拆成数列，用适当的 27 的幂乘以这些位数（因为有26个可能的字符，以及空格，一共27个），然后把乘积相加，这样就得出了每个单词独一无二的数字。

　　比如把单词cats 转换为数字：

　　cats = 3*273 + 1*272 + 20*271 + 19*270 = 59049 + 729 + 540 + 19 = 60337

　　这个过程会为每个单词创建一个独一无二的数，但是注意的是我们这里只是计算了 4 个字母组成的单词，如果单词很长，比如最长的10个字母的单词 zzzzzzzzzz，仅仅是279 结果就超出了7000000000000，这个结果是很巨大的，在实际内存中，根本不可能为一个数组分配这么大的空间。

　　所以这个方案的问题就是虽然为每个单词都分配了独一无二的下标，但是只有一小部分存放了单词，很大一部分都是空着的。那么现在就需要一种方法，把数位幂的连乘系统中得到的巨大的整数范围压缩到可接受的数组范围中。

　　对于英语字典，假设只有5000个单词，这里我们选定容量为10000 的数组空间来存放（后面会介绍为啥需要多出一倍的空间）。那么我们就需要将从 0 到超过 7000000000000 的范围，压缩到从0到10000的范围。

　　第一种方法：取余，得到一个数被另一个整数除后的余数。首先我们假设要把从0-199的数字（用largeNumber表示），压缩为从0-9的数字（用smallNumber表示），后者有10个数，所以变量smallRange 的值为10，这个转换的表达式为：

　　smallNumber = largeNumber % smallRange

　　当一个数被 10 整除时，余数一定在0-9之间，这样，我们就把从0-199的数压缩为从0-9的数，压缩率为 20 :1。

　　我们也可以用类似的方法把表示单词唯一的数压缩成数组的下标：

　　arrayIndex = largerNumber % smallRange

　　这也就是哈希函数。它把一个大范围的数字哈希（转化）成一个小范围的数字，这个小范围的数对应着数组的下标。使用哈希函数向数组插入数据后，这个数组就是哈希表。

2、冲突

　　把巨大的数字范围压缩到较小的数字范围，那么肯定会有几个不同的单词哈希化到同一个数组下标，即产生了冲突。

　　冲突可能会导致哈希化方案无法实施，前面我们说指定的数组范围大小是实际存储数据的两倍，因此可能有一半的空间是空着的，所以，当冲突产生时，一个方法是通过系统的方法找到数组的一个空位，并把这个单词填入，而不再用哈希函数得到数组的下标，这种方法称为开放地址法。比如加入单词 cats 哈希化的结果为5421，但是它的位置已经被单词parsnip占用了，那么我们会考虑将单词 cats 存放在parsnip后面的一个位置 5422 上。

　　另一种方法，前面我们也提到过，就是数组的每个数据项都创建一个子链表或子数组，那么数组内不直接存放单词，当产生冲突时，新的数据项直接存放到这个数组下标表示的链表中，这种方法称为链地址法。

3、开放地址法

　　开发地址法中，若数据项不能直接存放在由哈希函数所计算出来的数组下标时，就要寻找其他的位置。分别有三种方法：线性探测、二次探测以及再哈希法。

　　①、线性探测

　　在线性探测中，它会线性的查找空白单元。比如如果 5421 是要插入数据的位置，但是它已经被占用了，那么就使用5422，如果5422也被占用了，那么使用5423，以此类推，数组下标依次递增，直到找到空白的位置。这就叫做线性探测，因为它沿着数组下标一步一步顺序的查找空白单元。

　　完整代码：

package com.ys.hash;

public class MyHashTable {
	private DataItem[] hashArray;	//DataItem类，表示每个数据项信息
	private int arraySize;//数组的初始大小
	private int itemNum;//数组实际存储了多少项数据
	private DataItem nonItem;//用于删除数据项
	
	public MyHashTable(int arraySize){
		this.arraySize = arraySize;
		hashArray = new DataItem[arraySize];
		nonItem = new DataItem(-1);//删除的数据项下标为-1
	}
	//判断数组是否存储满了
	public boolean isFull(){
		return (itemNum == arraySize);
	}
	
	//判断数组是否为空
	public boolean isEmpty(){
		return (itemNum == 0);
	}
	
	//打印数组内容
	public void display(){
		System.out.println("Table:");
		for(int j = 0 ; j < arraySize ; j++){
			if(hashArray[j] != null){
				System.out.print(hashArray[j].getKey() + " ");
			}else{
				System.out.print("** ");
			}
		}
	}
	//通过哈希函数转换得到数组下标
	public int hashFunction(int key){
		return key%arraySize;
	}
	
	//插入数据项
	public void insert(DataItem item){
		if(isFull()){
			//扩展哈希表
			System.out.println("哈希表已满，重新哈希化...");
			extendHashTable();
		}
		int key = item.getKey();
		int hashVal = hashFunction(key);
		while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1){
			++hashVal;
			hashVal %= arraySize;
		}
		hashArray[hashVal] = item;
		itemNum++;
	}
	/**
	 * 数组有固定的大小，而且不能扩展，所以扩展哈希表只能另外创建一个更大的数组，然后把旧数组中的数据插到新的数组中。
	 * 但是哈希表是根据数组大小计算给定数据的位置的，所以这些数据项不能再放在新数组中和老数组相同的位置上。
	 * 因此不能直接拷贝，需要按顺序遍历老数组，并使用insert方法向新数组中插入每个数据项。
	 * 这个过程叫做重新哈希化。这是一个耗时的过程，但如果数组要进行扩展，这个过程是必须的。
	 */
	public void extendHashTable(){
		int num = arraySize;
		itemNum = 0;//重新计数，因为下面要把原来的数据转移到新的扩张的数组中
		arraySize *= 2;//数组大小翻倍
		DataItem[] oldHashArray = hashArray;
		hashArray = new DataItem[arraySize];
		for(int i = 0 ; i < num ; i++){
			insert(oldHashArray[i]);
		}
	}
	
	//删除数据项
	public DataItem delete(int key){
		if(isEmpty()){
			System.out.println("Hash Table is Empty!");
			return null;
		}
		int hashVal = hashFunction(key);
		while(hashArray[hashVal] != null){
			if(hashArray[hashVal].getKey() == key){
				DataItem temp = hashArray[hashVal];
				hashArray[hashVal] = nonItem;//nonItem表示空Item,其key为-1
				itemNum--;
				return temp;
			}
			++hashVal;
			hashVal %= arraySize;
		}
		return null;
	}
	
	//查找数据项
	public DataItem find(int key){
		int hashVal = hashFunction(key);
		while(hashArray[hashVal] != null){
			if(hashArray[hashVal].getKey() == key){
				return hashArray[hashVal];
			}
			++hashVal;
			hashVal %= arraySize;
		}
		return null;
	}
	
	public static class DataItem{
		private int iData;
		public DataItem(int iData){
			this.iData = iData;
		}
		public int getKey(){
			return iData;
		}
	}

}

　　需要注意的是，当哈希表变得太满时，我们需要扩展数组，但是需要注意的是，数据项不能放到新数组中和老数组相同的位置，而是要根据数组大小重新计算插入位置。这是一个比较耗时的过程，所以一般我们要确定数据的范围，给定好数组的大小，而不再扩容。

　　另外，当哈希表变得比较满时，我们每插入一个新的数据，都要频繁的探测插入位置，因为可能很多位置都被前面插入的数据所占用了，这称为聚集。数组填的越满，聚集越可能发生。

　　这就像人群，当某个人在商场晕倒时，人群就会慢慢聚集。最初的人群聚过来是因为看到了那个倒下的人，而后面聚过来的人是因为它们想知道这些人聚在一起看什么。人群聚集的越大，吸引的人就会越多。

　　②、装填因子

　　已填入哈希表的数据项和表长的比率叫做装填因子，比如有10000个单元的哈希表填入了6667 个数据后，其装填因子为 2/3。当装填因子不太大时，聚集分布的比较连贯，而装填因子比较大时，则聚集发生的很大了。

　　我们知道线性探测是一步一步的往后面探测，当装填因子比较大时，会频繁的产生聚集，那么如果我们探测比较大的单元，而不是一步一步的探测呢，这就是下面要讲的二次探测。

　　③、二次探测

 　　二测探测是防止聚集产生的一种方式，思想是探测相距较远的单元，而不是和原始位置相邻的单元。

　　线性探测中，如果哈希函数计算的原始下标是x, 线性探测就是x+1, x+2, x+3, 以此类推；而在二次探测中，探测的过程是x+1, x+4, x+9, x+16，以此类推，到原始位置的距离是步数的平方。二次探测虽然消除了原始的聚集问题，但是产生了另一种更细的聚集问题，叫二次聚集：比如讲184，302，420和544依次插入表中，它们的映射都是7，那么302需要以1为步长探测，420需要以4为步长探测， 544需要以9为步长探测。只要有一项其关键字映射到7，就需要更长步长的探测，这个现象叫做二次聚集。二次聚集不是一个严重的问题，但是二次探测不会经常使用，因为还有好的解决方法，比如再哈希法。

　　④、再哈希法

　　为了消除原始聚集和二次聚集，我们使用另外一种方法：再哈希法。

　　我们知道二次聚集的原因是，二测探测的算法产生的探测序列步长总是固定的：1,4，9,16以此类推。那么我们想到的是需要产生一种依赖关键字的探测序列，而不是每个关键字都一样，那么，不同的关键字即使映射到相同的数组下标，也可以使用不同的探测序列。

　　方法是把关键字用不同的哈希函数再做一遍哈希化，用这个结果作为步长。对于指定的关键字，步长在整个探测中是不变的，不过不同的关键字使用不同的步长。

　　第二个哈希函数必须具备如下特点：

　　一、和第一个哈希函数不同

　　二、不能输出0（否则，将没有步长，每次探测都是原地踏步，算法将陷入死循环）。

　　专家们已经发现下面形式的哈希函数工作的非常好：stepSize = constant - key % constant; 其中constant是质数，且小于数组容量。
　　再哈希法要求表的容量是一个质数，假如表长度为15(0-14)，非质数，有一个特定关键字映射到0，步长为5，则探测序列是0,5,10,0,5,10,以此类推一直循环下去。算法只尝试这三个单元，所以不可能找到某些空白单元，最终算法导致崩溃。如果数组容量为13, 质数，探测序列最终会访问所有单元。即0,5,10,2,7,12,4,9,1,6,11,3,一直下去，只要表中有一个空位，就可以探测到它。

　　完整再哈希法代码：

package com.ys.hash;

public class HashDouble {
	private DataItem[] hashArray;	//DataItem类，表示每个数据项信息
	private int arraySize;//数组的初始大小
	private int itemNum;//数组实际存储了多少项数据
	private DataItem nonItem;//用于删除数据项
	
	public HashDouble(){
		this.arraySize = 13;
		hashArray = new DataItem[arraySize];
		nonItem = new DataItem(-1);//删除的数据项下标为-1
	}
	//判断数组是否存储满了
	public boolean isFull(){
		return (itemNum == arraySize);
	}
	
	//判断数组是否为空
	public boolean isEmpty(){
		return (itemNum == 0);
	}
	
	//打印数组内容
	public void display(){
		System.out.println("Table:");
		for(int j = 0 ; j < arraySize ; j++){
			if(hashArray[j] != null){
				System.out.print(hashArray[j].getKey() + " ");
			}else{
				System.out.print("** ");
			}
		}
	}
	//通过哈希函数转换得到数组下标
	public int hashFunction1(int key){
		return key%arraySize;
	}
	
	public int hashFunction2(int key){
		return 5 - key%5;
	}
	
	//插入数据项
	public void insert(DataItem item){
		if(isFull()){
			//扩展哈希表
			System.out.println("哈希表已满，重新哈希化...");
			extendHashTable();
		}
		int key = item.getKey();
		int hashVal = hashFunction1(key);
		int stepSize = hashFunction2(key);//用第二个哈希函数计算探测步数
		while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1){
			hashVal += stepSize;
			hashVal %= arraySize;//以指定的步数向后探测
		}
		hashArray[hashVal] = item;
		itemNum++;
	}

	/**
	 * 数组有固定的大小，而且不能扩展，所以扩展哈希表只能另外创建一个更大的数组，然后把旧数组中的数据插到新的数组中。
	 * 但是哈希表是根据数组大小计算给定数据的位置的，所以这些数据项不能再放在新数组中和老数组相同的位置上。
	 * 因此不能直接拷贝，需要按顺序遍历老数组，并使用insert方法向新数组中插入每个数据项。
	 * 这个过程叫做重新哈希化。这是一个耗时的过程，但如果数组要进行扩展，这个过程是必须的。
	 */
	public void extendHashTable(){
		int num = arraySize;
		itemNum = 0;//重新计数，因为下面要把原来的数据转移到新的扩张的数组中
		arraySize *= 2;//数组大小翻倍
		DataItem[] oldHashArray = hashArray;
		hashArray = new DataItem[arraySize];
		for(int i = 0 ; i < num ; i++){
			insert(oldHashArray[i]);
		}
	}
	
	//删除数据项
	public DataItem delete(int key){
		if(isEmpty()){
			System.out.println("Hash Table is Empty!");
			return null;
		}
		int hashVal = hashFunction1(key);
		int stepSize = hashFunction2(key);
		while(hashArray[hashVal] != null){
			if(hashArray[hashVal].getKey() == key){
				DataItem temp = hashArray[hashVal];
				hashArray[hashVal] = nonItem;//nonItem表示空Item,其key为-1
				itemNum--;
				return temp;
			}
			hashVal += stepSize;
			hashVal %= arraySize;
		}
		return null;
	}
	
	//查找数据项
	public DataItem find(int key){
		int hashVal = hashFunction1(key);
		int stepSize = hashFunction2(key);
		while(hashArray[hashVal] != null){
			if(hashArray[hashVal].getKey() == key){
				return hashArray[hashVal];
			}
			hashVal += stepSize;
			hashVal %= arraySize;
		}
		return null;
	}
	public static class DataItem{
		private int iData;
		public DataItem(int iData){
			this.iData = iData;
		}
		public int getKey(){
			return iData;
		}
	}
}

4、链地址法

　　在开放地址法中，通过再哈希法寻找一个空位解决冲突问题，另一个方法是在哈希表每个单元中设置链表（即链地址法），某个数据项的关键字值还是像通常一样映射到哈希表的单元，而数据项本身插入到这个单元的链表中。其他同样映射到这个位置的数据项只需要加到链表中，不需要在原始的数组中寻找空位。

　　有序链表：

package com.ys.hash;

public class SortLink {
	private LinkNode first;
	public SortLink(){
		first = null;
	}
	public boolean isEmpty(){
		return (first == null);
	}
	public void insert(LinkNode node){
		int key = node.getKey();
		LinkNode previous = null;
		LinkNode current = first;
		while(current != null && current.getKey() < key){
			previous = current;
			current = current.next;
		}
		if(previous == null){
			first = node;
		}else{
			previous.next = node;
		}
　　　　　　node.next = curent;
	}
	public void delete(int key){
		LinkNode previous = null;
		LinkNode current = first;
		if(isEmpty()){
			System.out.println("Linked is Empty!!!");
			return;
		}
		while(current != null && current.getKey() != key){
			previous = current;
			current = current.next;
		}
		if(previous == null){
			first = first.next;
		}else{
			previous.next = current.next;
		}
	}
	
	public LinkNode find(int key){
		LinkNode current = first;
		while(current != null && current.getKey() <= key){
			if(current.getKey() == key){
				return current;
			}
                        current = current.next;
		}
		return null;
	}
	
	public void displayLink(){
		System.out.println("Link(First->Last)");
		LinkNode current = first;
		while(current != null){
			current.displayLink();
			current = current.next;
		}
		System.out.println("");
	}
	class LinkNode{
		private int iData;
		public LinkNode next;
		public LinkNode(int iData){
			this.iData = iData;
		}
		public int getKey(){
			return iData;
		}
		public void displayLink(){
			System.out.println(iData + " ");
		}
	}
}

　　链地址法：

package com.ys.hash;

import com.ys.hash.SortLink.LinkNode;

public class HashChain {
	private SortLink[] hashArray;//数组中存放链表
	private int arraySize;
	public HashChain(int size){
		arraySize = size;
		hashArray = new SortLink[arraySize];
		//new 出每个空链表初始化数组
		for(int i = 0 ; i < arraySize ; i++){
			hashArray[i] = new SortLink();
		}
	}
	
	public void displayTable(){
		for(int i = 0 ; i < arraySize ; i++){
			System.out.print(i + "：");
			hashArray[i].displayLink();
		}
	}
	
	public int hashFunction(int key){
		return key%arraySize;
	}
	
	public void insert(LinkNode node){
		int key = node.getKey();
		int hashVal = hashFunction(key);
		hashArray[hashVal].insert(node);//直接往链表中添加即可
	}
	
	public LinkNode delete(int key){
		int hashVal = hashFunction(key);
		LinkNode temp = find(key);
		hashArray[hashVal].delete(key);//从链表中找到要删除的数据项，直接删除
		return temp;
	}
	
	public LinkNode find(int key){
		int hashVal = hashFunction(key);
		LinkNode node = hashArray[hashVal].find(key);
		return node;
	}

}

　　链地址法中，装填因子（数据项数和哈希表容量的比值）与开放地址法不同，在链地址法中，需要有N个单元的数组中转入N个或更多的数据项，因此装填因子一般为1，或比1大（有可能某些位置包含的链表中包含两个或两个以上的数据项）。

　　找到初始单元需要O(1)的时间级别，而搜索链表的时间与M成正比，M为链表包含的平均项数，即O(M)的时间级别。

5、桶

　　另外一种方法类似于链地址法，它是在每个数据项中使用子数组，而不是链表。这样的数组称为桶。

　　这个方法显然不如链表有效，因为桶的容量不好选择，如果容量太小，可能会溢出，如果太大，又造成性能浪费，而链表是动态分配的，不存在此问题。所以一般不使用桶。

6、总结 

　　哈希表基于数组，类似于key-value的存储形式，关键字值通过哈希函数映射为数组的下标，如果一个关键字哈希化到已占用的数组单元，这种情况称为冲突。用来解决冲突的有两种方法：开放地址法和链地址法。在开发地址法中，把冲突的数据项放在数组的其它位置；在链地址法中，每个单元都包含一个链表，把所有映射到同一数组下标的数据项都插入到这个链表中。