在Java中运用Hashtables
Hashtables提供了一个很有用的方法可以使应用程序的性能达到最佳。
by Pete Ford
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开头的号码的。因此，平均比较数就大大超过简单数学运算的范围了。
【打印本文】【发给朋友】【返回顶部】
1 2 3 4 5 6 下一页
|
