首页 > 程序开发 > 软件开发 > Java >

HashTable实现--分离链式法

2012-12-03

[java]package changsheng.algorithms.hash;import java.util.LinkedList;public class SeparateChainingHashTable<T> { /** * Construct the hash table. */ public SeparateChainingHashTable()...

[java]
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.
*/ www.2cto.com
@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);
}
}

}
相关文章
最新文章
热点推荐