`

自己实现的HashTable

    博客分类:
  • java
阅读更多

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

相关推荐

    HashTable的java实现

    在Java中,除了`HashTable`,还有其他实现,如`HashMap`,它在单线程环境下提供了更好的性能,而`ConcurrentHashMap`则在多线程环境下提供高性能且线程安全的解决方案。学习和掌握这些不同的实现方式可以帮助开发者...

    哈希表hashtable实现

    在本篇文章中,我们将深入探讨哈希表的实现,特别是基于C语言的简单实现,参考文件"hashtable.c"和"hashtable.h"。 1. 哈希函数:哈希表的核心是哈希函数,它将输入(键或关键字)转换为数组索引。一个好的哈希函数...

    c语言实现hashtable,一键多值

    c语言实现hashtable,一个key可以对应多个data,c语言实现

    利用C语言实现HashTable

    HashTable是在实际应用中很重要的一个结构,下面讨论一个简单的实现,虽然简单,但是该有的部分都还是有的。 一,访问接口 创建一个hashtable. hashtable hashtable_new(int size) /其中size表示包含的接点个数。...

    HashTable

    《深入解析HashTable:C语言实现的精髓》 在计算机科学中,哈希表(HashTable)是一种数据结构,它实现了关联数组的抽象数据类型,能够快速地进行查找、插入和删除操作。哈希表通过将键(Key)映射到表中的一个位置...

    hashtable购物车Session+Hashtable实现

    ### 基于Hashtable与Session实现的购物车系统 #### 一、引言 随着互联网技术的发展,电子商务网站成为人们日常购物的重要渠道之一。在众多电商功能中,“购物车”作为一个核心组件,允许用户暂时存储选购的商品,在...

    用Session、Hashtable实现购物车功能

    本教程将详细讲解如何使用Java中的Session和Hashtable来实现这一功能。 首先,Session是Web应用程序中用于跟踪用户状态的一种机制。在HTTP协议无状态的特性下,Session为我们提供了在多个请求之间保持用户信息的...

    C# json 转hashtable

    var hashtable = (Hashtable)serializer.Deserialize(jsonString, typeof(Hashtable)); ``` 2. **Newtonsoft.Json**:这是更流行和功能强大的第三方库,也被称为Json.NET。它的`JsonConvert.DeserializeObject`方法...

    WinFormHashTable最简单用法,.net hashtable ,hashtable ,hashtable用法

    哈希表(Hashtable)是.NET框架中的一种常用数据结构,主要用作键值对存储,它提供了快速的数据存取方式。在WinForm应用程序中,我们可能会利用Hashtable来管理各种对象,尤其是在需要高效查找和操作数据时。下面将...

    HashMap和HashTable的区别和不同

    `HashTable`通过同步每个方法的执行来实现这一点,即在执行`HashTable`的任何方法时,都会锁定整个对象,确保同一时间只有一个线程能够访问或修改`HashTable`。 - **HashMap**: 相较之下,`HashMap`不是一个线程...

    hashMap和hashTable的区别

    `HashMap` 和 `HashTable` 都是 Java 集合框架中非常重要的数据结构,它们都实现了 `Map` 接口,用于存储键值对。尽管它们在功能上有很多相似之处,但在实现细节和性能特性上存在显著差异。 #### 二、主要区别 1. ...

    HashMap和HashTable底层原理以及常见面试题

    HashMap和HashTable是Java中两个常用的数据结构,都是基于哈希表实现的,但它们之间存在着一些关键的区别。本文将深入探讨HashMap和HashTable的底层原理,并总结常见的面试题。 HashMap的底层原理 HashMap是Java中...

    简单HashTable c实现

    哈希表(HashTable)是一种常见的数据结构,它通过哈希函数将键(Key)映射到数组的索引位置,从而实现快速查找、插入和删除操作。在C语言中实现哈希表,需要理解哈希函数的设计、冲突解决策略以及数据结构的组织...

    asp.net遍历hashtable

    在ASP.NET中,Hashtable是一种常用的数据结构,它是一个键值对集合,允许程序员存储和检索对象。本篇文章将深入探讨如何在ASP...在WebSite3项目中,可能涉及的就是如何在实际应用中使用这些技巧,实现高效的数据管理。

    hashtable存储数据.rar

    此外,`Hashtable`实现了`Map`接口,所以也可以使用`entrySet()`方法获取所有键值对的`Set`视图,方便进行遍历和操作。 在实际开发中,由于`Hashtable`的线程安全特性,它通常在需要跨线程共享数据时使用。但是,`...

    HashMap与HashTable区别

    在Java编程语言中,`HashMap`和`HashTable`是两种非常重要的数据结构,它们都实现了`Map`接口,并提供了键值对的存储方式。这两种数据结构虽然相似,但在实现细节和使用场景上存在显著差异。下面将详细介绍`HashMap`...

    hashmap与hashtable区别

    - **Hashtable**:该类继承自`Dictionary`类,并且实现了`Map`接口。它最早出现在Java 1.0版本中,可以视为早期实现键值对存储的一种方式。 - **HashMap**:相比之下,`HashMap`是在Java 1.2版本中引入的新类,它...

    hashtable排序

    实现hashtable按值排序和按key排序,可直接运行

    hashtable和hashmap的区别

    在Java编程语言中,`Hashtable`和`HashMap`是两种非常重要的数据结构,它们都实现了`Map`接口,用于存储键值对。尽管它们有着相似的功能,但在实现细节和应用场景上存在显著差异。接下来,我们将详细探讨`Hashtable`...

Global site tag (gtag.js) - Google Analytics