《在java中运用hashtable》由会员分享，可在线阅读，更多相关《在java中运用hashtable（7页珍藏版）》请在金锄头文库上搜索。
1、Hashtables提供了一个很有用的方法可以使应用程序的性能达到最佳。 Hashtables（哈希表）在计算机领域中已不是一个新概念了。它们是用来加快计算机的处理速度的，用当今的标准来处理，速度非常慢，而它们可以让你在查询许多数据条目时，很快地找到一个特殊的条目。尽管现代的机器速度已快了几千倍，但是为了得到应用程序的最佳性能，hashtables仍然是个很有用的方法。 设想一下，你有一个包含约一千条记录的数据文件,比如一个小企业的客户记录,还有一个程序，它把记录读到内存中进行处理。每个记录包含一个唯一的五位数的客户ID号、客户名字、地址、帐户结余等等。假设记录不是按客户ID号顺序分类的，所以
2、，如果程序要将客户ID号作为“key” 来查找一个特殊的客户记录，唯一的查找方法就是连续地搜索每个记录。有时侯，它会很快找到你需要的记录；但有时侯，在程序找到你需要的记录前，它几乎已搜索到了最后一条记录。如果要在1,000条记录中搜索，那么查找任何一条记录都需要程序平均查核500.5 (1000 + 1 )/2)条记录。如果你常需要查找数据，你应该需要一个更快的方法来找到一条记录。一种加快搜索的方法就是把记录分成几段，这样，你就不用搜索一个很大的列表了，而是搜索几个短的列表。对于我们数字式的客户ID号，你可以建10个列表,以0开头的ID号组成一个列表，以1开头的ID号组成一个列表，依此类推。那
3、么要查找客户ID号38016，你只需要搜索以3开头的列表就行了。如果有1,000条记录，每个列表的平均长度为100（1,000条记录被分成10个列表），那么搜索一条记录的平均比较次数就降到了约50（见图1）。 当然，如果约十分之一的客户号是以0开头的，另外十分之一是以1开头的，等等，那么这种方法会很适合。如果90%的客户号以0开头，那么那个列表就会有900条记录，每次查找平均需要进行450次比较。另外，程序需要执行的搜索有90%都是针对以0开头的号码的。因此，平均比较数就大大超过简单数学运算的范围了。 如果我们可以按这样一种方式在我们的列表中分配记录，情况就会好一些，即每个列表约有相同条目的记
4、录，而不管键值中数字的分布。我们需要一种方法能够把客户号码混合到一起并更好地分布结果。例如，我们可以取号码中的每位数，乘以某个大的数（随着数字位置的不同而不同）， 然后将结果相加产生一个总数，把这个数除以10，并将余数作为索引值（index）(除数相同的分到一组)。当读入记录时，程序在客户号码上运行这个哈希（hash) 函数来确定记录属于哪个列表。当用户需要查询时，将同一个哈希函数作为一个“key”用于客户号码，这样就可以搜索正确的列表了。 像这样的一个数据结构就称为一个哈希表（hashtable)。 Java中的Hashtables Java包含两个类，java.util.Hashtable
5、 和java.util.HashMap，它们提供了一个多种用途的hashtable机制。这两个类很相似，通常提供相同的公有接口。但它们的确有一些重要的不同点，我在后面会讲到。 Hashtable和HashMap对象可以让你把一个key和一个value结合起来，并用put() 方法把这对key/value输入到表中。然后你可以通过调用get()方法，把key作为参数来得到这个value（值）。只要满足两个基本的要求，key和value可以是任何对象。注意，因为key和value必须是对象，所以原始类型（primitive types）必须通过运用诸如Integer(int)的方法转换成对象。 为
6、了将一个特定类的对象用做一个key，这个类必须提供两个方法，equals() 和 hashCode()。这两个方法在java.lang.Object中，所以所有的类都可以继承这两个方法；但是，这两个方法在Object类中的实现一般没什么用，所以你通常需要自己重载这两个方法。Equals()方法把它的对象同另一个对象进行比较，如果这两个对象代表相同的信息，则返回true。该方法也查看并确保这两个对象属于相同的类。如果两个参照对象是完全一样的对象，Object.equals()返回true，这就说明了为什么这个方法通常不是很适合的原因。在大多数情况下，你需要一个方法来一个字段一个字段地进行比较，所
7、以我们认为代表相同数据的不同对象是相等的。 HashCode()方法通过运用对象的内容执行一个哈希函数来生成一个int值。Hashtable和HashMap用这个值来算出一对key/value位于哪个bucket（哈希元）（或列表）中。作为例子，我们可以查看一下String 类，因为它有自己的方法来实现这两个方法。String.equals()对两个String对象一个字符一个字符地进行比较，如果字符串是相同的，则返回true： String myName = Einstein; / The following test is / always true if ( myName.equals(
8、Einstein) ) . String.hashCode()在一个字符串上运行哈希函数。字符串中每个字符的数字代码都乘以31，结果取决于字符串中字符的位置。然后将这些计算的结果相加，得到一个总数。这个过程似乎很复杂，但是它确保能够更好地分布值。它也证明了你在开发你自己的hashCode()方法时，能够走多远，确信结果是唯一的。 例如，假设我要用一个hashtable来实现一个书的目录，把书的ISBN号码作为搜索键来进行搜索。我可以用String类来承载细节，并准备好了equals()和hashCode()方法。我们可以用put()方法添加成对的key/value到hashtable中。 Pu
9、t()方法接受两个参数，它们都属于Object类型。第一个参数是key；第二个参数是value。Put()方法调用key的hashCode()方法，用表中的列表数来除这个结果。把余数作为索引值来确定该条记录添加到哪个列表中。注意，key在表中是唯一的；如果你用一个已经存在的key来调用put()，匹配的条目就被修改了，因此它参照的是一个新的值，而旧的值被返回了（当key在表中不存在时，put()返回空值）。要读取表中的一个值，我们把搜索键用于get()方法。它返回一个转换到正确类型的Object参照： BookRecord br =(BookRecord)isbnTable.get(0-345
10、-40946-9); System.out.println(Author: + br.author+ Title: + br.title); 另一个有用的方法是remove()，其用法同get()几乎一样，它把条目从表中删除，并返回给调用程序。 你自己的类 如果你想把一个原始类型用做一个key，你必须创建一个同等类型的对象。例如，如果你想用一个整数key，你应该用构造器Integer(int)从整数中生成一个对象。所有的封装类如Integer、Float和Boolean都把原始值看做是对象，它们重载了equals()和hashCode()方法，因此，它们可以被用做key。JDK中提供的许多其它
11、的类也是这样的（甚至Hashtable和HashMap类都实现它们自己的equals()和hashCode()方法），但你把任何类的对象用做hashtable keys前，应该查看文件。查看类的来源，看看equals()和hashCode()是如何实现的，也很有必要。例如，Byte、Character、Short和Integer都返回所代表的整数值作为哈希码。这可能适合，也可能不适合你的需求。 如果你想创建一个hashtable，这个hashtable运用你自己定义的一个类的对象作为key，那么你应该确信这个类的equals()和hashCode()方法提供有用的值。首先查看你扩展的类，确定它
12、的实现是否满足你的需求。如果没有，你应该重载方法。 任何equals()方法的基本设计约束是，如果传递给它的对象属于同一个类，而且它的数据字段设定为表示同样数据的值，那么它就应该返回true。你也应该确信，如果传递一个空的参数给该方法，那么你的代码返回false： public boolean equals(Object o) if ( (o = null)| !(o instanceof myClass) return false; / Now compare data fields. 另外，在设计一个hashCode()方法时，应该记住一些规则。首先，该方法必须为一个特定的对象返回相同的值
13、，而不管这个方法被调用了多少次（当然，只要对象的内容在调用之间没有改变，在将一个对象用做一个hashtable的key时，应该避免这一点）。第二，如果由你的equals()方法定义的两个对象是相等的，那么它们也必须生成相同的哈希码。第三，这更像是一个方针，而不是一个原则，你应该设法设计方法，使它为不同的对象内容生成不同的结果。如果偶尔不同的对象正好生成了相同的哈希码，这也不要紧。但是，如果该方法只能返回范围在1到10的值，那么只能用10个列表，而不管在hashtable中有多少个列表。 在设计equals()和hashCode（）时，另一个要记住的因素是性能问题。每次调用put()或get()
14、，都包括调用hashCode()来查找正确的列表，当get()扫描列表来查找key时，它为列表中的每个元素调用equals()。实现这些方法使它们尽可能快而有效地运行，尤其当你打算使你的类公开可用时，因为其它的用户可能想在执行速度很重要的情况下，在高性能的应用程序中运用你的类。 Hashtable性能 影响hashtable功效的主要因素就是表中列表的平均长度，因为平均搜索时间与这个平均长度直接相关。很显然，要减小平均长度，你必须增加hashtable中列表的数量；如果列表数量非常大，以至于大多数列表或所有列表只包含一条记录，你就会获得最佳的搜索效率。然而，这样做可能太过分了。如果你的hash
15、table的列表数远远多于数据条目，那你就没有必要做这样的内存花费了，而在一些情况下，人们也不可能接受这样的做法。 在我们前面的例子中，我们预先知道我们有多少条记录1,000。知道这点后，我们就可以决定我们的hashtable应该包含多少个列表，以便达成搜索速度和内存使用效率之间最好的折衷方式。然而，在许多情况下，你预先不知道你要处理多少条记录；数据被读取的文件可能会不断扩大，或者记录的数量可能一天一天地发生很大的变化。 随着条目的增加，Hashtable和HashMap类通过动态地扩展表来处理这个问题。这两个类都有接受表中列表最初数量的构造器，和一个作为参数的负载系数（load factor）： public Hashtable(int initialCapacity,float loadFactor) public HashMap(int initialCapacity,float loadFactor) 将这两个数相乘计算出一个临界值。每次给哈希表添加一个新的条目时，计数就被更新，当计数超过临界值时，表被重新设置（rehash)。（列表数量增加到以前数量的两倍加1，所有的条目转移到正确的列表中。）缺省的构造器设定最初的容量为11，负载系数是0.75，所以临界值是8。当第九条记录被添加到表中时，就重新调整哈希表，使其有23个列表，新的临界值将是17（23*0.75的整数
