- 浏览: 24037 次
- 性别:
数据结构之Hash表
一.数据结构概念
数据结构是计算机存储,组织数据的方式.
包括三个组成部分: 数据的逻辑结构 ,数据的存储结构 ,数据运算结构
就个人理解,数据结构就是存储数据的容器,简单的数组显然不能适应大量数据存储,查找等功能的实现。因此,合理,高效,也就是空间和时间效率都必须高效,也就成了计算机人员所研究的重点对象。
接下来,就简单介绍Hash表作为一种数据结构的原理,具体代码实现.
二.Hash原理
1.数组,链表 , 数等数据结构有一个共同点:数据的位置和其关键字之间不存在一个确定关系,它们之间的区别仅在于:关键字和给定值比较的顺序不同.
2.将数据位置和关键字联系----以Hash(key) 函数计算key在表中的位置.
接下来我将以除留余数法---H(key)=key MOD p(p<m) (m为表长) 示例讲解Hash表的构成。
3.冲突.
可以想象,数据数量一旦增多,必然发生不同key值通过Hash函数计算的地址值相同的情况,我们称这种情况成为——冲突。
为解决冲突,即为产生冲突的关键字寻找下一个哈希地址,可以采取多种方法:
(开放定址法 , 再Hash法 ,链地址法 等)
此时,我选择最后一种方法来讲解,其余的方法读者有兴趣课自行找寻资料进行学习.
4.链地址法——结合数组和链表,即通过Hash函数计算得到相同地址的元素链在第一个元素的后面。此时,存储形式就是一个个节点了,包括数据的Key值和指针域。
5.数据结构的用途就是实现对数据的操作:增----删----查----改 ,效率当然越高越好.
就我们所知的:
数组查找方便,通过下表可直接定位,但增,删的效率较慢,因为改变的代价是其他数据也要进行相应的移动。
链表在插入,删除等操作上显然体现了其优势,因为只用改变数据链域中的指向即可。但链表的查找操作却仍是需要逐一遍历,效率较低。
Hash的结构很容易解释其平衡查找和删除插入操作的效率问题
6.阀值.
首先,Hash表仍是以数组为基础的,即数组大小初始就要设定且不能改变,当我们无法预知数据总量时,无法准确估计数组大小。若数组初始设定的过大,则浪费内存,若太小,则会出现数组下的链表过长,甚至长于数组的长度,此时,查找效率明显降低。
为解决这个问题,我们需要设定一个阀值,用作控制平衡的量度.
此时,我设定的阀值的是:某一条链上的节点总数和数组大小的比值。这这是个数值,更是个规则。建设Hash表过程中,不能超过这个规则的设定。一旦超过,则需要ReHash。
7.ReHash
用更大的数组重新计算地址,并按照上述规则建设Hash表,直至满足阀值的要求。
三.代码实现
public class MyHash { private static int size;// 数组的初始大小 private static int newSize;//新数组的大小 Node[] array;//初始数组 Node[] newArray;//新数组 static int length = 0;// 当前存储的节点数 double p = 0.7;//阀值 static int time = 1;//reHash的次数统计 public static void main(String[] agr) {//主函数 MyHash hash = new MyHash(); hash.test(); } public MyHash() {//构造函数 size = 16; array = new Node[size];// 初始化数组 } private void test() {// 测试方法 // 添加 Random random = new Random();//创造随机数 long start1 = System.currentTimeMillis();//当前时间 for (int i = 0; i < 100000; i++) { int num = random.nextInt(10000);//循环10万次 add(num);//添加至Hash链表中 } System.out.println(); long start2= System.currentTimeMillis() ; // 检查是否超过阀值,若超过则reHash overP(); System.out.println("遍历数组------------------------->"); long start3 = System.currentTimeMillis(); for (int j = 0; j < size; j++) { System.out.println("第" + j + "个位置"); Node node = array[j]; System.out.print(node.getKey() + " "); node = node.getNext(); while (node != null) { System.out.print(node.getKey() + " "); node = node.getNext(); } System.out.println(); } System.out.println("实现Hash创建所用时间为:" + (start2-start1)); System.out.println("实现Hash搜索所用时间为:" + (System.currentTimeMillis() - start3)); } /** * 根据key值计算地址 * * @return:地址 */ public int Hash(int key, int size) {//求余数 return key % size; } /** * 将节点加入到Hash表中 */ public void add(int key) { int add = Hash(key, size);// 先计算地址,判断该位置是否为空 Node node = array[add]; if (node == null) {// 为空,即可以加入该key值 array[add] = new Node(); array[add].setKey(key); length++; } else {// 不为空,用链地址法处理冲突 while (node.getNext() != null) { node = node.getNext(); } Node next = new Node(); node.setNext(next); next.setKey(key); length++; } } /** * 查找 * @param key */ public boolean find(int key) { int add = Hash(key, size);// 计算地址 if (array[add].getKey() == key) { return true; } else { Node next = array[add].getNext(); while (next != null) { while (next.getKey() != key) { next = next.getNext(); } return true; } return false; } } /** * 改 */ public void alter(int key, int cover) { int index = Hash(key, size); if (array[index].getKey() == key) { array[index].setKey(cover); } else { Node next = array[index].getNext(); while (next.getKey() != key) { next = next.getNext(); } next.setKey(cover); } } /** * 判断是否超过阀值 */ public void overP() { for (int i = 0; i < size; i++) { int num = 0; if (array[i] != null) { Node next = array[i].getNext(); while (next != null) {// 某一串,有下个节点 num++; next = next.getNext(); } } if (num >= (0.7 * size)) {// 某一串的个数超过阀值 System.out.println("超过阀值,重新Hash----------------------->"); reHash(); } break; } } /** * 再Hash */ private void reHash() { time++; newSize = time * size; newArray = new Node[newSize]; for (int i = 0; i < size; i++) { Node node = array[i];// 原数组 while (node != null) { int add = Hash(node.getKey(), newSize);// 计算新地址 Node newNode = newArray[add]; if (newNode == null) {// 数组上为空 newArray[add] = new Node(); newArray[add].setKey(node.getKey());// 设置Key值 } else {// 数组该位置不为空,找下一个 while (newNode.getNext() != null) { newNode = newNode.getNext(); } Node newNext = new Node(); newNode.setNext(newNext); newNode.setKey(node.getKey()); } node = node.getNext();// /循环至下一个 } } size = newSize; array = newArray;// 将新数组赋给原先数组 overP(); } }
运行结果如下:
................
第1917个位置
7677 3837 7677 1917 9597 5757 1917 3837 3837 1917 1917 3837 3837 9597 3837 3837 9597 1917 9597 5757 1917 5757 3837 1917 5757 9597 3837 5757 3837 9597 9597 7677 1917 3837 5757 5757 3837 3837 1917 5757 3837 5757 3837 0
第1918个位置
1918 3838 1918 9598 1918 9598 5758 7678 3838 1918 5758 5758 7678 9598 7678 1918 3838 5758 5758 5758 1918 9598 5758 1918 3838 3838 9598 7678 9598 1918 1918 7678 9598 1918 1918 9598 5758 3838 5758 3838 5758 1918 1918 1918 1918 3838 7678 3838 1918 0
第1919个位置
9599 1919 5759 1919 1919 7679 3839 3839 7679 5759 7679 3839 5759 3839 9599 3839 5759 5759 1919 9599 7679 3839 3839 5759 5759 5759 1919 1919 9599 5759 9599 9599 7679 3839 3839 9599 9599 5759 1919 3839 0
实现Hash创建所用时间为:6827
实现Hash搜索所用时间为:1394
发表评论
-
java基础整理
2013-05-13 22:22 0Java基础整理 从武汉回来有好几周的时间了 ... -
线程同步
2013-01-18 23:49 825窗外狂风大作,实在不想在睡觉时刻本着不完成誓不罢休不 ... -
线程同步
2013-01-18 23:19 0窗外狂风大作,实在不 ... -
通信基础小结
2012-10-29 00:14 748通信基础小结 通信 ... -
线程项目总结
2012-08-01 22:46 909线程项目——坦克大战总结 一.预计游 ... -
线程基础
2012-08-01 22:32 603线程基础 一.进程和线程 ... -
数据结构之链表
2012-08-01 22:23 636数据结构之链表 链表的基本概念 ... -
哈弗曼树解压缩
2012-07-30 15:06 787... -
IO总结
2012-07-16 21:05 645Java IO 总结 第一部分 ... -
Java集合机制
2012-07-15 20:01 989Java 集合框架 一.关于集合 ... -
异常机制
2012-07-11 14:30 738JAVA异常机制总结 ... -
画图板小结
2012-07-05 10:05 706项目总结——画板 一.整体思路 ... -
关键字
2012-05-25 16:28 599关键字总结 一.关键字分类 1.常用关键字 ... -
继承,转型,重写,多态性
2012-05-13 15:11 669Java实战入门小结——02 一:继承 1 ... -
类,对象,构造函数,this关键字等
2012-04-15 22:48 1120Java实战入门小结--01 一:类与对象的关系 类 ...
相关推荐
cpp代码-数据结构-hash
Tabela-Hash:数据结构-哈希表
数据结构课程设计, hash表,哈希表。
最快的排序算法 最快的内容查找算法-----暴雪的Hash算法,排序算法数据结构
于基hash表的班级成员管理数据结构课程设计--毕业设计.doc
数据结构原本,大一统,外文书原版 Data structures Contents Articles Introduction 1 Data structure 1 Linked data structure 3 Succinct data structure 6 Implicit data structure 8 Compressed data structure...
双向链表 - 数据结构与算法 C 双向链表 - 数据结构与算法 C 。。。。。。
最快的排序算法 javahash实现-Java-哈希算法-最快的实现,排序算法数据结构
最快的排序算法 计算机最快的算法-史上14个最快速算法:孩子的计算能力爆表!大脑堪比计算机!...,排序算法数据结构
本课件以C语言为描述语言,从最简单的线性链表开始讲解,非常适合初级学者,并且包含了数据结构的所有内容。
数据结构第16次作业,hash表 Spellchecking Prerequisites, Goals, and Outcomes Prerequisites: Students should have mastered the following prerequisite skills. • Hash Tables - Understanding of the ...
数据结构与算法分析java版 Table of Contents Data Structures and Algorithms in Java - 4 Introduction - 7 Part I Chapter 1 - Overview - 11 Chapter 2 - Arrays - 29 Chapter 3 - Simple Sorting -...
并且要用顺序存储结构。 基本思想是:首先将给定值key与表中中间位置记录的关键字相比较,若二者相等,则查找成功,否则根据比较的结果确定下次查找的范围是在中间记录的前半部分还是后半部分,然后在新的查找范围内...
背景 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录...
通常,遍历某些数据结构、在过程中积累参数很有用。 CounterHash 类提供了递增、递减、加、减和获取散列的总和、值和排序键的函数。 例子 设置 将 counter-hash-js 添加到您的项目或 package.json 文件中: npm ...
数组(Array):连续存储元素的集合,可以通过索引访问元素。插入和删除元素的时间复杂度较高,为 O(n),但...哈希表(Hash Table):使用哈希函数将键映射到存储位置的数据结构,可以实现快速的插入、删除和查找操作。
数据结构中hash函数的实现,自己写的,VC平台。
数据结构Hash表C语言实现