分离链接散列算法的缺点是使用一些链表。由于给新单元分配地址需要时间，因此这就导致算法的速度有些减慢，同时算法实际上还要求对第二种数据结构的实现。另有一种不用链表解决冲突的方法是尝试另外一些单元，直到找出空的单元为止。更常见的是，单元h0(x),h1(x),h2(x),...相继被试选，其中hi(x)=(hash(x)+f(i)) mod TableSize，且f(0)=0。函数f是冲突解决方法，因为所有的数据都要置于表内，所以这种解决方案所需要的表要比分离链接散列的表大。一般来说，对于不使用分离链接的散列表来说，其装填因子λ应该低于 0.5。我们把这样的表叫做探测散列表(probing hash table)。现在我们就来考察三中通常的冲突解决方案。
import java.util.Random;
public class QuadraticProbingHashTable<AnyType> {
private static final int DEFAULT_TBALE_SIZE = 11;
private HashEntry<AnyType>[] array;
private int currentSize;
/*
* 三种情况：null，非null且该项为活动的，非null且该项被标记删除
*/
private static class HashEntry<AnyType> {
public AnyType element;
public boolean isActive;
public HashEntry(AnyType e) {
this(e, true);
}
public HashEntry(AnyType e, boolean i) {
element = e;
isActive = i;
}
}
public QuadraticProbingHashTable() {
this(DEFAULT_TBALE_SIZE);
}
public QuadraticProbingHashTable(int size) {
array = new HashEntry[size];
makeEmpty();
}
public void makeEmpty() {
for (int i = 0; i < array.length; i++) {
array[i] = null;
}
currentSize = 0;
}
/**
* 哈希表是否包含某元素
*
* @param x
* 查询元素
* @return 查询结果
*/
public boolean contains(AnyType x) {
int currentPos = findPos(x);
return isActive(currentPos);
}
/**
* 向哈希表中插入某元素，若存在则不操作
*
* @param x
* 插入元素
*/
public void insert(AnyType x) {
int currentPos = findPos(x);
System.out.println(x + " hash-> " + currentPos);
if (isActive(currentPos)) {
return;
}
array[currentPos] = new HashEntry<AnyType>(x, true);
if (++currentSize > array.length / 2) {
rehash();
}
}
/**
* 向哈希表中懒惰删除某元素
*
* @param x
* 删除元素
*/
public void remove(AnyType x) {
int currentPos = findPos(x);
if (isActive(currentPos)) {
array[currentPos].isActive = false;
}
}
/**
* 通过哈希算法找到某元素下标（平方探测法）：f(i)=f(i-1)+2i-1
*
* @param x
* 查找元素
* @return 该元素在数组中下标
*/
private int findPos(AnyType x) {
int offset = 1;
int currentPos = myhash(x);
while (array[currentPos] != null
&& !array[currentPos].element.equals(x)) {
currentPos += offset;
offset += 2;
if (currentPos >= array.length) {
currentPos -= array.length;
}
}
return currentPos;
}
/**
* 检查指定下标是否存在活动项
*
* @param currentPos
* 下标
* @return 是否有活动项
*/
private boolean isActive(int currentPos) {
return array[currentPos] != null && array[currentPos].isActive;
}
/**
* 简单的哈希算法
*
* @param x
* 元素
* @return 哈希值
*/
private int myhash(AnyType x) {
int hashVal = x.hashCode();
hashVal %= array.length;
if (hashVal < 0) {
hashVal += array.length;
}
return hashVal;
}
/**
* 再散列函数，插入空间过半时执行
*/
@SuppressWarnings("unchecked")
private void rehash() {
HashEntry<AnyType>[] oldArray = array;
// 创建一个容量翻倍的空表
array = new HashEntry[nextPrime(2 * array.length)];
currentSize = 0;
// 将数据复制到新表
for (int i = 0; i < oldArray.length; i++) {
if (oldArray[i] != null && oldArray[i].isActive) {
insert(oldArray[i].element);
}
}
System.out.println("\nrehash by length of: " + array.length);
}
/**
* 检查某整数是否为素数
*
* @param num
* 检查整数
* @return 检查结果
*/
private static boolean isPrime(int num) {
if (num == 2 || num == 3) {
return true;
}
if (num == 1 || num % 2 == 0) {
return false;
}
for (int i = 3; i * i <= num; i += 2) {
if (num % i == 0) {
return false;
}
}
return true;
}
/**
* 返回不小于某个整数的素数
*
* @param num
* 整数
* @return 下一个素数（可以相等）
*/
private static int nextPrime(int num) {
if (num == 0 || num == 1 || num == 2) {
return 2;
}
if (num % 2 == 0) {
num++;
}
while (!isPrime(num)) {
num += 2;
}
return num;
}
public void printTable() {
for (int i = 0; i < array.length; i++) {
System.out.println("-----");
if (array[i] != null) {
System.out.println(array[i].element + " ");
} else {
System.out.println();
}
}
}
public static void main(String[] args) {
QuadraticProbingHashTable<Integer> hashTable = new QuadraticProbingHashTable<Integer>();
Random random = new Random();
for (int i = 0; i < 20; i++) {
hashTable.insert(random.nextInt(60));
}
hashTable.printTable();
}
}
版权声明：本文为博主原创文章，未经博主允许不得转载。
数据结构（Java语言）——HashTable（开放定址法）简单实现
原文：http://blog.csdn.net/zhang_zp2014/article/details/48029547