自己实现的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 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;
	}

}

评论

10 楼 yegaofei 2010-04-01  

借楼主的帖子问个问题：

当我们遍历Hashtable的key集合时，常用Enumeration的nextElement()方法,我看了下jdk的代码，nextElement()方法是以从后往前的顺序遍历的，而且注释写的是为了更快速的遍历。

我想问一下，为什么从后往前的速度会比较快？

9 楼 asialee 2010-03-07  

captmjc 写道

另外，对于checkPrime，建议lz google "prime sieve"，并以此为基础，实现准备好前N个Prime (http://primes.utm.edu/lists/small/1000.txt，10000.txt ...)以加快速度

非常感谢

8 楼 captmjc 2010-03-07  

asialee 写道

robertliudeqiang 写道

楼上说的对，你这个实现的类似HashSet。在JDK里，HashSet是基于HashMap实现的。

对程序的个人观点：
1 你使用的是“开放寻址法”，个人觉得没有JDK里面HashMap用的bucket的结构有效率，主要原因是当loadFactor比较高的时候冲突会比较多。
2  private boolean checkPrime(int n)
可能有时候并不需要真的找一个素数，特别是当n很大的时候，只需要找一个可能的大素数就行了，应该有相应算法。

非常感谢，看来我真的有修改了，应该叫做HashSet，还有，我没有去看JDK里面的HashSet的实现，对它检测冲突的方法也不是很了解，建议给我扫盲一下。

HashSet其实利用了HashMap

7 楼 captmjc 2010-03-07  

另外，对于checkPrime，建议lz google "prime sieve"，并以此为基础，实现准备好前N个Prime (http://primes.utm.edu/lists/small/1000.txt，10000.txt ...)以加快速度

6 楼 asialee 2010-03-06  

robertliudeqiang 写道

楼上说的对，你这个实现的类似HashSet。在JDK里，HashSet是基于HashMap实现的。

对程序的个人观点：
1 你使用的是“开放寻址法”，个人觉得没有JDK里面HashMap用的bucket的结构有效率，主要原因是当loadFactor比较高的时候冲突会比较多。
2  private boolean checkPrime(int n)
可能有时候并不需要真的找一个素数，特别是当n很大的时候，只需要找一个可能的大素数就行了，应该有相应算法。

非常感谢，看来我真的有修改了，应该叫做HashSet，还有，我没有去看JDK里面的HashSet的实现，对它检测冲突的方法也不是很了解，建议给我扫盲一下。

5 楼 robertliudeqiang 2010-03-06  

楼上说的对，你这个实现的类似HashSet。在JDK里，HashSet是基于HashMap实现的。

对程序的个人观点：
1 你使用的是“开放寻址法”，个人觉得没有JDK里面HashMap用的bucket的结构有效率，主要原因是当loadFactor比较高的时候冲突会比较多。
2  private boolean checkPrime(int n)
可能有时候并不需要真的找一个素数，特别是当n很大的时候，只需要找一个可能的大素数就行了，应该有相应算法。

4 楼 captmjc 2010-03-06  

1， 你说你这个只支出String的，Object[]或者泛型不就可以了
2， 这个貌似实现的是HashSet的类似功能，而不是HashTable的键值对

3 楼 asialee 2010-03-06  

另外，现在这个只是支持String，我主要是想看看冲突检测和解决的。

2 楼 asialee 2010-03-06  

robertliudeqiang 写道

asialee 写道

[size=medium]
/**
* 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);
}

如果是实现HashTable, ms方法应该是:

public boolean insert(String key, String value);

这个是这样的，JDK的HashTable是用的key的hash值查找的，它里面存储的是Entry，我是直接根据要插入的值生成Hash值的， 实际上查找的时候是直接查找值的。

1 楼 robertliudeqiang 2010-03-06  

asialee 写道

[size=medium]
/**
* 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);
}

如果是实现HashTable, ms方法应该是:

public boolean insert(String key, String value);