但是我们想想为什么会有这种问题?因为我们给每一个单词都分配了一个数组单元,而类似aaaa,zzzz这样的
单词显然是不存在的,因此我们有了一个最常用的哈希化的方法,“取余法”。50000个单词,但我们给它分
配一个容量为100000的数组,我们先将单词转化为10进制数字largeNumber,则 arrayIndex = hugeNumber
% arraySize;
哈希化其实是一种压缩,是压缩就必定要付出代价,也就是不能保证每个单词都能有自己的空白数组单元,
这也就是我们所说的“哈希冲突”。我们有两种方法解决冲突,一种是给冲突的数据再找一个空白数组单元,
叫做“开放地址法”,第二种是创建一个存放链表的数组,将所有冲突数据放到对应位置的链表中,这叫做
“链地址法”。
而开放地址法又有线性探测、二次探测和再哈希法。线性探测比较简单,就是依次向下寻找空白数组单元。
简单写一下线性探测的插入数据的java代码:
public int hashFunc(int key){
return key % arraySize;
}
public void insert(DataItem item){
int key = item.getkey();
int hashVal = hashFunc(key);
while(hashArray[hashVal] != null && hashArray[hashVal] != -1){ //-1指的是被删除过数据
hashVal ++; 项的数组单元
hashVal %= arraySize; //如果有必要则返回数组初始部位继续查询
}
hashArray[hashVal] = item;
}
当哈希表的数据项接近于填满哈希表时,会产生一种不好的现象“聚集”,这会使得哈希表处理数据的速度大大
下降,二次探测能有效避免聚集,假如线性探测的过程是x+1,x+2,x+3....那么二次探测的过程就是x+1,x+4,x+9.....
但是这样具有相同的哈希化后的值的数据又会产生“二次聚集”,因此我们又有了再哈希法,也就是将关键字用不同的
哈希函数再哈希化一边将结果作为探测的“步长”。现在已知一个哈希函数能很好满足这个想法:stepSize = constant - (key % constant);
其中constant是小于数组容量的一个质数。下面我简单写下代码来体现这一方法如何插入数据:
public void insert(DataItem item){
int key = item.getKey();
int hashVal = hashFunc1(key);
int stepSize = hashFunc2(key); //hashFunc2为再哈希化的哈希函数
while(hashArray[hashVal] != null && hashArray[hashVal] != -1){
hashVal += stepSize;
hashVal %= arraySize;
}
hashArray[hashVal] = item;
}
“链地址法”的意思就是让数组里面存储的不是数据项而是链表下面用一个图来展示:
public void insert(Link theLink){
int key = theLink.getKey();
Link previous = null;
Link currunt = first;
while(currunt != null && key > current.getKey()){
previous = current;
current = current.next;
}
if(previous == null)
first = theLink
else
previous.next = theLink;
theLink.next = current;
}
相关推荐
哈希表的建立和查找哈希表的建立和查找哈希表的建立和查找哈希表的建立和查找
对一批关键字集合采用开放定址哈希表的存储结构来建立相应的哈希表和完成查找过程。 (1) 熟练掌握哈希表的构造方法 (2) 理解哈希表与其他结构表的实质性差别。
/为班级30个人的姓名设计一个哈希表,假设姓名用汉语拼音表示。要求用除留余数法 构造哈希函数,用线性探测再散列法处理冲突,平均查找长度的上限为2。 编写数据结构和算法来实现。要求:将哈希函数和处理冲突方法...
哈希表应用 设计哈希表实现图书查找系统,完成相应的建表和查表程序。从键盘输入各图书相关信息,分别以图书编号为关键字建立散列表。待填入哈希表的书号至少30个;构造合适的哈希函数。 (1)记录由外部输入。 (2...
哈希表设计程序设计+数据结构实验报告 1.1 针对某个集体中的人名设计一个哈希表,使得平均查找长度不超过R,完成相应的建立和查表程序. 1.2 人名为汉语拼音形式,最长不超过18个字符(如:庄双双 zhuangshuangshuang)...
////采用除留余数法定义哈希表,哈希表长度为10,哈希函数为H(key)=key%13。产生冲突时采用线性探测法实现下面要求的功能。 ////(1)初始化哈希表,置空哈希表 ////(2)在哈希表中查找元素 ////(3)在哈希表中...
哈希表课程设计数据结构实验报告——哈希表设计 针对某个集体中的人名设计一个哈希表,使得平均查找长度不超过R,完成相应的建立和查表程序. 1.2 人名为汉语拼音形式,最长不超过18个字符(如:庄双双 ...
哈希表的概念作用及意义,哈希表的构造方法
哈希表的设计与实现课程设计 问题描述:针对某个单位电话号码簿,设计一个哈希表,并完成相应的建表和查表程序。 基本要求:设每个记录有下列数据项:电话号码、用户名、住址。从键盘输入各记录,以用户名为关键字...
哈希表的设计与实现——链地址法 问题描述: 设计哈希表实现电话号码查找系统。 基本要求: (1)设每个记录有下列数据项:电话号码、用户名、地址; (2)从文件中读取各记录,分别以电话号码和用户名为关键字建立...
问题描述:针对某个单位电话号码簿,设计一个哈希表,并完成相应的建表和查表程序。 基本要求:设每个记录有下列数据项:电话号码、用户名、住址。从键盘输入各记录,以用户名为关键字建立哈希表,哈希函数用除留取...
用C语言实现的哈希表设计,内有姓名列表,只要输入姓名就可得到查到在哈希表中的相应位置
假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。
哈希表的设计与实现。设计哈希表实现电话号码查询系统。基本要求:(1)设每个记录有一列数据项:电话号码、用户名、地址(2)从键盘输入各记录,分别以电话号码和用户名为关键字建立哈希表;(3)采用再哈希法解决...
简单哈希表模型。可以助你更好的完成哈希表相关的编程。
哈希表的设计与实现哈希表的设计与实现哈希表的设计与实现
针对某个集体(比如你所在的班级)中的“人名”设计一个哈希表,使得平均查找长度不超过R,完成相应的建表和查表程序。 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2...
哈希表的建立与运用C语言实现哈希表的建立与运用C语言实现哈希表的建立与运用C语言实现哈希表的建立与运用C语言实现哈希表的建立与运用C语言实现
初始化哈希表 清空哈希表 哈希函数 在哈希表中查找元素 在哈希表中插入一个元素 输出哈希表中所有元素
哈希表相关操作实现。对应讲解的博客地址:http://blog.csdn.net/ns_code/article/details/20763801