散列表（Hash table）

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

一、基本概念

l散列函数(Hash function)：若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。

l冲突：对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。

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

综上所述，根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。

二、构造散列函数的方法

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

l数字分析法：找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址；

l平方取中法: 取关键字平方后的中间几位作为散列地址；

l折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址；

l随机数法: 选择一个随机函数，取关键字的随机函数值为它的散列地址，即h(key)=random(key)，其中random为伪随机函数，但要保证函数值是在0到m-1之间；

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

三、处理冲突的方法

l开放寻址法：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=伪随机数序列，称伪随机探测再散列。

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

l链地址法（拉链法）：将所有关键字为同义词的记录存储在同一线性链表中；

l建立一个公共溢出区。

四、查找性能分析

在哈希表上进行查找的过程和哈希造表的过程是一致的。一些关键码可通过散列函数转换的地址直接找到，而另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。查找过程中，关键码的比较次数，取决于产生冲突的多少，影响产生冲突多少有以下三个因素：

      1.   散列函数是否均匀；

      2.   处理冲突的方法；

      3.   散列表的装填因子α= 填入表中的元素个数 / 散列表的长度。

α是散列表装满程度的标志因子。散列表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。

五、散列表java实现（MyHashtable）

 下面是散列表的一个简单实现，采用开放寻址法线性探测解决冲突，参考《数据结构Java语言描》，Micheal Main著。

 

public class MyHashtable {
	
	private int manyItems;//表中元素个数
	private Object[] keys;
	private Object[] data;
	private boolean[] hasBeenUsed;//若索引i处存在元素，则hasBeenUsed[i]为ture，否则为false
	
	public MyHashtable(int capacity) {
		if(capacity <= 0)
			throw new IllegalArgumentException("capacity is negative");
		
		keys = new Object[capacity];
		data = new Object[capacity];
		hasBeenUsed = new boolean[capacity];
	}
	
	//hash函数
	private int hash(Object key) {
		return Math.abs(key.hashCode()%data.length);
	}
	
	//当前索引发生冲突，找下一索引
	private int nextIndex(int i) {
		if(i + 1 == data.length) {
			return 0;
		} else {
			return i + 1;
		}
	}
	
	//如果在表中找到指定的关键字，返回值为关键字的索引，否则返回-1
	private int findIndex(Object key) {
		int count = 0;
		int i = hash(key);
		
		while((count < data.length) && hasBeenUsed[i]) {
			if(key.equals(keys[i])) {
				return i;
			} else {
				count++;
				i = nextIndex(i);
			}
		}
		return -1;
	}
	
	public Object get(Object key) {
		int index = findIndex(key);
		
		if(index == -1) {
			return null;
		} else {
			return data[index];
		}
	}
	
	public Object put(Object key, Object element) {
		int index = findIndex(key);
		Object answer;
		
		if(index != -1) {
			answer = data[index];
			data[index] = element;
			return answer;
		} else if(manyItems < data.length) {
			index = hash(key);
			while(keys[index] != null) {
				index = nextIndex(index);
			}
			keys[index] = key;
			data[index] = element;
			hasBeenUsed[index] = true;
			manyItems++;
			return null;
		} else {
			throw new IllegalStateException("Hashtable is full!");
		}
	}
	
	public Object remove(Object key) {
		int index = findIndex(key);
		Object answer = null;
		
		if(index != -1) {
			answer = data[index];
			data[index] = null;
			keys[index] = null;
			manyItems--;
		}
		return answer;
	}
	
	public boolean contains (Object key) {
		return (findIndex(key) != -1);
	}
	
	public static void main(String[] args) {
		MyHashtable table = new MyHashtable(100);
		
		table.put(1, "china");
		table.put(2, "美国");
		System.out.println(table.get(2).toString());
	}
}