一:对以往所学的简单数据结构回顾
学习程序语言时数组是我们首先接触到的数据结构。众所周知,数组在访问数据时通过下标可以及其快速的访问数据,但是在删除和插入时数组就表现的并不优越。
链表在数据的删除和插入时会很方便,但是不能达到对数据的快速访问。
那么有没有一种对两者进行综合的数据结构呢?
答案是肯定的。比如Hash数据结构就可以即拥有数组的优点又可以实现链表的优点。
那么我们就简单的介绍一下什么是Hash,并实现一个简单的Hash结构
二:Hash的简单介绍
Hash:Hash就是将任意长度的输入通过散列算法得到固定长度的输出,该输出即为散列值。
其中得到散列值的方法极为散列函数。散列函数可以得到存储元素的存储位置。
例如:向数组中存入数据 200,如果直接将200作为数组的元素值存储(比如array[i]=200),则在查找的时候需要遍历数组并判断某一位置是否是200。
这样的存储方法在查找在数据比较多的时候会比较浪费时间。
那么我们可以通过某一函数,获得该元素所在位置的索引,那么在查找的时候只需获得该索引位置的数据即可。
比如:
int index = H(存入的元素);
其中index 即为获得的索引。而该函数即为散列函数。
常用的构造散列函数的方法如下:
1:直接寻址法
2:数字分析法
3:平方取中法
4:折叠法
5:随机法
6:除留取余法:取关键字被某个不大于散列表长度的数P除后所得的余数为散列地址。例如关键字200,取P=30;余数20即为关键字200的散列地址。
三:用除留取余法实现一个简单的Hash结构
聪明的你肯定会想到在做除留取余时可能会出现具有相同散列地址的情况。
为了处理这一问题我们就需要将数组和链表联合使用了。
其中数组存储链表,而链表存储元素。
依然用除留取余法获得元素的索引,若有相同的散列地址则将该数据添加到该位置处链表中
那么我们首先定义一个节点类
package hashV3;
public class DataNode {
public int member;
public DataNode next;
}
定义一个链表并实现数据的添加和删除
package hashV3;
public class MyHash {
private DataNode[] array = new DataNode[100];
private int getHash(DataNode node){
int index = node.member%10;
return index;
}
/**
* 添加元素
* @param node
*/
public void add(DataNode node){
int index = this.getHash(node);
if(array[index] == null){
array[index] = node;
}else{
node.next = array[index];
array[index] = node;
System.out.println("====--->>>>"+node.member);
}
}
public boolean remove(DataNode node){
int index = this.getHash(node);
if(node == null || array[index]==null){ //如果删除的数据为空
return false;
}
DataNode temp = array[index];
if(temp.member==node.member){//如果删除的是第一个数据
array[index] = temp.next;
}
while(temp.next.member != node.member && temp.next!=null){
temp = temp.next;
}
temp.next = temp.next.next;
return true;
}
/**
* 打印数据
*/
public void print(){
for(int i=0; i<array.length; i++){
if(array[i]!= null){
DataNode node = array[i];
while(node != null){
System.out.println(" "+node.member);
node = node.next;
}
}
}
}
}
则在主函数中实现数据的添加和删除
package hashV3;
import java.util.Random;
public class HashMain {
public static void main(String[] args){
HashMain h = new HashMain();
h.add();
h.remove();
}
/**
* 添加方法
*/
private void add(){
MyHash hash = new MyHash();
Random rand = new Random();
for(int i=0; i<10; i++){
int a = rand.nextInt(4);
DataNode node = new DataNode();
node.member = a;
hash.add(node);
}
hash.print();
}
/**
* 删除方法
*/
private void remove(){
MyHash hash = new MyHash();
DataNode n = new DataNode();
n.member = 2;
hash.remove(n);
System.out.println("************************************************");
hash.print();
}
}
分享到:
相关推荐
java 集合和泛型 1. Map接口 2. HashMap底层实现 3. Hash数据结构和算法 4. 红黑树数据结构和算法
严蔚敏教授的《数据结构》是一本广受欢迎的教材,它详细介绍了各种数据结构及其算法,并提供了C语言的实现示例。 在这份压缩包中,你将找到对以下关键数据结构的C语言实现: 1. **线性结构**: - **数组**:基础...
此外,哈希表(Hash Table)是另一种重要的数据结构,它通过散列函数实现快速的查找、插入和删除操作,达到近乎恒定的时间复杂度。而堆(Heap)是一种特殊的树形数据结构,通常用于实现优先队列,例如在排序算法(如...
本资源包“PHP各种数据结构实现”提供了一系列独立的PHP文件,用于实现常见数据结构,使得开发者无需从零开始,能快速理解和应用这些数据结构。 1. 数组(Array):PHP中的数组是最基础的数据结构,可以存储一系列...
图书管理信息系统的设计与实现数据结构课程设计报告 本设计报告的目的是设计和实现一个图书管理信息系统,使用数据结构课程设计报告作为设计的基础。该系统的主要功能包括图书采编、图书编目、图书查询及图书流通...
哈希表,又称散列表,是数据结构课程中一种高效的数据组织方式,它通过特定的函数(哈希函数)将键(key)映射到数组的特定位置来实现快速访问。这种数据结构允许我们以接近常数时间的复杂度进行插入、删除和查找...
本项目提供了用C语言实现的一些数据结构小程序,这些程序可以帮助我们更好地理解数据结构及其应用。让我们深入探讨一下这些话题。 首先,"银行业务模拟"是一个常见的问题,它通常涉及到队列(Queue)数据结构。队列...
数据结构Hash表C语言实现
7. **哈希表(Hash Table)**:哈希表是一种通过哈希函数来实现快速查找的数据结构,它允许将键映射到特定的位置以存储数据,从而实现平均时间复杂度为O(1)的查找性能。冲突解决策略包括链地址法、开放寻址法等。 ...
本主题主要关注如何利用STL实现常见的数据结构,如栈、链表、散列以及各种排序和查找方法。这对于C++实习生来说,是必须掌握的基础技能。 首先,让我们来探讨栈(Stack)。栈是一种后进先出(LIFO)的数据结构,STL...
在这个"数据结构源码JS实现.zip"压缩包中,包含了多种经典数据结构的JavaScript实现,这对于理解和掌握这些概念至关重要。以下是对每个文件内容的详细解释: 1. **二叉搜索树**(Binary Search Tree, BST):这是一...
《数据结构》算法实现及解析_高一凡.pdf这本书很可能包含了以上知识点的代码实现,对于初学者来说,通过阅读和实践这些代码,可以加深对数据结构的理解,提升编程技能。在实际工作中,理解和熟练运用数据结构是解决...
数据结构常用算法c++实现,程序目录如下: Array shuffle Prime test(trial division) Prime test(Miller-Rabin's method) 2D Array Arbitary Integer Linear congruential generator Maximum subarray problem Bit...
此外,哈希表(Hash Table)是一种提供快速查找的数据结构,通过散列函数将键映射到数组的特定位置,实现常数时间的查找。堆(Heap)是一种特殊的树形数据结构,通常用于实现优先队列,如最大堆和最小堆。 排序算法...
总之,李春葆教授的《数据结构教程》上机实验源代码是一个宝贵的资源,它提供了亲自动手实现和调试数据结构的机会。通过深入学习和实践这些代码,不仅可以巩固理论知识,还能提升编程技能,为未来在计算机科学领域的...
在Python中,虽然我们有丰富的内置数据结构,如列表、字典、集合和...下面我们将实现一些常见的基础数据结构,包括栈(Stack)、队列(Queue)、链表(Linked List)、哈希表(Hash Table)和二叉树(Binary Tree)。
在"广工计算机数据结构课程设计之电梯模拟"这个项目中,学生们被要求运用所学的数据结构知识来实现一个电梯模拟系统。这个设计不仅检验了学生的编程技能,更重要的是锻炼了他们对数据结构的理解和应用能力。 电梯...
本主题主要围绕JavaScript实现常见数据结构进行详细探讨。 首先,我们来了解一些基本的数据结构类型: 1. 数组(Array):JavaScript中的数组是最常用的数据结构之一,它可以存储多个元素,并通过索引来访问。数组...
在ActionScript(AS)中实现数据结构是编程基础的重要部分,尤其对于开发高效且优化的Flash应用程序至关重要。数据结构是组织、存储和处理数据的特定方式,它为算法设计提供了基础。以下是一些AS中常见数据结构的...
殷人昆教授的《数据结构》是一本深受读者喜爱的教材,由清华大学出版社出版,它深入浅出地介绍了数据结构的概念,并提供了C++语言的实现,帮助读者更好地理解和应用这些概念。 在C++中实现数据结构,我们需要了解...