散列表
1.直接寻址表
如图:关键字集合U={0,1,2,...,m-1},用一个数组T来表示,每个关键字指向一个数据,当然数据不一定是存满的,也就是说有些关键字可能会用不到。key表示已经存储数据的关键字集合。
当关键字的全域U比较小时,直接寻址是一种简单有效的技术。查找,删除等操作只需要O(1)时间。
如果U很大,要保存一个|U|大小的T显然是不可能的,实际情况是用到的关键字集合key对U来说可能很小,因而分配给T的大部分空间会造成浪费。这就好比腾讯有上亿的用户,但某一时间在线的用户可能只会是其中的一部分,如采用直接寻址法就会产生上述问题。
2.散列表
如果U很大,用散列表来解决上述问题。在直接寻址方式下key直接指向对应元素;在散列方式下,具有关键字key的元素处在hash(key)中。亦即,利用散列函数hash(),根据关键字key计算其hash(key)值,将元素存在hash(key)对应处。
这样,又产生了不同的key可能有相同的hash()值的冲突问题,这种情形称作碰撞。解决这个问题可用链接法和开发寻址法。
链表法就是将散列到同一位置处的元素放在一个链表中。链表是无序的,在查找一个元素时要遍历链表。
3.开放寻址法
在开放寻址法中,所有元素都在散列表中,当查找一个元素时,要查找所有表项,直到找到所需元素,或者最终发现不在表中。在这种方法中,散列表可能被填满,以至于不能插入任何新的元素,但装载因子绝对不会大于1。
下面是我写的代码,当产生冲突时用链表法解决:
每个元素用结点表示,关键字ID
public class StudentNode {
//学号
public String ID;
//子结点
public StudentNode child;
}
BKDRHash算法:
package hash.net;
/**
* BKDRHash算法
* @author wenxiaodong
*2012-10-20 下午04:55:21
*/
public class HashArithmetic {
//保存结点的数组
public StudentNode[] students=new StudentNode[20];
//BKDRHash算法,得到hash值
public int BKDRHash(String s){
//哈希值
int hash=0;
int seed=31;
int i=0;
while(i<s.length()){
hash=hash*seed+s.charAt(i);
i++;
}
return hash;
}
//添加结点的方法
public void put(String ID){
StudentNode sn=new StudentNode();
sn.ID=ID;
//得到hash值
int key=BKDRHash(ID)%20;
//如果此位置为空
if(students[key]==null){
students[key]=sn;
}else{//如果已经有元素了
sn.child=students[key];
students[key]=sn;
}
System.out.print("key值"+key);
}
//删除结点的方法
public void delete(String ID){
//得到hash值
int key=BKDRHash(ID)%20;
//如果此处元素不存在
if(students[key]==null){
System.out.println("此处元素为空");
}else{//此处存在元素
StudentNode s1 = null;
StudentNode s2=students[key];
while(s2!=null){
if(s2.ID==ID){
if(s1==null){
students[key]=s2.child;
}else{
s1.child=s2.child;
}
return;
}
s1=s2;
s2=s2.child;
}
}
System.out.println("要删除的元素不存在");
}
}
主函数:
public class TestMain {
public static void main(String args[]){
HashArithmetic ha=new HashArithmetic();
String str=new String();
for(int i=0;i<40;i++){
ha.put(str+i);
System.out.println(" ID:"+ha.students[ha.BKDRHash(str+i)%20].ID);
}
}
}
- 大小: 23.1 KB
分享到:
相关推荐
散列表的设计与实现,课程设计. 设计散列表实现电话号码查找系统。 【基本要求】 1) 设每个记录有下列数据项:电话号码、用户名、地址; 2) 从键盘输入各记录,分别以电话号码和用户名为关键字建立散列表; 3) 采用...
为小于n个关键字设计一个散列表,使得查找成功时平均查找长度,要求完成相应的散列表建立和查找。假设关键字为整型数据,散列函数用除留余数法,采用开放定址法的线性探测法处理冲突。 1.从键盘输入关键字个数n及...
散列表的设计与实现,课程设计. 设计散列表实现电话号码查找系统。 【基本要求】 1) 设每个记录有下列数据项:电话号码、用户名、地址; 2) 从键盘输入各记录,分别以电话号码和用户名为关键字建立散列表; 3) 采用...
设计散列表实现电话号码查找系统。基本要求:(1)设每个记录有下列数据项:电话号码、用户名、地址;(2)从键盘输入各记录,分别以电话号码和用户名为关键字建立散列表;(3)采用双散列法解决冲突;(4)查找并显示给定...
散列表是一种存储结构,是和链表,数组不同的存储结构,其存储位置是有存储数据而定的,本题中,有学生姓名、住址和电话号码,输入学生姓名,将拼音字母转化成阿克斯码,将所有的阿克斯码加起来与20取余数得到的数字...
散列表,也称为哈希表。根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置的表。 哈希函数的构造方法:1)...
5、散列表的设计与实现 任务:设计散列表实现电话号码查找系统。 要求: (1) 设每个记录有下列数据项:用户名、电话号码、地址; (2) 从键盘输入各记录,以用户名(汉语拼音形式)为关键字建立散列表; (3) ...
散列表散列表散列表散列表散列表散列表散列表散列表散列表散列表
Linux内核的实现,大量使用了数据结构,包括了数组、链表和散列表。其中用的最多的是双向循环链表。Linux内核使用的是自己定义的链表和散列表,简单而高效,使用方法也非常的别具一格。 研究Linux内核的链表和散...
数据结构课程设计,用散列表实现电话号码添加、查询,java语言,附软件截图,课程设计报告。
基本要求: (1)设每个记录有下列... (2)从键盘输入各记录,分别以电话号码和用户名为关键字建立散列表; (3)采用一定的方法解决冲突; (4)查找并显示给定电话号码的记录; (5)查找并显示给定用户名的记录。
数据结构课程设计 散列表的应用:插入买票
散列的C语言实现:链地址法、线性探测法、双重散列表
散列表在进行映射的时候经常会发生冲突,这里采用链接法来解决链接法映射冲突带来的问题
数据结构散列表编写的电话本及冲突处理源码,散列表,哈希表,存储数据,电话本,散列表,哈希表,存储数据,电话本
数据结构课程设计报告 题目1:基于散列表的程序相近度检测系统 ——采用的方法:哈希散列函数,二分查找 题目2:旅游交通查询系统 ——采用的方法:二维链表与图
设计散列表实现电话号码查找系统。 【基本要求】 1) 设每个记录有下列数据项:电话号码、用户名、地址; 2) 从键盘输入各记录,分别以电话号码和用户名为关键字建立散列表; 3) 采用一定的方法解决冲突; 4) 查找并...
在cuda上用gpu实现散列表 在cuda上用gpu实现散列表
一个用c语言编写的散列表通讯录系统,实现了增删改查功能。