编写一个布谷鸟散列表（Java语言描述）
编写接口IHashTable
作者：进阶的JFarmer
public interface IHashTable {
int hash(T x, int which);
int getNumberOfFunctions();
void generateNewFunctions();
}
实现StringIHashTable类
该类实现了IHashTable，T具体化为java.lang.String。
import java.util.Random;
public class StringHashTable implements IHashTable {
private final int [] MULTIPLIERS;
private final Random r = new Random();
public StringHashTable(int d) {
MULTIPLIERS = new int [d];
generateNewFunctions();
}
public int getNumberOfFunctions() {
return MULTIPLIERS.length;
}
public void generateNewFunctions() {
for(int i = 0; i < MULTIPLIERS.length; i++) {
MULTIPLIERS[i] = r.nextInt();
}
}
public int hash(String x, int which) {
final int multiplier = MULTIPLIERS[which];
int hashVal = 0;
for(int i = 0; i < x.length( ); i++) {
hashVal = multiplier * hashVal + x.charAt(i);
}
return hashVal;
}
}
CuckooHashTable核心功能设计
boolean insert(x) → Insert x.
boolean remove(x) → Remove x.
boolean contains(x) → Return true if x is present.
void makeEmpty() → Remove all items.
int size() → Return number of items.
CuckooHashTable编程实现
import java.util.Arrays;
import java.util.Random;
/**
* Cuckoo hash table implementation of hash tables.
* CONSTRUCTION: a hashing function family and an approximate initial size or default of 101.
*/
public class CuckooHashTable {
/**
* Construct the hash table.
* @param hf the hash family
*/
public CuckooHashTable(IHashTable hf) {
this(hf, DEFAULT_TABLE_SIZE);
}
/**
* Construct the hash table.
* @param hf the hash family
* @param size the approximate initial size.
*/
public CuckooHashTable(IHashTable hf, int size) {
allocateArray( nextPrime( size ) );
doClear( );
hashFunctions = hf;
numHashFunctions = hf.getNumberOfFunctions( );
}
private Random r = new Random();
private static final double MAX_LOAD = 0.40;
private static final int ALLOWED_REHASHES = 1;
private int rehashes = 0;
private boolean insertHelper1(T x) {
final int COUNT_LIMIT = 100;
while(true) {
int lastPos = -1;
int pos;
for(int count = 0; count < COUNT_LIMIT; count++) {
for(int i = 0; i < numHashFunctions; i++) {
pos = myhash(x, i);
if(array[pos] == null) {
array[pos] = x;
currentSize++;
return true;
}
}
// none of the spots are available. Kick out a random one
int i = 0;
do {
pos = myhash(x, r.nextInt(numHashFunctions));
} while(pos == lastPos && i++ ALLOWED_REHASHES) {
expand(); // Make the table bigger
rehashes = 0;
} else {
rehash();
}
}
}
private boolean insertHelper2(T x) {
final int COUNT_LIMIT = 100;
while( true ) {
for(int count = 0; count ALLOWED_REHASHES) {
expand(); // Make the table bigger
rehashes = 0;
} else {
rehash();
}
}
}
/**
* Insert into the hash table. If the item is
* already present, return false.
* @param x the item to insert.
*/
public boolean insert(T x) {
if(contains(x)) {
return false;
}
if(currentSize >= array.length * MAX_LOAD) {
expand();
}
return insertHelper1(x);
}
private int myhash(T x, int which) {
int hashVal = hashFunctions.hash(x, which);
hashVal %= array.length;
if(hashVal < 0) {
hashVal += array.length;
}
return hashVal;
}
private void expand( ) {
rehash((int)(array.length / MAX_LOAD));
}
private void rehash( ) {
//System.out.println( "NEW HASH FUNCTIONS " + array.length );
hashFunctions.generateNewFunctions( );
rehash( array.length );
}
private void rehash( int newLength ) {
//System.out.println( "REHASH: " + array.length + " " + newLength + " " + currentSize );
T[] oldArray = array; // Create a new double-sized, empty table
allocateArray(nextPrime(newLength));
currentSize = 0;
// Copy table over
for(T str : oldArray) {
if( str != null ) {
insert( str );
}
}
}
/**
* Gets the size of the table.
* @return number of items in the hash table.
*/
public int size() {
return currentSize;
}
/**
* Gets the length (potential capacity) of the table.
* @return length of the internal array in the hash table.
*/
public int capacity() {
return array.length;
}
/**
* Method that searches all hash function places.
* @param x the item to search for.
* @return the position where the search terminates, or -1 if not found.
*/
private int findPos(T x) {
for(int i = 0; i < numHashFunctions; i++) {
int pos = myhash( x, i );
if(array[pos] != null && array[pos].equals(x)) {
return pos;
}
}
return -1;
}
/**
* Remove from the hash table.
* @param x the item to remove.
* @return true if item was found and removed
*/
public boolean remove(T x) {
int pos = findPos(x);
if(pos != -1) {
array[pos] = null;
currentSize--;
}
return pos != -1;
}
/**
* Find an item in the hash table.
* @param x the item to search for.
* @return the matching item.
*/
public boolean contains(T x) {
return findPos(x) != -1;
}
/**
* Make the hash table logically empty.
*/
public void makeEmpty() {
doClear();
}
private void doClear() {
currentSize = 0;
Arrays.fill(array, null);
}
private static final int DEFAULT_TABLE_SIZE = 101;
private final IHashTable hashFunctions;
private final int numHashFunctions;
private T[ ] array; // The array of elements
private int currentSize; // The number of occupied cells
/**
* Internal method to allocate array.
* @param arraySize the size of the array.
*/
@SuppressWarnings("unchecked")
private void allocateArray(int arraySize) {
array = (T[]) new Object[arraySize];
}
/**
* Internal method to find a prime number at least as large as n.
* @param n the starting number (must be positive).
* @return a prime number larger than or equal to n.
*/
protected static int nextPrime(int n) {
if(n % 2 == 0) {
n++;
}
for(; !isPrime(n); n += 2) {}
return n;
}
/**
* Internal method to test if a number is prime.
* Not an efficient algorithm.
* @param n the number to test.
* @return the result of the test.
*/
private static boolean isPrime(int n) {
if(n == 2 || n == 3) {
return true;
}
if(n == 1 || n % 2 == 0) {
return false;
}
for(int i = 3; i * i <= n; i += 2) {
if(n % i == 0) {
return false;
}
}
return true;
}
}
测试
public class Test {
public static void main( String [ ] args ) {
long cumulative = 0;
final int NUMS = 2000000;
final int GAP = 37;
final int ATTEMPTS = 10;
System.out.println("Checking... (no more output means success)");
for(int att = 0; att < ATTEMPTS; att++) {
System.out.println("ATTEMPT: " + att);
CuckooHashTable H = new CuckooHashTable(new StringHashTable(3));
long startTime = System.currentTimeMillis();
for(int i = GAP; i != 0; i = (i + GAP) % NUMS) {
H.insert(""+i);
}
for(int i = GAP; i != 0; i = (i + GAP) % NUMS) {
if( H.insert(""+i)) {
System.out.println( "OOPS!!! " + i );
}
}
for(int i = 1; i < NUMS; i+= 2) {
H.remove(""+i);
}
for(int i = 2; i < NUMS; i+=2) {
if(!H.contains(""+i)) {
System.out.println("Find fails " + i);
}
}
for(int i = 1; i NUMS * 4) {
System.out.println("LARGE CAPACITY " + H.capacity());
}
}
System.out.println("Total elapsed time is: " + cumulative);
}
}
测试结果：
Checking... (no more output means success)
ATTEMPT: 0
ATTEMPT: 1
ATTEMPT: 2
ATTEMPT: 3
ATTEMPT: 4
ATTEMPT: 5
ATTEMPT: 6
ATTEMPT: 7
ATTEMPT: 8
ATTEMPT: 9
Total elapsed time is: 21851
作者：进阶的JFarmer
