`
cynhafa
  • 浏览: 163214 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

java的Hashtable

 
阅读更多
Hashtables(哈希表)在计算机领域中已不是一个新概念了。它们是用来加快计算机的处理速度的,用当今的标准来处理,速度非常慢,而它们可以让你在查询许多数据条目时,很快地找到一个特殊的条目。尽管现代的机器速度已快了几千倍,但是为了得到应用程序的最佳性能,hashtables仍然是个很有用的方法。

<wbr><wbr><wbr>设想一下,你有一个包含约一千条记录的数据文件,比如一个小企业的客户记录,还有一个程序,它把记录读到内存中进行处理。每个记录包含一个唯一的五位数的客户ID号、客户名字、地址、帐户结余等等。假设记录不是按客户ID号顺序分类的,所以,如果程序要将客户ID号作为“key”<wbr>来查找一个特殊的客户记录,唯一的查找方法就是连续地搜索每个记录。有时侯,它会很快找到你需要的记录;但有时侯,在程序找到你需要的记录前,它几乎已搜索到了最后一条记录。如果要在1,000条记录中搜索,那么查找任何一条记录都需要程序平均查核500.5<wbr>((1000<wbr>+<wbr>1<wbr>)/2)条记录。如果你常需要查找数据,你应该需要一个更快的方法来找到一条记录。<wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

<wbr></wbr>

<wbr><span style="font-size:16px; color:#333333"><wbr><wbr><wbr><wbr><wbr><wbr>一种加快搜索的方法就是把记录分成几段,这样,你就不用搜索一个很大的列表了,而是搜索几个短的列表。对于我们数字式的客户ID号,你可以建10个列表,以0开头的ID号组成一个列表,以1开头的ID号组成一个列表,依此类推。那么要查找客户ID号38016,你只需要搜索以3开头的列表就行了。如果有1,000条记录,每个列表的平均长度为100(1,000条记录被分成10个列表),那么搜索一条记录的平均比较次数就降到了约50(见图1)。<br> 当然,如果约十分之一的客户号是以0开头的,另外十分之一是以1开头的,等等,那么这种方法会很适合。如果90%的客户号以0开头,那么那个列表就会有900条记录,每次查找平均需要进行450次比较。另外,程序需要执行的搜索有90%都是针对以0开头的号码的。因此,平均比较数就大大超过简单数学运算的范围了。<br><wbr><wbr><wbr>如果我们可以按这样一种方式在我们的列表中分配记录,情况就会好一些,即每个列表约有相同条目的记录,而不管键值中数字的分布。我们需要一种方法能够把客户号码混合到一起并更好地分布结果。例如,我们可以取号码中的每位数,乘以某个大的数(随着数字位置的不同而不同),<wbr>然后将结果相加产生一个总数,把这个数除以10,并将余数作为索引值(index)(除数相同的分到一组)。当读入记录时,程序在客户号码上运行这个哈希(hash)<wbr>函数来确定记录属于哪个列表。当用户需要查询时,将同一个哈希函数作为一个“key”用于客户号码,这样就可以搜索正确的列表了。<wbr>像这样的一个数据结构就称为一个哈希表(hashtable)。<br><br> Java中的Hashtables<br><wbr><wbr><wbr>Java包含两个类,java.util.Hashtable<wbr>和java.util.HashMap,它们提供了一个多种用途的hashtable机制。这两个类很相似,通常提供相同的公有接口。但它们的确有一些重要的不同点,我在后面会讲到。<wbr><br> Hashtable和HashMap对象可以让你把一个key和一个value结合起来,并用put()<wbr>方法把这对key/value输入到表中。然后你可以通过调用get()方法,把key作为参数来得到这个value(值)。只要满足两个基本的要求,key和value可以是任何对象。注意,因为key和value必须是对象,所以原始类型(primitive<wbr>types)必须通过运用诸如Integer(int)的方法转换成对象。<br><wbr><wbr><wbr>为了将一个特定类的对象用做一个key,这个类必须提供两个方法,equals()<wbr>和<wbr>hashCode()。这两个方法在java.lang.Object中,所以所有的类都可以继承这两个方法;但是,这两个方法在Object类中的实现一般没什么用,所以你通常需要自己重载这两个方法。Equals()方法把它的对象同另一个对象进行比较,如果这两个对象代表相同的信息,则返回true。该方法也查看并确保这两个对象属于相同的类。如果两个参照对象是完全一样的对象,Object.equals()返回true,这就说明了为什么这个方法通常不是很适合的原因。在大多数情况下,你需要一个方法来一个字段一个字段地进行比较,所以我们认为代表相同数据的不同对象是相等的。<wbr><br><wbr><wbr><wbr>HashCode()方法通过运用对象的内容执行一个哈希函数来生成一个int值。Hashtable和HashMap用这个值来算出一对key/value位于哪个bucket(哈希元)(或列表)中。作为例子,我们可以查看一下String<wbr>类,因为它有自己的方法来实现这两个方法。String.equals()对两个String对象一个字符一个字符地进行比较,如果字符串是相同的,则返回true:<br> String<wbr>myName<wbr>=<wbr>"Einstein";<br> //<wbr>The<wbr>following<wbr>test<wbr>is<wbr><br> //<wbr>always<wbr>true<br> if<wbr>(<wbr>myName.equals("Einstein")<wbr>)<br> {<wbr>...<br><wbr><wbr><wbr>String.hashCode()在一个字符串上运行哈希函数。字符串中每个字符的数字代码都乘以31,结果取决于字符串中字符的位置。然后将这些计算的结果相加,得到一个总数。这个过程似乎很复杂,但是它确保能够更好地分布值。它也证明了你在开发你自己的hashCode()方法时,能够走多远,确信结果是唯一的。<br> 例如,假设我要用一个hashtable来实现一个书的目录,把书的ISBN号码作为搜索键来进行搜索。我可以用String类来承载细节,并准备好了equals()和hashCode()方法。我们可以用put()方法添加成对的key/value到hashtable中。<br> Put()方法接受两个参数,它们都属于Object类型。第一个参数是key;第二个参数是value。Put()方法调用key的hashCode()方法,用表中的列表数来除这个结果。把余数作为索引值来确定该条记录添加到哪个列表中。注意,key在表中是唯一的;如果你用一个已经存在的key来调用put(),匹配的条目就被修改了,因此它参照的是一个新的值,而旧的值被返回了(当key在表中不存在时,put()返回空值)。要读取表中的一个值,我们把搜索键用于get()方法。它返回一个转换到正确类型的Object参照:<br> BookRecord<wbr>br<wbr>=(BookRecord)isbnTable.get("0-345-40946-9");<br> System.out.println("Author:<wbr>"<wbr>+<wbr>br.author+<wbr>"<wbr>Title:<wbr>"<wbr>+<wbr>br.title);<br><br><wbr><wbr><wbr>另一个有用的方法是remove(),其用法同get()几乎一样,它把条目从表中删除,并返回给调用程序。<br><br> 你自己的类<br><wbr><wbr><wbr>如果你想把一个原始类型用做一个key,你必须创建一个同等类型的对象。例如,如果你想用一个整数key,你应该用构造器Integer(int)从整数中生成一个对象。所有的封装类如Integer、Float和Boolean都把原始值看做是对象,它们重载了equals()和hashCode()方法,因此,它们可以被用做key。JDK中提供的许多其它的类也是这样的(甚至Hashtable和HashMap类都实现它们自己的equals()和hashCode()方法),但你把任何类的对象用做hashtable<wbr>keys前,应该查看文件。查看类的来源,看看equals()和hashCode()是如何实现的,也很有必要。例如,Byte、Character、Short和Integer都返回所代表的整数值作为哈希码。这可能适合,也可能不适合你的需求。<br><br><wbr><wbr><wbr><wbr>如果你想创建一个hashtable,这个hashtable运用你自己定义的一个类的对象作为key,那么你应该确信这个类的equals()和hashCode()方法提供有用的值。首先查看你扩展的类,确定它的实现是否满足你的需求。如果没有,你应该重载方法。<br><br><wbr><wbr><wbr><wbr>任何equals()方法的基本设计约束是,如果传递给它的对象属于同一个类,而且它的数据字段设定为表示同样数据的值,那么它就应该返回true。你也应该确信,如果传递一个空的参数给该方法,那么你的代码返回false:<br> public<wbr>boolean<wbr>equals(Object<wbr>o){<br> if<wbr>(<wbr>(o<wbr>==<wbr>null)||<wbr>!(o<wbr>instanceof<wbr>myClass)){<br> return<wbr>false;<br> }<br><br> //<wbr>Now<wbr>compare<wbr>data<wbr>fields...<br><br><wbr><wbr><wbr><wbr>另外,在设计一个hashCode()方法时,应该记住一些规则。首先,该方法必须为一个特定的对象返回相同的值,而不管这个方法被调用了多少次(当然,只要对象的内容在调用之间没有改变,在将一个对象用做一个hashtable的key时,应该避免这一点)。第二,如果由你的equals()方法定义的两个对象是相等的,那么它们也必须生成相同的哈希码。第三,这更像是一个方针,而不是一个原则,你应该设法设计方法,使它为不同的对象内容生成不同的结果。如果偶尔不同的对象正好生成了相同的哈希码,这也不要紧。但是,如果该方法只能返回范围在1到10的值,那么只能用10个列表,而不管在hashtable中有多少个列表。<br><br><wbr><wbr><wbr><wbr>在设计equals()和hashCode()时,另一个要记住的因素是性能问题。每次调用put()或get(),都包括调用hashCode()来查找正确的列表,当get()扫描列表来查找key时,它为列表中的每个元素调用equals()。实现这些方法使它们尽可能快而有效地运行,尤其当你打算使你的类公开可用时,因为其它的用户可能想在执行速度很重要的情况下,在高性能的应用程序中运用你的类。<br><br> Hashtable性能<br><wbr><wbr><wbr><wbr>影响hashtable功效的主要因素就是表中列表的平均长度,因为平均搜索时间与这个平均长度直接相关。很显然,要减均长度,你必须增加hashtable中列表的数量;如果列表数量非常大,以至于大多数列表或所有列表只包含一条记录,你就会获得最佳的搜索效率。然而,这样做可能太过分了。如果你的hashtable的列表数远远多于数据条目,那你就没有必要做这样的内存花费了,而在一些情况下,人们也不可能接受这样的做法。<br> 在我们前面的例子中,我们预先知道我们有多少条记录1,000。知道这点后,我们就可以决定我们的hashtable应该包含多少个列表,以便达成搜索速度和内存使用效率之间最好的折衷方式。然而,在许多情况下,你预先不知道你要处理多少条记录;数据被读取的文件可能会不断扩大,或者记录的数量可能一天一天地发生很大的变化。<br> 随着条目的增加,Hashtable和HashMap类通过动态地扩展表来处理这个问题。这两个类都有接受表中列表最初数量的构造器,和一个作为参数的负载系数(load<wbr>factor):<br> public<wbr>Hashtable(int<wbr>initialCapacity,float<wbr>loadFactor)<br><br> public<wbr>HashMap(int<wbr>initialCapacity,float<wbr>loadFactor)<br><br><wbr><wbr><wbr><wbr>将这两个数相乘计算出一个临界值。每次给哈希表添加一个新的条目时,计数就被更新,当计数超过临界值时,表被重新设置(rehash)。(列表数量增加到以前数量的两倍加1,所有的条目转移到正确的列表中。)缺省的构造器设定最初的容量为11,负载系数是0.75,所以临界值是8。当第九条记录被添加到表中时,就重新调整哈希表,使其有23个列表,新的临界值将是17(23*0.75的整数部分)。你可以看到,负载系数是哈希表中平均列表数量的上限,这就意味着,在缺省情况下,哈希表很少会有许多包含不只一条记录的列表。比较我们最初的例子,在那个例子中,我们有1,000条记录,分布在10个列表中。如果我们用缺省值,这个表将会扩展到含有1,500多个列表。但你可以控制这点。如果用负载系数相乘的列表数量大于你处理的条目数,那么表永远不会重制,所以我们可以仿效下面的例子://<wbr>Table<wbr>will<wbr>not<wbr>rehash<wbr>until<wbr>it<br> //<wbr>has<wbr>1,100<wbr>entries<wbr>(10*110):<br> Hashtable<wbr>myHashTable<wbr>=<wbr>new<wbr>Hashtable(10,<wbr>110.0F);<br><br><wbr><wbr><wbr><wbr>你可能不想这么做,除非你没有为空的列表节省内存,而且不介意额外的搜索时间,这可能在嵌入系统中会出现这种情况。然而,这种方法可能很有用,因为重新设置很占用计算时间,而这种方法可以保证永远不会发生重新设置这种情况。注意,虽然调用put()可以使表增大(列表数量增加),调用remove()不会有相反的结果。所以,如果你有一个大的表,而且从中删除了大部分条目,结果你会有一个大的但是大部分是空的表。<br> Hashtable和HashMap<br><wbr><wbr><wbr><wbr>Hashtable和HashMap类有三个重要的不同之处。第一个不同主要是历史原因。Hashtable是基于陈旧的Dictionary类的,HashMap是Java<wbr>1.2引进的Map接口的一个实现。<br> 也许最重要的不同是Hashtable的方法是同步的,而HashMapu方法不是。这就意味着,虽然你可以不用采取任何特殊的行为就可以在一个多线程的应用程序中用一个Hashtable,但你必须同样地为一个HashMap提供外同步。一个方便的方法就是利用Collections类的静态的synchronizedMap()方法,它创建一个线程安全的Map对象,并把它作为一个封装的对象来返回。这个对象的方法可以让你同步访问潜在的HashMap。这么做的结果就是当你不需要同步时,你不能切断Hashtable中的同步(比如在一个单线程的应用程序中),而且同步增加了很多处理费用。第三点不同是,只有HashMap可以让你将空值作为一个表的条目的key或value。HashMap中只有一条记录可以是一个空的key,但任意数量的条目可以是空的value。这就是说,如果在表中没有发现搜索键,或者如果发现了搜索键,但它是一个空的值,那么get()将返回null。如果有必要,用containKey()方法来区别这两种情况。<br><br><wbr><wbr><wbr><wbr>一些资料建议,当需要同步时,用Hashtable,反之用HashMap。但是,因为在需要时,HashMap可以被同步,HashMap的功能比Hashtable的功能更多,而且它不是基于一个陈旧的类的,所以有人认为,在各种情况下,HashMap都优先于Hashtable。<br><br> 关于Properties<br><wbr><wbr><wbr><wbr>有时侯,你可能想用一个hashtable来映射key的字符串到value的字符串。DOS、Windows和Unix中的环境字符串就有一些例子,如key的字符串PATH被映射到value的字符串C:\WINDOWS;C:\WINDOWS\SYSTEM。Hashtables是表示这些的一个简单的方法,但Java提供了另外一种方法。<br><wbr><wbr><wbr><wbr>Java.util.Properties类是Hashtable的一个子类,设计用于String<wbr>keys和values。Properties对象的用法同Hashtable的用法相象,但是类增加了两个节省时间的方法,你应该知道。Store()方法把一个Properties对象的内容以一种可读的形式保存到一个文件中。Load()方法正好相反,用来读取文件,并设定Properties对象来包含keys和values。注意,因为Properties扩展了Hashtable,你可以用超类的put()方法来添加不是String对象的keys和values。这是不可取的。另外,如果你将store()用于一个不包含String对象的Properties对象,store()将失败。作为put()和get()的替代,你应该用setProperty()和getProperty(),它们用String参数。好了,我希望你现在可以知道如何用hashtables来加速你的处理了。</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></span></wbr>


分享到:
评论

相关推荐

    java Hashtable的泛型化

    在Java编程语言中,`Hashtable`是`Collections`框架的一部分,它是一个同步的键值对存储容器。在早期的Java版本中,`Hashtable`并没有直接支持泛型,这意味着你可以在其中存储任何类型的键(`Object`)和值(`Object...

    HashTable的java实现

    在Java编程语言中,哈希表(HashTable)是一种常见的数据结构,它提供了高效的数据存储和检索功能。哈希表基于哈希函数将键(Key)映射到数组的索引位置,通过键值对(Key-Value Pair)来存储数据。这种数据结构允许...

    java的hashtable的用法.docx

    在Java编程语言中,`Hashtable`是`Dictionary`类的一个具体实现,它提供了一个基于键值对的数据结构,允许程序员存储和检索对象。`Hashtable`类是线程安全的,因此可以在多线程环境中直接使用,而无需额外的同步控制...

    java的hashtable的用法.pdf

    Java中的`Hashtable`是`Dictionary`类的一个具体实现,它是一个基于哈希表的键值对存储结构。在Java标准库中,`Hashtable`属于早期的集合框架成员,不支持泛型,但在处理键和值时依然需要确保它们都是非null的引用。...

    java hashtable实现代码

    Java中的`Hashtable`类是Java集合框架的一部分,它是一个基于哈希表的Map接口实现。这个数据结构允许我们以键值对的形式存储数据,并且提供了快速的插入、删除和查找操作。`Hashtable`是线程安全的,因此可以在多...

    Java 实例 - 遍历 HashTable 的键值源代码+详细教程.zip

    在Java编程语言中,`HashTable`是一个非常重要的数据结构,它提供了一种存储键值对的方式,其中每个键都是唯一的。这个压缩包“Java 实例 - 遍历 HashTable 的键值源代码+详细教程.zip”包含了关于如何遍历`...

    Hashtable的使用

    在Java编程语言中,`Hashtable`是一个基于键值对(key-value pairs)的数据结构,它属于同步的、线程安全的容器类。`Hashtable`是`Dictionary`类的一个子类,它不支持`null`键或`null`值。这个类实现了`Map`接口,...

    Java 实例 - 使用 Enumeration 遍历 HashTable源代码+详细指导教程.zip

    在Java编程语言中,`HashTable`是一个非常基础且重要的数据结构,它提供了键值对(key-value pairs)的存储功能。本教程将深入探讨如何使用`Enumeration`接口遍历`HashTable`,并提供详细的源代码实例及指导。`...

    HashMap与HashTable和HashSet的区别

    在Java集合框架中,`HashMap`, `HashTable` 和 `HashSet` 是三个重要的数据结构,它们分别实现了`Map`接口和`Set`接口,提供了不同的功能来满足不同的编程需求。本文将重点分析这三种数据结构之间的区别,特别是针对...

    Java中HashTable和HashMap的区别_动力节点Java学院整理

    Java中的`HashTable`和`HashMap`都是实现`Map`接口的数据结构,用于存储键值对。两者虽然在功能上相似,但在实现细节和使用场景上有显著的区别。 首先,线程安全性是两者之间的一个关键差异。`HashTable`是线程安全...

    Java中Hashtable类与HashMap类的区别详解

    Java中的`Hashtable`和`HashMap`都是用于存储键值对的数据结构,它们都实现了`Map`接口,但在一些关键特性上有所不同。以下是这两者的主要区别: 1. **线程安全性**: - `Hashtable`是线程安全的,这意味着在多...

    java对LDAP的增删改查

    首先,需要import 相应的类库,包括 `java.util.Hashtable`、`javax.naming.Context`、`javax.naming.NamingException`、`javax.naming.directory.DirContext` 和 `javax.naming.directory.InitialDirContext`。...

    java 对象集合小例子.

    本篇文章将深入探讨Java中的几个主要对象集合:Hashtable、Vector、LinkedList以及数组和集合的基本概念。 首先,让我们来看Java中的`Hashtable`。Hashtable是Java早期版本中的一个同步容器类,它继承自Dictionary...

    JAVA修改AD域密码_免证书

    Hashtable, String&gt; env = new Hashtable(); env.put(Context.INITIAL_CONTEXT_FACTORY, "com.sun.jndi.ldap.LdapCtxFactory"); env.put(Context.PROVIDER_URL, "ldap://your.ad.server:389"); env.put(Context....

    Java RMI中文规范

    - **面向对象**:RMI允许传递整个对象,包括复杂类型,如Java HashTable,而不仅仅是基本数据类型。这使得分布式计算能够充分利用面向对象的优势。 - **可移动属性**:RMI可以将对象的实现从客户机移动到服务器,...

    《JAVA程序设计》期末考试试题及答案.doc

    System.out.println(hashtable.get("300").toString() + hashtable.get("200").toString() + hashtable.get("100").toString()); // 输出 "cccbbbaaa" ``` ### 8. 异常处理与异常类层次结构 **知识点概述:** - **...

    java中得泛型

    以`Hashtable`为例,在Java中,`Hashtable`是一个用于存储键值对的集合类。在引入泛型前,`Hashtable`只能使用`Object`作为键和值的类型,这意味着无论我们希望存储的是哪种类型的键值对,都必须显式地进行类型转换...

    浅谈Java web中基于Hashtable的数据库操作.zip

    在Java Web开发中,数据库操作是不可或缺的一部分,而基于Hashtable的数据存储和检索方式曾经是早期常用的手段之一。本文将深入探讨如何在Java Web环境中利用Hashtable进行数据库交互,并讨论其优缺点以及现代开发中...

    java 中遍历取值异常(Hashtable Enumerator)解决办法

    在Java编程中,`Hashtable` 是一个古老的容器类,它继承自 `Dictionary` 类,并实现了 `Map` 接口。`Hashtable` 不允许存储 `null` 键和 `null` 值,且它是线程安全的。在使用 `Hashtable` 进行遍历时,可能会遇到一...

Global site tag (gtag.js) - Google Analytics