一、你不了解哈希表

1. 什么是哈希表？

• 我们已经知道了一个数据项，关键字映射存储位置。
• 我们查找过程，其实就是比较，不断比较关键字，从而才可以找到存储位置。
• 现在你应该可以发现，他们就像函数一样，X=关键字，Y=存储位置。
• 哈希表的难点就在于找映射关系：f(x) = y
• 称函数为：哈希函数。
• 按这个思想建立的表为哈希表。
• 哈希表的优点：在于它不需要不断比较，而是直接找到，一次就好。
• 黑体字是重点

2. 冲突

• 函数的数学定义有一点：不允许一个X对应多个Y。
• 哈希函数也是函数，所以还剩下一种情况：多个X对应一个Y。
• 所以哈希表要解决的冲突：不同的关键字可能得到同一存储地址。
• 错误可以解决，冲突不能完全避免。我们通常要设定一种处理冲突的方法。

3. 关键名词

• 哈希表：一个关键字对应一个储存位置，形成的表。
• 存储位置 = 哈希地址 = 散列地址
• 函数关系 = 映射关系 = 对应关系 = 哈希构造 = 散列
• H(x) = y

二、你已经知道了哈希表

（一）、哈希函数的构造方法

- 目标：构造好的哈希函数。
- 好的哈希函数：关键字经过哈希函数得到一个“随机的地址”，以便使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突。

1. 直接定址法

$$H(key)=key或H(key)=a\ast key+b$$

2. 数字分析法

$$太灵活了，知道有这种方法就行了$$

3. 平方取中法——重要
$$取关键字平方后的中间几位为哈希地址$$

• 如：
• 

4. 折叠法

$$将关键字分割成相同的几部分（最后一部分的位数可以不同），然后取这几部分叠加和（舍去进位）作为哈希地址$$

• 折叠发适合关键字位数多，且每一位上的数字分布大致均匀。
• 如：
• 

5. 除留余数法——重要

$$H(key)=keyMODp,p<=m$$
$$m为哈希表的表长$$

• 它可以与其他方法一起用。
• p的选择很重要。

（二）、处理冲突的方法

1. 开放定址法——重要

$$Hi=(H(key)+di)MODm$$

• H(key)为哈希函数。
• m为哈希表表长。
• di为增量序列。

1. di = 1, 2, 3, …, m-1 公式被称为线性探测再散列。
2. di = 1^2, -1^2, 2^2, -2^2, …, k^2, -k^2 (k<=m/2) 公式被称为二次探测再散列。
3. di = 伪随机序列 公式被称为随机探测再散列。

• 如：
• 

2. 在哈希法
3. 链地址法
4. 建立一个公共溢出区

三、哈希表的查找的代码

（一）、哈希表的数据结构

// 开放定址哈希表的储存结构
int hashsize[] = {997, ... }; // 哈希表容量递增表，一个合适的素数序列
typedef struct {
	ElemType * elem; // 动态分配数组
	int count; // 当前元素个数
	int sizeindex; // hashsize[sizeindex]为当前容量
}HashTable;

（二）、哈希表的Java代码

• 哈希表的构造：

	/**
	 * 除数取余法，构造哈希表
	 * 
	 * @param keys
	 * @param values
	 * @param hashTableLength 哈希表表长，素数
	 */
	public Search(int[] keys, String[] values, int hashTableLength) {
		length = hashTableLength;
		searchTable = new DataItem[length];
		for (int i = 0; i < length; i++) {
			searchTable[i] = null;
		}

		int tempPosition;
		for (int i = 0; i < keys.length; i++) {
			tempPosition = keys[i] % hashTableLength;

			while (searchTable[tempPosition] != null) {
				tempPosition = (tempPosition + 1) % hashTableLength;
				System.out.println("冲突, 向前移动关键字" + keys[i]);
			}

			searchTable[tempPosition] = new DataItem(keys[i], values[i]);
		}
	}

• 哈希查找：

	/**
	 * 哈希查找
	 * 
	 * @param key
	 * @return
	 */
	public String hashSearch(int key) {
		int tempPosition = key % length;

		while (searchTable[tempPosition] != null) {
			if (searchTable[tempPosition].key == key) {
				return searchTable[tempPosition].value;
			}
			tempPosition = (tempPosition + 1) % length;
		}

		return null;
	} // hashSearch

• 测试函数：

	public static void main(String[] args) {
		int[] key = { 1, 3, 5, 6, 7, 9, 10 };
		String[] values = { "if", "then", "else", "switch", "case", "for", "while" };
	
		Search search = new Search(key, values, 13);

		System.out.println(search.toString());
		System.out.println("Search result of 10 is: " + search.hashSearch(10));
	}

（三）、输出样例

• Search类源码：

package search;

public class Search {

	/** 查找表 */
	DataItem[] searchTable;

	/** 表长度 */
	int length;

	class DataItem {

		/** 关键字域 */
		int key;

		/** 其他域 */
		String value;

		DataItem(int key, String value) {
			this.key = key;
			this.value = value;
		}

		public String toString() {
			return "[" + key + ", " + value + "]";
		}
	} // 数据项

	/**
	 * 构造查找表
	 * 
	 * @param keys
	 * @param values
	 */
	public Search(int[] keys, String[] values) {
		// TODO
		if (keys.length != values.length) {
			throw new RuntimeException("键 与 值不对应!");
		}
		length = keys.length;
		searchTable = new DataItem[length];

		for (int i = 0; i < length; i++) {
			searchTable[i] = new DataItem(keys[i], values[i]);
		}
	} // structure

	/**
	 * 除数取余法，构造哈希表
	 * 
	 * @param keys
	 * @param values
	 * @param hashTableLength 哈希表表长，素数
	 */
	public Search(int[] keys, String[] values, int hashTableLength) {
		length = hashTableLength;
		searchTable = new DataItem[length];
		for (int i = 0; i < length; i++) {
			searchTable[i] = null;
		}

		int tempPosition;
		for (int i = 0; i < keys.length; i++) {
			tempPosition = keys[i] % hashTableLength;

			while (searchTable[tempPosition] != null) {
				tempPosition = (tempPosition + 1) % hashTableLength;
				System.out.println("冲突, 向前移动关键字" + keys[i]);
			}

			searchTable[tempPosition] = new DataItem(keys[i], values[i]);
		}
	}

	/**
	 * 打印查找表
	 */
	public String toString() {
		String resultString = "I am a search table with " + length + " data items.\r\n";
		for (int i = 0; i < length; i++) {
			resultString += searchTable[i] + " ";
		}
		return resultString;
	}// toString

	/**
	 * 顺序查找
	 * 
	 * @param key
	 * @return key相对应的值
	 */
	public String sequentialSearch(int key) {
		// TODO
		searchTable[0].key = key; // "哨兵"
		int i;
		for (i = length - 1; searchTable[i].key != key; i--)
			;
		return searchTable[i].value;
	} // sequentialSearch

	/**
	 * 折半查找
	 * 
	 * @param key
	 * @return
	 */
	public String binarySearch(int key) {
		// TODO
		int low = 0;
		int high = length - 1;
		int mid = (low + high) / 2;

		while (low <= high) {
			mid = (low + high) / 2;
			if (searchTable[mid].key == key) {
				return searchTable[mid].value;
			} else if (searchTable[mid].key < key) {
				low = mid + 1;
			} else {
				high = mid - 1;
			}
		} // Of while

		return null;
	}// binarySearch

	/**
	 * 哈希查找
	 * 
	 * @param key
	 * @return
	 */
	public String hashSearch(int key) {
		int tempPosition = key % length;

		while (searchTable[tempPosition] != null) {
			if (searchTable[tempPosition].key == key) {
				return searchTable[tempPosition].value;
			}
			tempPosition = (tempPosition + 1) % length;
		}

		return null;
	} // hashSearch

	public static void main(String[] args) {
		// TODO
		System.out.println("\r\n-------sequentialSearchTest-------");
		// 1 声明
		int[] keys1 = { -1, 5, 3, 6, 10, 7, 1, 9 };
		String[] values1 = { "null", "if", "then", "else", "switch", "case", "for", "while" };
		// 2 对象
		Search search1 = new Search(keys1, values1);
		// 3 打印
		System.out.println(search1.toString());
		// 4 测试
		long startTime1 = System.nanoTime(); // 获取开始时间
		System.out.println("Search result of 10 is: " + search1.sequentialSearch(10));
		long endTime1 = System.nanoTime(); // 获取结束时间
		System.out.println("查找时间（纳秒）: " + (endTime1 - startTime1));

		System.out.println("\r\n-------binarySearchTest-------");
		// 1 声明
		int[] keys2 = { 1, 3, 5, 6, 7, 9, 10 };
		String[] values2 = { "if", "then", "else", "switch", "case", "for", "while" };
		// 2 对象
		Search search2 = new Search(keys2, values2);
		// 3 打印
		System.out.println(search2.toString());
		// 4 测试
		long startTime2 = System.nanoTime(); // 获取开始时间
		System.out.println("Search result of 10 is: " + search2.binarySearch(10));
		long end2Time2 = System.nanoTime(); // 获取结束时间
		System.out.println("查找时间（纳秒）: " + (end2Time2 - startTime2));

		System.out.println("\r\n-------hashSearchTest-------");
		// 1 声明
		int[] key3 = { 1, 3, 5, 6, 7, 9, 10 };
		String[] values3 = { "if", "then", "else", "switch", "case", "for", "while" };
		// 2 对象
		Search search3 = new Search(key3, values3, 13);
		// 3 打印
		System.out.println(search3.toString());
		// 4 测试
		long startTime3 = System.nanoTime(); // 获取开始时间
		System.out.println("Search result of 10 is: " + search3.hashSearch(10));
		long endTime3 = System.nanoTime(); // 获取结束时间
		System.out.println("查找时间（纳秒）: " + (endTime3 - startTime3));
	}

} // Search

• 输出：