自己实现的HashTable
自己实现的HashTable，主要是学习一下Hash的冲突检测以及冲突解决方式，没有详细的测试，希望大家多多指教。
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 overflowif (probe_counter > hash_mid) {return false;}String tmp = strArray[hash_key];// Empty slotif (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/2if (probe_counter > hash_mid) {return false;}String tmp = elements[hash_key];// Record empty for the keyif (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;}} 1 楼 robertliudeqiang 2010-03-06 asialee 写道[size=medium]