一:对以往所学的简单数据结构回顾
学习程序语言时数组是我们首先接触到的数据结构。众所周知,数组在访问数据时通过下标可以及其快速的访问数据,但是在删除和插入时数组就表现的并不优越。
链表在数据的删除和插入时会很方便,但是不能达到对数据的快速访问。
那么有没有一种对两者进行综合的数据结构呢?
答案是肯定的。比如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. 红黑树数据结构和算法
数据结构Hash表C语言实现
数据结构常用算法c++实现,程序目录如下: Array shuffle Prime test(trial division) Prime test(Miller-Rabin's method) 2D Array Arbitary Integer Linear congruential generator Maximum subarray problem Bit...
散列表可以实现 O(1)的快速查找,用 Hash 数据结构作为底层存储结构较为合适。本系统应首先实现 Hash 表的基本结构和操作,在此基础上构建电话号码查找系统。电话号码查找系统包括若干数据项:电话号码、用户名、...
散列表可以实现 O(1)的快速查找,用 Hash 数据结构作为底层存储结构较为合适。本系统应首先实现 Hash 表的基本结构和操作,在此基础上构建电话号码查找系统。电话号码查找系统包括若干数据项:电话号码、用户名、...
数据结构中hash函数的实现,自己写的,VC平台。
[Cambridge University Press] 数据结构算法教程 (C# 实现) (英文版) [Cambridge University Press] Data Structures and Algorithms Using C# (E-Book) ☆ 图书概要:☆ C# programmers: No more translating ...
TestCuckooHashTable.cpp: Test program for cuckoo hash tables (need to compile CuckooHashTable.cpp also) CaseInsensitiveHashTable.cpp: Case insensitive hash table from STL (Figure 5.23) BinaryHeap.h:...
最快的排序算法 javahash实现-Java-哈希算法-最快的实现,排序算法数据结构
双向链表 - 数据结构与算法 C 双向链表 - 数据结构与算法 C 。。。。。。
主要对ADL语言、数据结构与算法、算法分析基础、OOP、和C++做了简单介绍 基本数据结构 基本数据结构部分包括线性表、堆栈与队列、数组、字符串、整数集合类、树(包括AVL树、伸展树等)、图(包括网络流等问题的讨论...
常⽤的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所⽰: 线性表和⾮线性表 ⼀、线性表 常见的线性表有:数组、队列、栈、链表 线性表是最基本、最简单、也是最常⽤的⼀种数据结构。线性表...
针对本班的人名设计一个杂凑表,数据表的长度为50~80个记录;分析平均查找长度,完成相应的建表和查表程序,设计直观的界面显示杂凑表的内容。
2.编写程序实现Hash表的建立、删除、插入以及查找操作。 程序应包含的主要功能函数有: Hash( ):计算哈希地址 InitialHash( ):初始化哈希表 SearchHash( ):在哈希表中查找关键字 InsertHash( ):向哈希表中...
数据结构:映射 数据结构:映射 我们通常所⽤的map其实就是⼀棵红⿊树,如果有平衡树问题能够⽤它来解决⼀定要⽤,不要⼿写了,因为红⿊树的效率是⾮常棒的 先看⼏个定义: map,int> m1; map,map,int> >m2; multiset...
2.自己定义数据结构,写出程序:二叉树的前序遍历。 3.实现双向链表删除一个节点P,在节点P后插入一个节点,写出这两个函数。 4.下面哪种排序法对12354最快 a quick sort b.buble sort c.merge sort 5.哪种...
现在只能实现关键字为数字,存储单位为为字符串类型的,给大家简单的提供下HASH表的存储原理
理解内存页面调度的机理,掌握几种理论调度算法实现,并通过实验比较各种调度算法的优劣。此外通过实验了解HASH表数据结构的使用。
/* 实验任务: (1) 设计算法创建二叉排序树,按照中序遍历输出数据;查找指定元素,给出结点地址,给出比较次数。 (2) 采用除留余数函数实现散列(哈希)存储,某种方法解决冲突。 */
包含C#面向对象数据结构(基于数组的表,链表,二叉树,队列,二叉搜索树,AVL平衡树,hash表等)的实现。全是自己写的,都测试过.