全面解析java中的hashtable
Hashtables提供了一个很有用的方法可以使应用程序的性能达到最佳。
Hashtables(哈希表)在计算机领域中已不是一个新概念了。它们是用来加快计算机的处理速度的,用当今的标准来处理,速度非常慢,而它们可以让你在查询许多数据条目时,很快地找到一个特殊的条目。尽管现代的机器速度已快了几千倍,但是为了得到应用程序的最佳性能,hashtables仍然是个很有用的方法。
设想一下,你有一个包含约一千条记录的数据文件??比如一个小企业的客户记录还有一个程序,它把记录读到内存中进行处理。每个记录包含一个唯一的五位数的客户ID号、客户名字、地址、帐户结余等等。假设记录不是按客户ID号顺序分类的,所以,如果程序要将客户号作为“key”来查找一个特殊的客户记录,唯一的查找方法就是连续地搜索每个记录。有时侯,它会很快找到你需要的记录;但有时侯,在程序找到你需要的记录前,它几乎已搜索到了最后一条记录。如果要在1,000条记录中搜索,那么查找任何一条记录都需要程序平均查核500.5((1000+1)/2)条记录。如果你常需要查找数据,你应该需要一个更快的方法来找到一条记录。
一种加快搜索的方法就是把记录分成几段,这样,你就不用搜索一个很大的列表了,而是搜索几个短的列表。对于我们数字式的客户ID号,你可以建10个列表??以0开头的ID号组成一个列表,以1开头的ID号组成一个列表,依此类推。那么要查找客户ID号38016,你只需要搜索以3开头的列表就行了。如果有1,000条记录,每个列表的平均长度为100(1,000条记录被分成10个列表),那么搜索一条记录的平均比较次数就降到了约50(见图1)。
当然,如果约十分之一的客户号是以0开头的,另外十分之一是以1开头的,等等,那么这种方法会很适合。如果90%的客户号以0开头,那么那个列表就会有900条记录,每次查找平均需要进行450次比较。另外,程序需要执行的搜索有90%都是针对以0开头的号码的。因此,平均比较数就大大超过简单数学运算的范围了。
如果我们可以按这样一种方式在我们的列表中分配记录,情况就会好一些,即每个列表约有相同条目的记录,而不管键值中数字的分布。我们需要一种方法能够把客户号码混合到一起并更好地分布结果。例如,我们可以取号码中的每位数,乘以某个大的数(随着数字位置的不同而不同),然后将结果相加产生一个总数,把这个数除以10,并将余数作为索引值(index)。当读入记录时,程序在客户号码上运行这个哈希(hash)函数来确定记录属于哪个列表。当用户需要查询时,将同一个哈希函数作为一个“key”用于客户号码,这样就可以搜索正确的列表了。像这样的一个数据结构就称为一个哈希表(hashtable)。
Hashtable和HashMap对象可以让你把一个key和一个value结合起来,并用
为了将一个特定类的对象用做一个key,这个类必须提供两个方法,equals()和hashCode()。这两个方法在
Equals()方法把它的对象同另一个对象进行比较,如果这两个对象代表相同的信息,则返回true。该方法也查看并确保这两个对象属于相同的类。如果两个参照对象是完全一样的对象,Object.equals()返回true,这就说明了为什么这个方法通常不是很适合的原因。在大多数情况下,你需要一个方法来一个字段一个字段地进行比较,所以我们认为代表相同数据的不同对象是相等的。
HashCode()方法通过运用对象的内容执行一个哈希函数来生成一个int值。Hashtable和HashMap用这个值来算出一对key/value位于哪个bucket(哈希元)(或列表)中。
作为例子,我们可以查看一下String类,因为它有自己的方法来实现这两个方法。String.equals()对两个String对象一个字符一个字符地进行比较,如果字符串是相同的,则返回true:
StringmyName="Einstein";
//Thefollowingtestis
//alwaystrue
if(myName.equals("Einstein"))
{...
String.hashCode()在一个字符串上运行哈希函数。字符串中每个字符的数字代码都乘以31,结果取决于字符串中字符的位置。然后将这些计算的结果相加,得到一个总数。这个过程似乎很复杂,但是它确保能够更好地分布值。它也证明了你在开发你自己的hashCode()方法时,能够走多远,确信结果是唯一的。
例如,假设我要用一个hashtable来实现一个书的目录,把书的ISBN号码作为搜索键来进行搜索。我可以用String类来承载细节,并准备好了equals()和hashCode()方法(见列表1)。我们可以用
要读取表中的一个值,我们把搜索键用于get()方法。它返回一个转换到正确类型的Object参照:
BookRecordbr=
(BookRecord)isbnTable.get(
"0-345-40946-9");
System.out.println(
"Author:"+br.author
+"Title:"+br.title);
另一个有用的方法是remove(),其用法同get()几乎一样,它把条目从表中删除,并返回给调用程序。
在
如果你想创建一个hashtable,这个hashtable运用你自己定义的一个类的对象作为key,那么你应该确信这个类的equals()和hashCode()方法提供有用的值。首先查看你扩展的类,确定它的实现是否满足你的需求。如果没有,你应该重载方法。
任何equals()方法的基本设计约束是,如果传递给它的对象属于同一个类,而且它的数据字段设定为表示同样数据的值,那么它就应该返回true。你也应该确信,如果传递一个空的参数给该方法,那么你的代码返回
false:publicbooleanequals(Objecto)
{
if((o==null)
||!(oinstanceofmyClass))
{
returnfalse;
}
//Nowcomparedatafields...
另外,在设计一个hashCode()方法时,应该记住一些规则。首先,该方法必须为一个特定的对象返回相同的值,而不管这个方法被调用了多少次(当然,只要对象的内容在调用之间没有改变,在将一个对象用做一个hashtable的key时,应该避免这一点)。第二,如果由你的equals()方法定义的两个对象是相等的,那么它们也必须生成相同的哈希码。第三,这更像是一个方针,而不是一个原则,你应该设法设计方法,使它为不同的对象内容生成不同的结果。如果偶尔不同的对象正好生成了相同的哈希码,这也不要紧。但是,如果该方法只能返回范围在1到10的值,那么只能用10个列表,而不管在hashtable中有多少个列表。
在设计equals()和hashCode()时,另一个要记住的因素是性能问题。每次调用
在我们前面的例子中,我们预先知道我们有多少条记录1,000。知道这点后,我们就可以决定我们的hashtable应该包含多少个列表,以便达成搜索速度和内存使用效率之间最好的折中方式。然而,在许多情况下,你预先不知道你要处理多少条记录;数据被读取的文件可能会不断扩大,或者记录的数量可能一天一天地发生很大的变化。
随着条目的增加,Hashtable和HashMap类通过动态地扩展表来处理这个问题。这两个类都有接受表中列表最初数量的构造器,和一个作为参数的负载系数(loadfactor):
publicHashtable(
intinitialCapacity,
floatloadFactor)
publicHashMap(
intinitialCapacity,
floatloadFactor)
将这两个数相乘计算出一个临界值。每次给哈希表添加一个新的条目时,计数就被更新,当计数超过临界值时,表被重新设置(rehash)。(列表数量增加到以前数量的两倍加1,所有的条目转移到正确的列表中。)缺省的构造器设定最初的容量为11,负载系数是0.75,所以临界值是8。当第九条记录被添加到表中时,就重新调整哈希表,使其有23个列表,新的临界值将是17(23*0.75的整数部分)。你可以看到,负载系数是哈希表中平均列表数量的上限,这就意味着,在缺省情况下,哈希表很少会有许多包含不只一条记录的列表。比较我们最初的例子,在那个例子中,我们有1,000条记录,分布在10个列表中。如果我们用缺省值,这个表将会扩展到含有1,500多个列表。但你可以控制这点。如果用负载系数相乘的列表数量大于你处理的条目数,那么表永远不会重制,
//Tablewillnotrehashuntilit
//has1,100entries(10*110):
HashtablemyHashTable=
newHashtable(10,110.0F);
你可能不想这么做,除非你没有为空的列表节省内存,而且不介意额外的搜索时间,这可能在嵌入系统中会出现这种情况。然而,这种方法可能很有用,因为重新设置很占用计算时间,而这种方法可以保证永远不会发生重新设置这种情况。
注意,虽然调用
也许最重要的不同是Hashtable的方法是同步的,而HashMap的方法不是。这就意味着,虽然你可以不用采取任何特殊的行为就可以在一个多线程的应用程序中用一个Hashtable,但你必须同样地为一个HashMap提供外同步。一个方便的方法就是利用Collections类的静态的synchronizedMap()方法,它创建一个线程安全的
第三点不同是,只有HashMap可以让你将空值作为一个表的条目的key或value。HashMap中只有一条记录可以是一个空的key,但任意数量的条目可以是空的value。这就是说,如果在表中没有发现搜索键,或者如果发现了搜索键,但它是一个空的值,那么get()将返回null。如果有必要,用containKey()方法来区别这两种情况。
一些资料建议,当需要同步时,用Hashtable,反之用HashMap。但是,因为在需要时,HashMap可以被同步,HashMap的功能比Hashtable的功能更多,而且它不是基于一个陈旧的类的,所以有人认为,在各种情况下,HashMap都优先于Hashtable。
有时侯,你可能想用一个hashtable来映射key的字符串到value的字符串。DOS、Windows和Unix中的环境字符串就有一些例子,如key的字符串PATH被映射到value的字符串C:\WINDOWS;C:\WINDOWS\SYSTEM。Hashtables是表示这些的一个简单的方法,但
Store()方法把一个Properties对象的内容以一种可读的形式保存到一个文件中。Load()方法正好相反,用来读取文件,并设定Properties对象来包含keys和values。
注意,因为Properties扩展了Hashtable,你可以用超类的
好了,我希望你现在可以知道如何用hashtables来加速你的处理了
相关文章
- java解析xml方法_详解Java解析XML的四种方法
- Contest1620 – 2020-2021-2学期《Java Web 系统开发》:java基础:字符串
- 如何做好Flex与Java交互「建议收藏」
- java语言代码大全_java语言代码大全解析
- java中scanner意思_Java中的Scanner
- java正则表达式解析「建议收藏」
- MySQL字段类型如何转为java_Java JDBC中,MySQL字段类型到JAVA类型的转换
- Java 并发:volatile 关键字解析「建议收藏」
- ringbuffer java例子_Java RingBuffer.publish方法代碼示例「建议收藏」
- Java 中static和非static的区别(方法和变量)
- java使用IMAP连接Gmail并解析邮件详解编程语言
- java解决hash算法冲突详解编程语言
- Java中的Stringbuffer类解析详解编程语言
- java中BigDecimal用法详解编程语言
- Java设计模式:23种设计模式全面解析(超级详细)
- Linux安装Java环境必备指南(linux装java)
- 数据库简易指南:如何使用 Java 连接 MySQL 数据库(java连接mysql)
- 机制解析Redis Java的过期机制.(redisjava过期)
- 数据Java操作MySQL库:获取你所需的数据(java获取mysql)
- 管理Linux下Java版本管理:轻松实现多版本切换(linux下java版本)
- Oracle全面支持Java链技术构建数据库应用(java链oracle)
- Java编程与Oracle技术创造技术价值的奥秘(java编程oracle)
- Java加速Oracle开发之旅(java中oracle包)
- Java采用反射获取class属性值的实现代码
- java当中的定时器的4种使用方式
- Java中堆和栈的区别详解
- Java进阶教程之String类