java分离链式法实现 HashTable的代码

如下的资料是关于java分离链式法实现 HashTable的代码。

protected Entry(int hash, K key, V value, Entry<K,V> next) {

    this.hash = hash;

    this.key = key;

    this.value = value;

    this.next = next;

}

而下面程序使用了LinkedList，使代码更简单更清晰易懂。

package changsheng.algorithms.hash;

import java.util.LinkedList;

public class SeparateChainingHashTable<T> {

public SeparateChainingHashTable() {

this(DEFAULT_TABLE_SIZE);

}

@SuppressWarnings("unchecked")

public SeparateChainingHashTable(int size) {

theLists = (LinkedList<T>[]) new LinkedList[nextPrime(size)];

for (int i = 0; i < theLists.length; i++)

theLists[i] = new LinkedList<T>();

}

public void insert(T x) {

LinkedList<T> whichList = theLists[x.hashCode() % theLists.length];

if (!whichList.contains(x)) {

whichList.addFirst(x);

}

}

public boolean remove(T x) {

return theLists[x.hashCode() % theLists.length].remove(x);

}

public boolean find(T x) {

return theLists[x.hashCode() % theLists.length].contains(x);

}

public void makeEmpty() {

for (int i = 0; i < theLists.length; i++)

theLists[i].clear();

}

private static final int DEFAULT_TABLE_SIZE = 101;

private LinkedList<T>[] theLists;

private static int nextPrime(int n) {

if (n % 2 == 0)

n++;

for (; !isPrime(n); n += 2)

;

return n;

}

private static boolean isPrime(int n) {

if (n == 2 || n == 3)

return true;

if (n == 1 || n % 2 == 0)

return false;

if (n % i == 0)

return false;

return true;

}

public static void main(String[] args) {

SeparateChainingHashTable<Integer> H = new SeparateChainingHashTable<Integer>();

final int NUMS = 4000;

final int GAP = 37;

System.out.println("Checking... (no more output means success)");

for (int i = GAP; i != 0; i = (i + GAP) % NUMS)

H.insert(new Integer(i));

for (int i = 1; i < NUMS; i += 2)

H.remove(new Integer(i));

for (int i = 2; i < NUMS; i += 2)

if (!H.find(new Integer(i)))

System.out.println("Find fails " + i);

for (int i = 1; i < NUMS; i += 2) {

if (H.find(new Integer(i)))

System.out.println("OOPS!!! " + i);

}

}

}