- 浏览: 43951 次
- 性别:
1、什么是hash?
Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
也许这么听大家肯定会对hash不知所云,晕晕乎乎。说实话,我也是这样。所以根据我自己的理解呢,hash就是把一段数据通过某种方法映射成另外一个值(相当于x映射为f(x)),也就是一个单向加密的过程。这个方法可以自己定义,也可以去网上找现成的,比如MD5的加密算法就用到了hash。
2、为什么要用hash?
当然是用来加密数据了~~~不错,不过这却不是我要说的。hash还可以用来干许多事比如说快速建立索引及查找。举个最现实的例子:QQ同时在线人数平均在几千万~近两亿(极端情况不考虑),每个用户都是一个User的类保存在腾讯的服务器上,存储这些数据也许可以用数组,也可以用链表,不过我们很快就会发现这种方法的缺陷。假如说这时,有一个用户上线了,腾讯的服务器必须先检测是否该QQ号是否已经登录了。若是,则向原来登录的客户机发送离线消息,然后再让新的用户上线;若不是,则直接让该用户上线。不管是哪种情况,都需要进行查找遍历。如果用数组或链表,那么都得从头开始排查,最差的情况是里头有多少元素就要排查多少次,这已经大大降低了查询效率,况且一个时刻上线下线的人数少说也得数以百计,并且之后还伴随着添加和删除过程(相对来说,数组是查询快,增删操作慢,而链表正好相反),那么这么看来,单纯的用数组或是链表是行不通的了。
那么我们应该怎么解决呢?用hash,当然!不过具体要怎么实行?首先我们建立一个模型:一个长度为n的数组,每一个数组元素存的是一段链表的头节点,链表长度为m(每个链表的m值相互无关),而链表的每个节点存储的则是一个User类的对象,这样无形中就形成了一个二维的数据存储结构,我们称之为数组加链表模型。假如有0~99这100个数需要存到这种模型中,我们可以让数组的第一个元素专门存储第一位为0的数(即一位数),链表长度为10,存储的数据分别为0、1、2、3、4、5、6、7、8、9;第二个元素存储第一位为1的数……以此类推,直到全部存进。现在我们要查找65,假设数组名为a,我们只需要找到a[6],然后再循环查找链表的下一个节点,直到找到65,只需要5次。而用链表查找,则需要查找65次。当然如果用数组定义的话直接a[65]就能得到,但是如果需要在65与66之间再插入一个值就比较麻烦了,而上述数组加链表模型依然能轻松的解决这一问题。
现在我们回到QQ用户的问题,若是对于不同的用户能够尽可能的把他们分散到数组加链表模型的各处的话,查找和增删等操作就迎刃而解了,采取一种什么样的机制让他们分散呢?这就是hash方法了。我们知道每个用户的QQ号是唯一的,所以我们可以用该数值来进行hash运算。假如QQ同时在线人数为1亿,我们采取取模的hash算法,我们建立一个数组名为a,长度为100000的数组加链表模型,然后用QQ号的值对100000取模,比如说QQ号为123456789,取模后为56789,那么我们就把他存入a[56789]的链表中。当然不止一个QQ号取模后结果为56789,对于这些QQ号,新来一个就把他加到链表的最后一个节点的后面并设置链表相邻元素间的指向关系。全部遍历一遍建立好了之后再找某个QQ号就可以先取模,然后到指定的数组链表上去找了,在这里最多只需要10000次即可找到(针对九位数的QQ)或确定不存在。
3、需要注意的方面:
首先是hash方法的确定,在这方面每个人有自己的想法,根据hash算法和初始容量然后初步确定数组长度n的大小,要使得数据尽量散列开来(所以hash函数一般翻译为“散列”嘛)。
其次就是随着用户的增多会导致链表的越来越长,当数组长度不变之后每个元素的链表长度却在一个劲地增加,长此以往,这个模型就会变得越来越像纯链表,也就慢慢偏向无效率了。所以在适时的时候,即链表长度和数组长度达到某一关系后我们就应该扩充数组长度了,当数组长度一变,取模的值也就变了,就是说原来的hash结果已经改变了,无法再适用到新的长度的数组上,所以我们需要对原来的每个元素重新hash一次,称之为rehash过程。可以想象,rehash的代价是巨大的,但是这也是必须的。
4、拓展方面:
其实既然有了数组加链表模型,那么我们可以继续设置数组加数组加链表模型,或者在前面套n个数组,但是前提条件是该用户类必须有n个字段值是唯一的,若QQ设置用户昵称也不能一样,那么我们在第二个数组里可以对用户昵称再进行hash一下,建立一个索引,然后加入链表中。
以下是简单实现的一个数组加链表模型:
import java.util.ArrayList; import java.util.List; import java.util.Random; import java.util.Scanner; public class HashTest { int prime; public HashTest() { Scanner sc = new Scanner(System.in); int count = 0; System.out.println("请输入需要添加的个数(值由系统随机生成):"); count = sc.nextInt(); long start = System.currentTimeMillis(); MyThread th = new MyThread(); th.start(); int size = 2 * (int) Math.sqrt(count); prime = Prime(size); User DataArray[] = new User[size]; h: for (int i = 0; i < count; i++) { System.out.println(i); int value = random(); int addr = hash(value); // 排查重复 User checkuser = new User(); try { checkuser = DataArray[addr]; } catch (ArrayIndexOutOfBoundsException aioobe) { aioobe.printStackTrace(); System.out.println(DataArray.length); } while (checkuser != null) { if (checkuser.getid() == value) { continue h; } checkuser = checkuser.getnext(); } User u = new User(value); DataArray = addto(addr, u, DataArray); } th.setflag(false); System.out.println("共用了" + ((System.currentTimeMillis() - start) / 1000) + "秒"); System.out.println("添加成功。\t\n是否继续操作:\t\n1:继续\t0:退出"); int choose = new Scanner(System.in).nextInt(); while (choose != 0 && choose != 1) { System.out.println("输入错误,请重新输入"); sc = new Scanner(System.in); choose = sc.nextInt(); } if (choose == 0) { System.exit(0); } else { System.out .println("请输入需要进行的操作:\t\n1:增加\t2:删除\t\n3:修改\t4:查询\t\n0:退出"); int result = new Scanner(System.in).nextInt(); while (result != 1 && result != 2 && result != 3 && result != 4 && result != 0) { System.out.println("输入错误,请重新输入"); sc = new Scanner(System.in); result = sc.nextInt(); } switch (result) { case 1: add(DataArray); break; case 2: del(DataArray); try { Thread.sleep(2000); query(DataArray); } catch (Exception e) { } break; case 3: fix(DataArray); try { Thread.sleep(2000); query(DataArray); } catch (Exception e) { } break; case 4: query(DataArray); break; case 0: break; default: } System.exit(0); } } /** * 获取质数 * * @param len * 数组长度 * @return 离len数值最近的最大的质数 */ int Prime(int len) { int sqr = (int) Math.sqrt(len); while (len > 2) { for (int i = 2; i < sqr; i++) { if (len % i == 0) { break; } if (i == sqr - 1) { return len; } } len--; } return len; } /** * 生成随机数 * * @return 生成的随机数 */ int random() { return new Random().nextInt(900000000) + 100000000; } /** * 哈希算法 * * @param value * 传入的值 * @param prime * 计算数组长度所得的质数 * @return 哈希算法后的结果 */ int hash(int value) { int sum = 0; while (value / 10 != 0) { sum += Math.pow(8, value % 10); value /= 10; } return sum % prime; } /** * 添加元素 * * @param addr * 数组的第几号元素 * @param u * 加入的User对象 * @param Array * 加至的数组 */ User[] addto(int addr, User u, User[] Array) { if (addr > Array.length) { throw new RuntimeException("地址超出数组长度,添加失败"); } if (Array[addr] == null) { Array[addr] = u; } else { User user = Array[addr]; // 链表节点数 int amount = 0; while (user.getnext() != null) { amount++; user = user.getnext(); } user.setnext(u); u.setlast(user); if (amount > Array.length * 0.8) { // 链表节点过多,扩展数组 System.out.println("链表节点过多,扩展数组"); Array = rehash(Array); } } return Array; } /** * 当数组需要扩张时的重新散列方法 * * @param Array */ User[] rehash(User[] Array) { User[] reArray = new User[(int) (Array.length * 1.5 + 100)]; List<User> list = new ArrayList<User>(); prime = Prime(reArray.length); for (int i = 0; i < Array.length; i++) { for (User u = Array[i]; u != null; u = u.getnext()) { list.add(u); try { // 把原本的上下链关系全部断开 u.getlast().setnext(null); u.setlast(null); } catch (NullPointerException npe) { System.out.println("空指针"); } } } for (int i = 0; i < list.size(); i++) { // 逐个添加 User u = list.get(i); int addr = hash(u.getid()); addto(addr, u, reArray); } Array = reArray; return Array; } void add(User[] DataArray) { Scanner sc = new Scanner(System.in); System.out.println("请输入需要添加的个数(值由系统随机生成):"); int count = sc.nextInt(); long start = System.currentTimeMillis(); MyThread th = new MyThread(); th.start(); h: for (int i = 0; i < count; i++) { int value = random(); int addr = hash(value); User checkuser = DataArray[addr]; while (checkuser != null) { if (checkuser.getid() == value) { continue h; } checkuser = checkuser.getnext(); } User u = new User(value); DataArray = addto(addr, u, DataArray); } th.setflag(false); System.out.println("花费了" + ((System.currentTimeMillis() - start) / 1000) + "秒后增加成功,即将显示结果……"); try { Thread.sleep(2000); } catch (Exception e) { } query(DataArray); } void del(User[] DataArray) { Scanner sc = new Scanner(System.in); System.out.println("请输入需要删除的用户的id值:"); int id = sc.nextInt(); int addr = hash(id); User u = DataArray[addr]; if (u != null) { if (u.getid() == id) { DataArray[addr] = u.getnext(); System.out.println("元素已成功删除,即将显示结果……"); return; } else { while (u.getnext() != null) { u = u.getnext(); if (u.getid() == id) { if (u.getnext() == null) { u.getlast().setnext(null); System.out.println("元素已成功删除,即将显示结果……"); return; } else { u.getlast().setnext(u.getnext()); u.getnext().setlast(u.getlast()); System.out.println("元素已成功删除,即将显示结果……"); return; } } } } } System.out.println("未找到相应元素,即将显示结果……"); } void fix(User[] DataArray) { Scanner sc = new Scanner(System.in); System.out.println("请输入需要修改的用户的id值"); int id = sc.nextInt(); int addr = hash(id); User u = DataArray[addr]; while (u != null) { if (u.getid() == id) { System.out.println("请设置其名字:"); Scanner scan = new Scanner(System.in); String name = scan.next(); u.setname(name); System.out.println("已成功更新数据,即将显示结果……"); return; } u = u.getnext(); } System.out.println("未找到相应元素,即将显示结果……"); } void query(User[] DataArray) { int all = 0; int mount = DataArray.length; System.out.println("共有" + mount + "个元素"); for (int i = 0; i < mount; i++) { int num = 1; User u = DataArray[i]; if (u != null) { while (u.getnext() != null) { num++; u = u.getnext(); } } else { num = 0; } all += num; System.out.println("第" + i + "个元素的链表中共有" + num + "个对象"); } System.out.println("共有" + all + "个对象"); } /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub new HashTest(); } class User { private int id; private User nextuser, lastuser; private String name; public User() { } public User(int id) { this.id = id; } public int getid() { return id; } public void setnext(User u) { this.nextuser = u; } public User getnext() { return nextuser; } public void setlast(User u) { this.lastuser = u; } public User getlast() { return lastuser; } public void setname(String name) { this.name = name; } public String getname() { return name; } } class MyThread extends Thread { public boolean flag = true; public void run() { while (flag) { System.out.println("正在添加中,请等待……"); try { Thread.sleep(5000); } catch (Exception e) { } } } public void setflag(boolean flag) { this.flag = flag; } } }
发表评论
-
PlaySound和sndPlaySound的三种播放音乐方法
2012-11-16 21:18 8138首先要添加头文件 #include "mmsyst ... -
PlaySound和sndPlaySound的三种播放音乐方法
2012-11-16 21:16 1首先要添加头文件 #incl ... -
android中的Dialog
2012-06-28 20:20 1501android手机和PC机一样,也会根据各种不同程 ... -
关于网络通信中如何传输对象的问题
2012-03-14 17:09 1711我们不管在用TC ... -
设计模式所感
2012-03-10 22:03 1056刚接触高级语言编程的人是不会考虑怎么去设计类之间的 ... -
UDP传输的实现与检测重发机制
2012-02-26 17:29 7516java建立UDP连接和建立TCP/IP连接一样简 ... -
c语言实现简单链表建立及筛选
2012-02-23 01:05 1620最近在重新复习c,其实也可以算是学习吧。由于大一时上课没怎么听 ... -
小小的心得
2011-12-12 11:51 921关于jsp的,因为最近要做数据库,所以看了看,不过估计到最后数 ... -
javah的classpath路径设置
2011-11-20 22:01 4851貌似javah的classpath路径必须要设置~~ ... -
JTree实现windows文件打开
2011-11-16 19:46 1420package cn.zyf.java树1116; im ... -
文件搜索的简单实现
2011-10-24 00:46 1244快一个月没写总结了, ... -
java关键字总结
2011-09-25 17:09 808首先我们得明确,java中 ... -
关于事件源的应用
2011-09-21 00:52 783今天被画图板的一个鼠标右键单击处理事件的事情搞得晕头转 ...
相关推荐
利用redis list和hash存法实现数据带排序增删改查
本文实例讲述了thinkPHP框架通过Redis实现增删改查操作的方法。分享给大家供大家参考,具体如下: 一、概述 Redis是一个NoSQL数据库,由于其数据类型的差异,所以要在MVC框架中实现CURD操作,比较繁锁。事实上在...
根据算法导论上的HashTable, C语言实现
C# StackExchange.Redis 操作封装类库,分别封装了Redis五大数据结构(String,Hash,List,Set,ZSet)的增删改查的操作方法,支持Async异步操作。支持Redis分库操作。支持信息队列操作。 带有单元测试,为每个...
实现了创建哈希表的函数 createHashtable,哈希函数 hash,插入键值对的函数 insert,查找键对应值的函数 get,删除指定键的节点的函数 erase,以及打印哈希表的函数 printHashtable。 在 main 函数中进行了简单的...
Hash分区是Oracle实现表分区的三种基本分区方式之一。对于那些无法有效划分分区范围的大表,或者出于某些特殊考虑的设计,需要使用Hash分区,下面介绍使用方法
hash表操作函数 HASH_ADD_INT HASH_ADD_STR
HASH分区表增加新的分区的一点研究 HASH分区的ADD PARTITION和RANGE分区、LIST分区的SPLIT PARTITION很类似
该文档消息描述了hash表的创建、数据插入、数据删除、数据查找以及hash表销毁等操作
stm32f407平台上实现的hash算法
C语言实现的Hash表(代码)。C语言实现的Hash表(代码)。C语言实现的Hash表(代码)。C语言实现的Hash表(代码)。
从linux内核提取出来的,双向链表和hash表实现。在普通的用户态C程序中,均可使用
Hash表应用 (必做) (查找) [问题描述] 设计散列表实现身份证查找系统,对身份证号进行Hash。 [基本要求] (1) 设每个记录有下列数据项:身份证号码(虚构,位数和编码规则与真实一致即可)、姓名、地址; ...
c语言hash表源码 来自于开源软件项目
Hash表的引出是为了减少查询数据库操作所带来的时间问题,将数据直接存放在哈希表中,方便查阅。当然,现在也可以用redis来做缓存操作。 从小往大看,每一个节点代表一个对象,并采用单链表的形式将每个节点串联起来...
自己实现的hash表,自己的hash函数,优化了的内存管理
修改图片 hash 值1
C++写的hash表模板类,效率还是很不错的。另付有测试代码和可运行文件
能够描述出什么是 nosql ...能够写出Redis中hash类型数据的增删改查相关命令 能够说出Redis中 list 保存的数据类型 能够使用StrictRedis对象对string类型数据进行增删改查 能够参考课件步骤搭建 Redis 集群
PHP可以模拟实现Hash表的增删改查。通过对key的映射到数组中的一个位置来访问。映射函数叫做Hash函数,存放记录的数组称为Hash表。 Hash函数把任意长度的和类型的key转换成固定长度输出。不同的key可能拥有相同的...