数据结构之-----简单哈希
看到题目可能很多很并不是那么熟悉，数据结构中的哈希用的比较少。但是要是说数组（队列）或者链表可能大家会感觉好一点，毕竟这是我们在编程中经常使用的一些数据结构。
本篇文章主要介绍一个简单的hash结构，为了能使这边文章读起来不那么的费力。我会从大家都熟悉的数组和链表过度到一个简单哈希的构造。
数组的优点：
数组的优势在于他的查找方便，只要用下标的索引便能非常快速又方便的找到数组中下标对应的我们存储在数组里的东西。
数组的缺点：
数组的一个很大的缺点就是，在实例化一个数组必须给它分配相应的内存空间，也就是说一个数组创建好了他的大小就固定了。这样就会产生问题：初始化的内存空间小，存储的数据就少。而初始化的空间过大，又会造成空间的浪费。而我们学过的队列能够解决其中的一些问题，队列是对数组的封装操作，实现数组长度的动态增删。队列实质里也是用一个数组在存储着数据，所以数组存在的一些问题它并没有解决。比如存储的数据很大的时候用队列实现不了（在最后存储的时候也是用一个非常大的数组来存储，这个问题和数组是一样的）。
队列的缺点：
队列的缺点还有删除和插入数据，或许用代码由于我们封装好的代码这些操作只要一句代码便能执行，但其内部的工作量是非常大的，用过对列的人都知道，向队列中任意插入一个数据，比如插在队列中索引值对应为0的位置，这会造成后边所有数据的位置都要往后移动一个位置。这样会使整个程序的效率下降。
链表的优点：
而对于链表优势弥补了队列在增删数据时的缺点。链表在删除和增加数据逇时候，只要改变相应节点的指向便可。
链表的缺点：
但是链表却没有了数组的优势，查找是链表的一个缺点。每次查找都要遍历链表。
为什么用hash？
既然两者都有优点，那么我们是否能将两者的优点结合在一起。答案是可以的。
结合两者的想法（思考）：
队列是对数组的封装操作。那么要是我们将数组和链表封装在一起操作就能很巧妙的将数组和链表的优势结合在一起。而本文要介绍的简单hash也就是用这种方法来实现的。
我们一起来想想，要是有那么一个数组，数组中存储的是一个节点，节点下面是是他的一个个子节点，这样数组和链表就结合了。那么这样的结构相比于上面所说的有什么优点呢？下面我就来说说他的优点。
1.利用数组的下标，我们可以很快的找到下标对应的一串链表。（数组的优点）
2.由于数据用的是节点来存储，那么在增删数据的时候链表的优势也就充分体现了。（链表的优点）
3.单单只看数组，有了下面挂着的链表能够存储的数据量大了。（相比于只有数组的时候）
想法中产生的问题：
这边有一个问题，在查找的时候虽然能够很快的找到相应链表，但在整串的链表中要去查找我们需要的数据，要是链表过长的话，那么链表查找的弊端就会显现出来。为了避免这种情况。我们要设定一个阀值，当数据存储量与数组长度的比大于某个值的话那么句增大数组的长度，然后按照存储数据的方法将已存的数据再次存入。这样就会避免某串链表过大了。
实现：
下面介绍如何用编程来实现我们上面的所想：
如何将一个数据存入，要存入的数据要带一个关键字，（关键字必须不一样）
下面以存储qq用户信息为例。
qq号都是不一样的。所以可以用qq号来作为要存储用户信息的关键字。
每个qq号通过一个映射对应到数组的下标。这个映射就是一个hash算法，当然这个算法由我们来自己设定。但是不能通过映射后获得的数组下标越界这种情况。
增加：
我们简单定义这个算法为除以数组长度取余，余数作为我们映射得到的数据。
1.所以定义int hash（）方法，返回的到的映射值
//属性boolean is_searched=false;
boolean is_removed=false;
boolean is_reseted=false;
//声明节点数组
private Node[] array;
//声明数组长度
private int size;
//声明阀值
private double fa_value=0.8;
//声明输入数据量属性
private int sum=0;
/**
* 定义hash算法
* @param qq
* @return
*/
private int hash(QQ qq){
return qq.getNumber()%size;
}
2.有了通过映射获取的数组下标，就可以存储数据了。
若该值对应的数组元素空（表示该位置没有存储数据），数据可以存入，实例化一个节点并将数据设置为给节点属性值，然后将节点存入数组该位置。
若不为空（表示已经有了数据），则判断该不为空的数组元素（即节点）的字节的是否为空，为空的话同样就在实例化一个节点，并作为子节点存入。若不为空，则再往下面的子节点判断。直至判断到有空的位置再将数据粗如（这边可以用递归或者循环）。/**
* 增加数据的方法
* @param qq
* @return
*/
public boolean add(QQ qq){
//判断是否要扩张数组空间
if(((double)sum/size)>fa_value){
rehash();//防止节点过长，重置数组
}
//计算qq号对应的数组下标
int index = hash(qq);
//判断node是否为null
if(array[index]==null){
//如果为空将该QQ对象加入
array[index]=new Node(qq);
sum++;
return true;
}else{
is_kong(array[index], qq);
return true;
}
}
/**
* 如果子节点为空，就实例化一个节点并存入数据。不为空就判断下一个节点
* @param node
*/
private void is_kong(Node node,QQ qq){
if(node.getNext()==null){
//如果为空就实例化一子节点并存入数据
Node childnode=new Node(qq);
node.setNext(childnode);
System.out.println("存入子节点了");
sum++;
}else{
//如果不为空就取下一个节点
is_kong(node.getNext().getNext(),qq);
}
}
/**
* 重置array
*/
private void rehash(){
sum=0;
//实例化一个数组，长度为原来数组的两倍
size*=2;
Node[] array2=new Node[size];
Node[] array3=array;
array=array2;
//遍历原来的数组
for(int i=0;i<array3.length;i++){
//取出原来数组中的有存储数据的节点
if(array3[i]!=null){
add(array3[i].getData());
}
}
}
查找：
不用说当然是利用关键字qq号，作为查找的依据来查找用户信息了。
1.利用qq号，通过hash算法获取的映射值，找到相依的数组元素（为一个节点，也可以理解成是一个长链），那么我们要查找的数据毕在这个节点，或者节点下面的子节点中。除非这个数据不存在这个结构里面。
2.同样取出根据下标找到数组元素，判断该元素是否为空。
不为空则判断是否节点的数据属性一样，要是一样那么就找到了。要是不一样，就往后面的子节点找。
直至到连的结尾。为空的话作出判断该用户信息不存在。
要是根据下面获取的元素为空，可作出判断，该用户信息不存在。/**
* 根据qq号码查询用户
* @param qqnumber
*/
public boolean search(int qqnumber){
is_searched=false;
//遍历数组
for(int i=0;i<array.length;i++){
if(array[i]!=null){
//如果qq号相等
if(array[i].getData().getNumber()==qqnumber){
System.out.println("你查询的用户名字是："+
array[i].getData().getName()+" " +
"qq号是："+array[i].getData().getNumber());
is_searched=true;
}else{
bianli(array[i].getNext(),qqnumber);
}
}
}
return is_searched;
}
/**
* 遍历数组节点子节点
* @param node
*/
private void bianli(Node node,int qqnumber){
//如果子节点不为空
if(node!=null){
//如果qq号相等
if(node.getData().getNumber()==qqnumber){
System.out.println("你查询的用户名字是："+
node.getData().getName()+" " +
"qq号是："+node.getData().getNumber());
is_searched=true;
}else{
//如果qq号不相等
bianli(node.getNext(),qqnumber);
}
}
}
删除：
1.和查找是一样的。找到数据的时候，要是存储数据的节点有子节点，用子节点代替该节点就行了。
/**
* 根据qq号删除用户
* @param qqnumber
*/
public boolean remove(int qqnumber){
is_removed=false;
//遍历数组
for(int i=0;i<array.length;i++){
if(array[i]!=null){
//如果qq号相等
if(array[i].getData().getNumber()==qqnumber){
if(array[i].getNext()==null){
//如果数组没有子节点
array[i]=null;
is_removed=true;
}else{
array[i]=array[i].getNext();
}
}else{
bianli2(array[i],qqnumber);
}
}
}
return is_removed;
}
/**
* 遍历数组节点子节点
* @param node
*/
private void bianli2(Node node,int qqnumber){
//如果子节点不为空
if(node.getNext()!=null){
//如果子节点qq号相等
if(node.getNext().getData().getNumber()==qqnumber){
node.setNext(node.getNext().getNext());
System.out.println("删除成功！！");
is_removed=true;
}
}else{
return;
}
}
修改：
有了上面这些这个就简单了。查找到相应数据对应的节点，改变节点数据属性就ok了。/**
* 根据qq号更改用户信息
* @param qqnumber
*/
public boolean reSet(int qqnumber,String newname){
is_reseted=false;
//遍历数组
for(int i=0;i<array.length;i++){
if(array[i]!=null){
//如果qq号相等
if(array[i].getData().getNumber()==qqnumber){
array[i].getData().setName(newname);
is_reseted=true;
}else{
bianli3(array[i],qqnumber,newname);
}
}
}
return is_reseted;
}
/**
* 遍历
* @param node
* @param newname
*/
private void bianli3(Node node,int qqnumber,String newname){
if(node.getNext()!=null){
if(node.getNext().getData().getNumber()==qqnumber){
node.getNext().getData().setName(newname);
is_reseted=true;
}else{
bianli3(node.getNext().getNext(),qqnumber,newname);
}
}else{
return ;
}
}
分享到：
相关推荐
数据结构是计算机科学中的核心课程之一，它主要研究如何在计算机中组织和管理数据，以提高数据处理的效率。在“北大信息院数据结构--张铭”这门课程中，我们将深入探讨各种经典的数据结构及其应用，这是一份包含全部...
在这个“数据结构课设--简单的职工管理系统”项目中，我们将深入理解并应用一些基本的数据结构，如数组、链表、栈、队列、树以及哈希表，来构建一个实际的应用系统。 首先，职工管理系统的核心功能可能包括员工信息...
哈希表是一种高效的数据结构，它通过特定的哈希函数将键（key）映射到一个固定大小的数组中，以此实现快速的插入、查找和删除操作。在本数据结构课程设计中，任务是设计一个哈希表来存储30个人的汉语拼音姓名，要求...
数组是最简单的一种数据结构，它提供了一种方式来存储和访问固定大小的数据集合。链表则允许我们在内存中不连续的位置存储元素，通过指针链接它们。队列是一种先进先出（FIFO）的数据结构，常用于任务调度和数据缓冲...
数据结构是计算机科学中的核心课程之一，主要研究如何在计算机中高效地组织和存储数据，以便于进行各种操作。严蔚敏教授是中国计算机科学领域的知名学者，他的《数据结构》教材在国内具有广泛的影响力，被许多高校...
常见的数据结构包括数组、链表、栈、队列、树（二叉树、平衡树、堆）、图以及哈希表等。每种数据结构都有其独特的特点和适用场景。 1. **数组**：数组是最基础的数据结构，它是一组相同类型元素的有序集合。通过...
哈希表，又称散列表，是一种非常重要的数据结构，它以高效的方式实现了数据的存储和检索。在C语言中，由于没有内置的哈希表实现，程序员需要自定义数据结构来构建哈希表。本教程将深入探讨如何利用C语言构建和操作...
哈希表是一种高效的数据结构，它通过特定的函数——哈希函数，将任意大小的键（key）映射到一个固定大小的数组索引上，从而实现快速的查找、插入和删除操作。在C语言中实现哈希表，我们需要理解以下几个关键概念和...
哈希表，又称散列表，是数据结构与算法领域中的一种重要存储结构，它通过将关键字映射到数组的特定位置来实现快速访问。在本资料中，虽然讲师的表述可能并非尽善尽美，但依然能为我们提供有价值的哈希表学习资源。 ...
### 数据结构核心知识点详解 #### 一、绪论 ##### 1. 数据结构与抽象数据类型 - **数据结构**：研究数据元素之间的逻辑关系和物理存储方式。 - **抽象数据类型(ADT)**：对数据类型的一个抽象描述，包括数据对象、...
【数据结构学习---查找】 在计算机科学中，查找是一种基本的操作，用于在数据集合中寻找特定元素。本节主要探讨四种查找算法：顺序查找、二分查找、分块查找和哈希查找，以及如何根据实际情况选择合适的查找方法。 ...
数据结构-Java实现一个简单的哈希表结构SingleHashMap，对了解哈希表的原理比较有帮助。
在数据结构实习项目“简单迷宫系统”中，我们主要探讨和应用了计算机科学中的核心概念，特别是与数据结构和算法相关的知识。这个项目旨在帮助学生深入理解如何使用不同的数据结构来解决实际问题，比如构建和求解迷宫...
哈希表是一种高效的数据结构，它通过哈希函数将键（在这个案例中是人名的汉语拼音）映射到数组的索引位置，以实现快速的插入和查找操作。 1. **问题描述**： - 主要任务是为30个人名建立哈希表，其中名字以汉语...
在IT领域，特别是数据结构与算法中，哈希函数扮演着至关重要的角色。它们被广泛应用于各种场景，如数据库索引、密码存储、缓存管理等，以提高数据检索的速度和效率。本文将深入探讨几种常用的哈希函数，包括SDBMHash...
### 数据结构中的哈希表查找 #### 哈希表简介 哈希表（Hash Table）是一种基于数组的数据结构，它通过将关键字映射到数组的某个位置来存储和检索数据，这种映射过程通常由一个哈希函数完成。哈希表能够实现快速的...
在数据结构的选择上，可能使用数组、链表、树或者哈希表等来存储图书信息，如书名、作者、出版日期、ISBN号等。对于快速查询，哈希表可能是理想选择，因为它能提供常数时间的查找速度。同时，为了实现借阅功能，可能...
数据结构是计算机科学中的核心课程，它探讨了如何在计算机中高效地组织和管理数据，以便于进行各种操作。湖南大学的数据结构期末试题涵盖了这门课程的重要概念和技术，旨在检验学生对这些知识的理解和应用能力。以下...
数据结构是计算机科学中的核心课程，它探讨了如何在计算机中高效地组织和操作数据。在山东大学软件学院2018-2019的数据结构考试中，涉及了线性结构、层次结构和网状结构这三个关键概念。 **线性结构**： 1. 线性表...