散列表
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. 散列表概念 散列表,又称哈希表,是一种基于数组结构的数据结构。它通过哈希函数将一组关键字映射到一个有限的连续地址集(即数组索引范围),并将这些关键字作为...
【作品名称】:基于 C/C++语言散列表实现的通讯录系统(课程设计报告+源码) 【适用人群】:适用于希望学习不同技术领域的小白或进阶学习者。可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【项目...
散列表的设计与实现,课程设计. 设计散列表实现电话号码查找系统。 【基本要求】 1) 设每个记录有下列数据项:电话号码、用户名、地址; 2) 从键盘输入各记录,分别以电话号码和用户名为关键字建立散列表; 3) 采用...
散列表,又称哈希表,是计算机科学中一种非常重要的数据结构,用于高效地存储和检索数据。在本课程设计中,我们将深入探讨散列表的原理、设计与实现,涵盖其核心概念、常见算法以及实际应用。以下是关于散列表的详细...
在这个特定的课设中,我们关注的是散列表的设计与实现,这是一种高效的数据结构,提供了近似于常数时间的查找、插入和删除操作。散列表,也称为哈希表,是通过将关键字映射到数组索引来实现的,这种映射过程通常由...
散列表在IT领域中是一种非常重要的数据结构,它在实现高效的数据存储和查找方面发挥着关键作用。在“用散列表写的通讯录管理系统”中,我们可以深入探讨如何利用散列表来构建一个快速、灵活的联系人管理解决方案。 ...
散列表,又称哈希表,是数据结构中一种高效存储和检索数据的结构。它通过散列函数将关键字映射到数组的特定位置,实现快速的插入、删除和查找操作。在本系统的描述中,我们可以看到一系列与散列表操作相关的功能: ...
散列表,亦称为哈希表,是一种在数据结构中占据重要地位的结构,其核心在于使用散列函数将数据的键值映射到一个有限的整数集合,并根据这个映射值确定数据在存储结构中的位置。这种设计使得数据的查找、插入和删除...
散列表(Hash Table)是一种数据结构,用于存储键值对,通过特定的散列函数将键(Key)转化为数组索引,实现快速访问。在实际应用中,由于散列函数的不完美,不同键可能会被映射到相同的索引位置,这种现象称为...
#### 一、基于散列表的程序相近度检测系统 **1. 需求分析** 对于两个C程序,需要设计并实现两种不同的基于散列表的检测算法,来计算这两个程序的相近度。具体来说,算法应该能够分析两个程序中的关键字出现频率,并...
散列表是一种存储结构,是和链表,数组不同的存储结构,其存储位置是有存储数据而定的,本题中,有学生姓名、住址和电话号码,输入学生姓名,将拼音字母转化成阿克斯码,将所有的阿克斯码加起来与20取余数得到的数字...
在本课程设计中,主要目标是构建一个基于散列表的电话号码查询系统,该系统能够高效地存储和检索用户信息,特别是电话号码。散列表作为一种数据结构,通过散列函数将键(如人名)映射到数组的特定位置,以此实现快速...
散列表是一种高效的数据结构,它通过哈希函数将键(key)映射到数组的索引位置,从而实现快速的查找、插入和删除操作。在这个电话号码查找系统中,散列表被用来存储电话号码和用户名作为关键字的记录,每个记录包含...
哈希表,也被称为散列表,是数据结构中一种高效的数据存储方式,它通过特定的哈希函数将关键字映射到一个固定大小的数组中,从而实现快速的查找、插入和删除操作。在IT领域,理解和掌握哈希表的实现方式至关重要,...
电话号码查找系统是一种高效的数据检索工具,通过使用散列表(哈希表)来存储和查找用户信息,如电话号码、用户名和地址等。在C语言中实现这样的系统,需要掌握以下关键知识点: 1. **数据结构**:首先,我们需要一...
散列表通讯录系统是一种高效的数据管理系统,主要用于存储和检索个人联系信息。在C语言中实现这样一个系统,可以深入了解数据结构和算法的应用。本文将详细探讨散列表通讯录系统的实现原理、设计思路以及C语言编程中...