java分离链式法实现 HashTable

java分离链式法实现 HashTable

JDK中的相应Hashtable中并没有使用LinkedList，而是使用自封装的Entry，显得使其更紧凑，且没有冗余。

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> {
	/**
	 * Construct the hash table.
	 */
	public SeparateChainingHashTable() {
		this(DEFAULT_TABLE_SIZE);
	}
	/**
	 * Construct the hash table.
	 * 
	 * @param size
	 *            approximate 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>();
	}
	/**
	 * Insert into the hash table. If the item is already present, then do
	 * nothing.
	 * 
	 * @param x
	 *            the item to insert.
	 */
	public void insert(T x) {
		LinkedList<T> whichList = theLists[x.hashCode() % theLists.length];
		if (!whichList.contains(x)) {
			whichList.addFirst(x);
		}
	}
	/**
	 * Remove from the hash table.
	 * 
	 * @param x
	 *            the item to remove.
	 */
	public boolean remove(T x) {
		return theLists[x.hashCode() % theLists.length].remove(x);
	}
	/**
	 * Find an item in the hash table.
	 * 
	 * @param x
	 *            the item to search for.
	 * @return the matching item, or null if not found.
	 */
	public boolean find(T x) {
		return theLists[x.hashCode() % theLists.length].contains(x);
	}
	/**
	 * Make the hash table logically empty.
	 */
	public void makeEmpty() {
		for (int i = 0; i < theLists.length; i++)
			theLists[i].clear();
	}
	private static final int DEFAULT_TABLE_SIZE = 101;
	/** The array of Lists. */
	private LinkedList<T>[] theLists;
	/**
	 * 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.
	 */
	private 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;
	}
	// Simple main
	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);
		}
	}
}