Hash表

[color=red][b]哈希表总结[/b][/color]
一、哈希表的概念及作用
一般的线性表，树中，记录在结构中的相对位置是随机的，即和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上，查找的效率依赖于查找过程中所进行的比较次数。
理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。
冲突现象：不同的关键字可能得到同一哈希地址。
二、哈希表的构造方法
1.直接定址法 哈希码就是关键字自身
2.数字分析法
有学生的生日数据如下：75.10.03 75.11.23 76.03.02
经分析,第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增加，所以尽量不取前三位，取后三位比较好。
3.平方取中法
取关键字平方后的中间几位为哈希地址。
4.折叠法
将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址，这方法称为折叠法。
例如：如果一本书的编号为0-442-20586-4,则：
5864 5864
4220 0224
+) 04 +) 04
----------- -----------
10088 6092
H(key)=0088 H(key)=6092

(a)移位叠加 (b)间界叠加
５、除留余数法
取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。
H(key)=key MOD p (p<=m)
６、随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即
H(key)=random(key) ,其中random为随机函数。通常用于关键字长度不等时采用此法。
二、处理冲突的方法
１、开放定址法
Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1)其中m为表长，di为增量序列
如果di值可能为1,2,3,...m-1，称线性探测再散列。
如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2) 称二次探测再散列。
如果di取值可能为伪随机数列。称伪随机探测再散列。
２、再哈希法
当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。
３、链地址法
将所有关键字为同义词的记录存储在同一线性链表中。
４、建立一个公共溢出区
除基本表外，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。

[color=red][b]哈希表实现[/b][/color]

/*数据项类
 用来表示数据*/
class DataItem {
	int key;
	String value;

	public DataItem() {
	}
	public DataItem(int t, String e) {
		this.key = t;
		this.value = e;
	}
	public int getKey() {
		return this.key;
	}
	public String getValue() {
		return this.value;
	}
}
/*
 * 产生聚集时使用的线性查找
 */
public class HashTableTest {
	private DataItem[] hashArray = null;// 数组
	private int arraySize = 0;// 数组大小
	private int currentSize=0;
	private DataItem nonItem = null;

	/* 哈希表初始化 */
	public HashTableTest(int size) {
		arraySize = size;
		hashArray = new DataItem[size];
	}

	// 输出表
	public void displayTable() {
		for (int i = 0; i < arraySize; i++) {
			if (hashArray[i] != null)
				System.out.print(hashArray[i].getKey() + " ");
			else
				System.out.print("* ");
		}
		System.out.println();
	}

	// 哈希函数,计算哈希码
	private int hashFunction(int key) {
		return key % arraySize;
	}
	private int hashFunctionDouble(int key){
		return 5-key%5;
	}
	// 插入新元素
	public void insert(DataItem item) {
		int key = item.getKey();
		int hashVal = this.hashFunction(key);//计算哈希码
		// int stepSize=this.hashFunctionDouble(key);//重散列
		while (hashArray[hashVal] != null) {

			hashVal++;//线性探测
			hashVal %= arraySize;

			/*hashVal+=stepSize;
			hashVal%=stepSize;*/	//重散列
			if(currentSize>arraySize){
				System.out.println("HashTable已满，插入失败！");
				break;
			}
			currentSize++;
		}
		if(currentSize<=arraySize)hashArray[hashVal] = item;
	}

	// 查找元素
	public DataItem find(int key) {
		int hashVal = this.hashFunction(key);
		while (hashArray[hashVal] != null) {
			if (hashArray[hashVal].getKey() == key)
				return hashArray[hashVal];
			hashVal++;
			hashVal %= arraySize;

			/*hashVal+=stepSize;
			hashVal%=stepSize;*/	//重散列

			if(hashVal==this.hashFunction(key))break;
		}
		System.out.println("查找失败！");
		return null;
	}
	public DataItem delete(int key){
		int hashVal=this.hashFunction(key);
		while(hashArray[hashVal]!=null){
			if(hashArray[hashVal].getKey()==key){
				DataItem item=hashArray[hashVal];
				hashArray[hashVal]=null;
				return item;
			}
			hashVal++;
			hashVal%=arraySize;

			/*hashVal+=stepSize;
			hashVal%=stepSize;*/	//重散列

			if(hashVal==this.hashFunction(key))break;
		}
		return null;
	}
	public static void main(String[] args) {
		int size = 10;
		DataItem item;
		HashTableTest hash = new HashTableTest(size);
		for (int i = 0; i < size; i++) {
			item = new DataItem(i, i + "zzq" + i);
			hash.insert(item);
		}
		hash.displayTable();
		item = new DataItem(11, 11 + "zzq" + 11);
		hash.insert(item);
		hash.displayTable();
		item = hash.find(1);
		System.out.println(item == null);

	}
}