自己实现的HashTable

import java.util.Locale;

/**
 * Implement a hash table to store strings (i.e. objects of the Java String
 * class)
 *
 * @author LiYazhou
 * @version 1.0
 */
public class HashTable {
	/**
	 * The initialize size of this hash table.
	 */
	private final static int INITIAL_SIZE = 50;

	/**
	 * The internal array to hold the elements
	 */
	private String[] elements;

	/**
	 * The real number of this hast table
	 */
	private int capacity;

	/**
	 * The no argument constructor to initialize the HashTable to size 101
	 */
	public HashTable() {
		this(INITIAL_SIZE);
	}

	/**
	 * Creates a hash table to store n items, the size of the underlying array
	 * should be a prime number, roughly 2 * n
	 *
	 * @param n
	 */
	public HashTable(int n) {
		int size = 2 * n;
		elements = new String[getNearestPrime(size)];
	}

	/**
	 * Inserts the parameter into the hash table, return true if the parameter
	 * was inserted
	 *
	 * @param value
	 *            The value to be inserted.
	 * @return Whether or not the value to be inserted.
	 */
	public boolean insert(String value) {
		if (loadFactor() >= 0.75) {
			reHash();
		}
		return insert(elements, value);
	}

	/**
	 * Inserts the parameter into the hash table, return true if the parameter
	 * was inserted
	 *
	 * @param strArray
	 *            To insert the value to the strArray array
	 * @param value
	 *            The value to be inserted.
	 * @return Whether or not the value to be inserted.
	 */
	private boolean insert(String[] strArray, String value) {
		int hash_key = hash(value, strArray.length);
		int increment = 1;

		int probe_counter = 0;
		int hash_mid = (strArray.length + 1) / 2;

		while (true) {
			// Check for overflow
			if (probe_counter > hash_mid) {
				return false;
			}
			String tmp = strArray[hash_key];
			// Empty slot
			if (tmp == null) {
				break;
				// Position already taken, duplicate keys are not allowed
			} else if (tmp.equals(value)) {
				return false;
				// Handles collision using h+i^2
			} else {
				hash_key = (hash_key + increment) % strArray.length;
				increment += 2;
				probe_counter++;
			}
		}
		strArray[hash_key] = value;
		capacity++;
		return true;
	}

	/**
	 * return true if the given string is in the table, false otherwise
	 *
	 * @param str
	 *            The value to be checked in this hash table
	 * @return Whether or not the value is in this hash table.
	 */
	public boolean lookUp(String str) {
		int hash_key = hash(str, elements.length);
		int increment = 1;

		int probe_counter = 0;
		int hash_mid = (elements.length + 1) / 2;

		while (true) {
			// Overflow encountered if the probe is bigger than hash_size/2
			if (probe_counter > hash_mid) {
				return false;
			}
			String tmp = elements[hash_key];
			// Record empty for the key
			if (tmp == null) {
				break;
			} else if (tmp.equals(str)) {
				return true;
			} else {
				hash_key = (hash_key + increment) % elements.length;
				increment += 2;
				probe_counter++;
			}
		}
		return false;
	}

	/**
	 * Returns the size of the hash table (the size of the underlying array)
	 *
	 * @return The size of the hash table
	 */
	public int length() {
		return elements.length;
	}

	/**
	 * Returns the number of strings currently stored in the hash table
	 *
	 * @return The number of strings currently stored in the hash table
	 */
	public int getNum() {
		return capacity;
	}

	/**
	 * The current load factor of this hash table.
	 *
	 * @return The current load factor of this hash table.
	 */
	private float loadFactor() {
		return (float) capacity / elements.length;
	}

	/**
	 * This method is to get the next nearest prime number after size
	 *
	 * @param size
	 *            The base which you want to find
	 * @return The next nearest prime number after size
	 */
	private int getNearestPrime(int size) {
		boolean isPrime = checkPrime(size);
		while (!isPrime) {
			size++;
			isPrime = checkPrime(size);
		}
		return size;
	}

	/**
	 * This is the hash function to return a hash code according to the key
	 *
	 * @param word
	 *            The key which you want to generate the hash code
	 * @param size
	 *            The size of current array's size
	 * @return The hash code for the give word
	 */
	private int hash(String word, int size) {
		word = word.toLowerCase(Locale.ENGLISH);
		int hashValue = 0;
		for (int i = 0; i < word.length(); i++) {
			hashValue = ((hashValue * 32) + (word.charAt(i) - 'a')) % size;
		}

		if(hashValue < 0){
			hashValue = hashValue + size;
		}
		return hashValue;
	}

	/**
	 * This method is to implement the rehash function when the load factor is
	 * greater than the initial load factor.
	 */
	private void reHash() {
		capacity = 0;
		String[] newArray = new String[getNearestPrime(2 * elements.length)];
		for (int i = 0; i < elements.length; i++) {
			if (elements[i] != null) {
				insert(newArray, elements[i]);
			}
		}
		elements = newArray;
	}

	/**
	 * This method is to check whether this number is a prime value or not
	 *
	 * @param n
	 *            The value which you want to check whether it is a prime value
	 * @return Whether the given value is a prime value.
	 */
	private boolean checkPrime(int n) {
		if (n < 1) {
			return false;
		}
		if (n % 2 == 0) {
			return false;
		}
		for (int i = 3; i * i <= n; i += 2) {
			if (n % i == 0) {
				return false;
			}
		}
		return true;
	}

}