`
lixiongzhi_m
  • 浏览: 60651 次
  • 性别: Icon_minigender_1
  • 来自: 福建
社区版块
存档分类
最新评论

数据结构之-----简单哈希

阅读更多
          数据结构之-----简单哈希
           看到题目可能很多很并不是那么熟悉,数据结构中的哈希用的比较少。但是要是说数组(队列)或者链表可能大家会感觉好一点,毕竟这是我们在编程中经常使用的一些数据结构。
           本篇文章主要介绍一个简单的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 ;
		}
	}
分享到:
评论

相关推荐

    数据结构--数据结构的组织方法.pdf

    (数据结构+算法) 解答: 数据结构:简单地说,数据结构是以某种特定的布局⽅式存储数据的容器。这种"布局⽅式"决定了数据结构对于某些操作是⾼效的,⽽对 于其他操作则是低效的。⾸先我们需要理解各种数据结构,...

    【数据结构】 - 哈希表-易语言

    仅供学习, 如果觉得效率可以的话可以直接使用 有能力自己优化, 方法不多, 思路简单 源码讲解, 哈希表实现原理视频 : https://bbs.125.la/thread-14529427-1-1.html

    数据结构哈希表C语言

    很简单的一个.........................................................

    精心整理史上最全的数据结构flash演示动画,共5个版本,祝大家考研成功!

    \数据结构flash演示\版本1\4-3-1串的简单匹配.swf \数据结构flash演示\版本1\4-3-2串的模式匹配1.swf \数据结构flash演示\版本1\4-3-3串的模式匹配2.swf \数据结构flash演示\版本1\4-3-4-1串的模式匹配next.swf ...

    数据结构(C#语言版)

    非常清晰易懂的C#数据结构描述。目录如下: 数据结构(C#语言版) -------------------------------------------------- 前 言 1 -------------------------------------------------- 目录 3 ----------------------...

    C语言版数据结构与算法分析-严蔚敏经典视频教程

    01-001数据结构的概念和基本术语、抽象数据类型的表示与实现 01-002算法设计的要求、算法效率的度量 02-001线性表的类型定义 02-002线性表的顺序表示与实现、线性表的基本操作 02-003单链表的创建与操作、加工型...

    模拟实现哈希表数据结构,

    现在只能实现关键字为数字,存储单位为为字符串类型的,给大家简单的提供下HASH表的存储原理

    简单哈希表:简单的哈希表类。-matlab开发

    这是一个简单的哈希表类。 键必须是字符串(strcmp 用于定位条目),数据可以是任何类型。 内部结构是两个单元格列表,一个是键,一个是数据。 以下是哈希表内容: @哈希表 文件clear - 清除哈希表display - 显示...

    数据结构 用哈希表做的通讯录

    这是一个关于通讯录基本功能的简单程序希望对大家有用

    数据结构课程设计 银行账户管理系统

    这是一个数据结构课程设计银行账户管理系统,其中用到的数据结构有哈希链 有文件读写功能 账户密码管理功能 用户界面简约有序,不足之处,大家多多包涵,指教,谢谢

    实现数据结构的哈希表

    C语言编写的实现哈希表的程序,简单易懂,适用于初学者

    数据结构习题答案(全部算法)严蔚敏版

    1.1 数据结构的基本概念和术语 1.1.1 引言 1.1.2 数据结构有关概念及术语 1.1.3 数据结构和抽象数据类型(ADT) 1.2 算法描述与分析 1.2.1 什么是算法 1.2.2 算法描述工具——C语言 1.2.3 算法分析技术初步...

    Java数据结构与算法

    全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和队列、链表、递归、进阶排序、二叉树、红黑树、哈希表及图形等知识。附录中则提供了运行专题Applet和例程、相关书籍和问题解答。《Java数据结构和算法》...

    java数据结构

    第02讲 - 简单排序.avi 第03讲 - 栈和队列.avi 第04讲 - 链表.avi 第05讲 - 双端链表和双向链表.avi 第06讲 - 递归的应用 第07讲 - 递归的高级应用 第08讲 - 希尔排序 第09讲 - 快速排序 第10讲 - 二叉树的...

    java数据结构与算法

    第02讲 - 简单排序.avi 第03讲 - 栈和队列.avi 第04讲 - 链表.avi 第05讲 - 双端链表和双向链表.avi 第06讲 - 递归的应用 第07讲 - 递归的高级应用 第08讲 - 希尔排序 第09讲 - 快速排序 第10讲 - 二叉树的...

    数据结构:八大数据结构分析.pdf

    常⽤的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所⽰: 线性表和⾮线性表 ⼀、线性表 常见的线性表有:数组、队列、栈、链表 线性表是最基本、最简单、也是最常⽤的⼀种数据结构。线性表...

    C语言课程设计报告-基于哈希表的二叉树优化,利用哈希表的查找性能优化二叉树的操作(比平衡二叉树性能更高)

    对于初学C语言地数据结构很友好。另外对于二叉地生成方式提供了非常简单地构建方法,可以很快构建你地二叉树。利用这个本课程设计,可以衍生到其他二叉树,如二叉查找树,二叉平衡树,红黑树。这些都只需要稍加对...

    数据结构大作业字典的建立

    数据结构 哈希表 字典 可作为数据结构课程设计的大作业,比较简单明了。

Global site tag (gtag.js) - Google Analytics