哈希值查询网址

散列的思想其实就是建立一个映射，元素关键字k和元素存储位置p之间的一个映射H，使得p = H(k)，这个函数就叫做散列函数。

哈希函数的构造方法有很多种：

数值分析：

从关键字中选择一个相对均匀分布的位数组成一个哈希地址，但这种情况一般适用于一组可以预先知道的关键字交易哈希值查项目地址，并且每个关键字的位数高于哈希表的地址码。当有很多数字时

平方的中文方法：

使用关键字平方值的中间位作为存储地址，适用于关键字中的每一位都有某些数字频繁出现的现象

分段堆叠方式：

将关键字分成相等的部分和部分，然后将这些部分相加，最高进位后的结果作为哈希地址被丢弃。如果关键字的位数特别多，这很有用

余法：

假设哈希表的长度为m，p为不大于m的素数，则哈希函数为：H(k) = k %p。

伪随机数法：

使用伪随机数作为哈希函数：H(K) = random(K);适用于关键字长度不等且分布不均的情况。

在构造哈希函数的过程中，不可避免地会出现以下几种情况：

要散列的元素（18,75,60,42,54）取p=7，用余法构造时：H(18） = 18 %7 = 4; H(75）=75%7=5;H(60）=60%7=4......

这样，元素 18 和 60 的哈希地址发生冲突。为了解决这个问题，通常有三种方式：

开放寻址方式：

即当关键字key的哈希地址p=H(key)发生冲突时，基于p生成另一个哈希地址p1，如果p1仍然发生冲突，则基于p生成另一个哈希地址p1。哈希地址p2...直到找到一个不冲突的哈希地址pi，并在其中存储对应的元素。

重新散列：

构造若干个哈希函数交易哈希值查项目地址，当发生冲突时，根据另一个哈希函数计算下一个哈希地址，直到不再发生冲突。即：Hi=Rhi(key) i=1,2,...k，其中：Rhi——不同的hash函数，这种方法不易产生聚合，但增加了计算时间。

链地址方式：

将所有具有相同哈希地址的关键字存储在同一个链表中。

以下是使用余数法和开地址法进行哈希查找的JAVA代码：

import java.util.Arrays;
import java.util.Random;
public class HashSearch {
	static int m; // 哈希表长
	static int hashTable[]; // 哈希表
	public static void main(String[] args) {
		int a[] = new int[100000];
		for (int i = 0; i < a.length; i++) {
			a[i] = i * 2;
		}// 初始化数组，数组中全是偶数
		int key = new Random(System.currentTimeMillis()).nextInt(200000);
		// 随机产生要查找的关键字
		for (int i = a.length;; i++) {
			if (isSushu(i)) {
				m = i;
				break;
			}
		}// 根据数组大小确定哈希表长
		hashTable = new int[m];
		Arrays.fill(hashTable, -1);// 将哈希表全部初始化为-1
		System.out.println(key + "  " + hashSearch(a, key));
	}
	public static boolean hashSearch(int a[], int key) {// 哈希查找
		ConstructHash(a);// 根据数组构造出哈希表
		int position = key % m;
		if (hashTable[position] == -1) {
			return false;
		} else if (hashTable[position] == key) {
			return true;
		} else {// 用线性探测再散列解决冲突
			for (int i = 1; i < m; i++) {
				int pi = (position + i) % m;
				if (hashTable[pi] == -1) {
					return false;
				} else if (hashTable[pi] == key) {
					return true;
				}
			}
			return false;
		}
	}
	public static void ConstructHash(int a[]) {// 构造哈希表
		for (int i = 0; i < a.length; i++) {
			int pi = Hash(a[i]);
			if (hashTable[pi] == -1) {
				hashTable[pi] = a[i];
			} else {// 用线性探测再散列解决冲突
				for (int j = 1; j < m; j++) {
					int position = (pi + j) % m;
					if (hashTable[position] == -1) {
						hashTable[position] = a[i];
						j = m;//中断内循环
					}
				}
			}
		}
	}
	public static int Hash(int n) {// 除留余数法构造哈希函数
		return n % m;
	}
	public static boolean isSushu(int i) {// 将哈希表长定为素数
		int k = (int) Math.sqrt((double) i);
		for (int j = 2; i <= k; j++) {
			if (i % j == 0) {
				return false;
			}
		}
		return true;
	}
}