bookjavavol 2网络应用开发ch15.pdf

第十五章

哈希(Hashing)

•

•15-1简介

•15-2基本概念(BasicConcepts)

•15-3操作哈希(OperationofHashing)

•15-4HashtableClass

•15-5EnumerationInterface

•15-6习题(Exercises)

15-1简介

•

•哈希(Hashing)是一种快速搜索的表类型，将搜

索键(SearchKeys)以哈希函数(HashFunction)

处理后，分置于各对应框(Buckets)，可达到直接

搜索的效率。

15-2基本概念(BasicConcepts)

•在搜索概念中，哈希(Hashing)是最快速的一种

搜索方式(Searching)，可直接搜索(Directly

Searching)，其搜索复杂度(Complexity)与数据

多少无关，均为O(1)。

范例137：设有一哈希函数(HashFunction)HF=

xMod10，试以此HF设计哈希表格索引(HashTable

Index)框(Bucket)。

范例138：参考范例137，设有数据搜索键K={3,

16,21,39}，试以哈希函数(HashFunction)HF=

xMod10创建哈希表格索引(HashTableIndex)框，

并安排数据哈希键(HashKeyofRecord)。

范例139：延续范例138，如果新增一个数据

搜索键51，试请更新其哈希结构(Hash

Structure)。

15-3操作哈希(OperationofHashing)

•

•一旦哈希函数(HashFunction)设定哈希表格索

引(HashTableIndex)框(Bucket)后，不再改

变索引框的结构，当有新增或删除数据搜索键时，

仅更新哈希链的结构。

范例141：参考范例140，设有数据搜索键K={69,

74,81,91,127,136,143,151}，哈希函数

(HashFunction)HF为3位(bits)序列，试请创建

哈希表索引框，并以各数据搜索键K之末端3位对应

i

哈希表格索引(HashTableIndex)，安排数据哈希

键(HashKeyofRecord)的位置。

范例142：延续范例141，将哈希索引框(Hash

IndexBucket)以最左端位0与1分段设置。

15-4HashtableClass

•

•java.util.Hashtable继承(extends)自

Dictionary→Object，此类对象可任何类型、

任何数量的数据、对象，称为元素(Elements)，

以一个搜索键(key)来识别或存取元素的内容。

范例143：试解释以publicHashtable(intca,float

fac)创建哈希表格的结构，令其中参数ca=16、fac=

0.5。

范例144：新建文件Ex15_4_1.java其功能为解释哈希实例方法

程序put(Objectkey,Objectvalue)的应用。

•

•01importjava.util.*;

•

•02clas15_4_1{

•03publicstaticvoidmain(String[]args){

•04Hashtableht=newHashtable();

•05ht.put(Server,newString(163.15.40.242));

•06ht.put(1,newString(163.15.40.243));

•07ht.put(2,newString(163.15.40.244))