- 浏览: 202534 次
- 性别:
- 来自: 长沙
最新评论
-
螺旋懒虫:
原本是想自己画点阵的,一来画的不标准,也不好解析(用excel ...
超级详细解析——字模 -
螺旋懒虫:
这个程序解决了我怎么加载点阵字库文件的问题,和怎么去拿到汉字对 ...
超级详细解析——字模 -
慕容墨风:
你好,我用你的测试程序发现数字提取不了
超级详细解析——字模 -
文之若素:
求代码,我最近在学这个,公司需要,呜呜呜,159374403 ...
初学EXTJS做的系统界面 -
csrhlu:
为什么我压缩之后文件还变大了呢? 而且解压eclipse下边会 ...
自己动手写压缩软件,超详细解释(哈夫曼实现)
前些天一直在纠结的 挂链 Hash表 趁着今天中午的时间 终于把其实现了。
总所周知的
两种线性结构的存储数据结构 链表 数组
两者的优点:
链表 对所存储的元素需要经常增加删除的,这个结构使用起来比较方便
数组 对经常需要对元素查询的,使用就方便,直接使用下标就可以了。
那问题是有没有结合两者优点的东西呢,有~!那就是HASH表
Java采用了哈希表的原理。哈希(Hash)实际上是个人名,由于他提出一哈希算法的概念,所以就以他的名字命名了。哈希算法也称为散列算法,是将数据依特定算法直接指定到一个地址上。hashCode方法实际上返回的就是对象存储的物理地址(实际可能并不是)。
挂链如下图所示:
这样一来,当集合要添加新的元素时,先调用这个元素的hashCode方法,就一下子能定位到它应该放置的物理位置上。如果这个位置上没有元素,它就可以直接存储在这个位置上,不用再进行任何比较了;如果这个位置上已经有元素了,就调用它的equals方法与新元素进行比较,相同的话就不存了,不相同就散列其它的地址(我所采用的是 其中的一种解决冲突的方法 挂连法)。所以这里存在一个冲突解决的问题。这样一来实际调用equals方法的次数就大大降低了,几乎只需要一两次。
package lesson1;
public class HashCode {
private Node[] HashList;//哈希链表
private int size=0;
private int Have=0;
//构造方法创建
public HashCode(int size){
HashList=new Node[size];
this.size=size;
}
//获得大小
public int getSize(){
return size;
}
//获得哈希编码
public int getHashCode(Object data){
return data.hashCode()*32767%size;
}
//增加元素
public void add(Object data){
int index=getHashCode(data);//得到哈希码对应的元素下标
//创建新的节点
Node newN =new Node(data);
if(HashList[index]==null){//哈希数组的index为空
HashList[index]=newN;
}else{//否则就加入到其的下拉链表中
Node Next=HashList[index];
if(Next.getData().equals(data)){//重复则不添加了
return ;
}
while(Next.getNext()!=null){//递归找到最后为空的下来链表
if(Next.getData().equals(data)){//重复则不添加了
return ;
}
Next=Next.getNext();
}
Next.setNext(newN);//设置为其的下拉链表。即拉链法的核心
}
Have++;//统计元素个数
if(Have+5>size){
reHash();//再次哈希,降低冲突
}
}
//删除一个
public void remove(Object node){
int index=getHashCode(node);
if(HashList[index].getData()==node){//在首节点的情况
if(HashList[index].getNext()==null){
HashList[index]=null;//没有挂链的就直接移除了
}else{//有挂链
HashList[index]=HashList[index].getNext();
}
return ;
}
//要删除的在拉链中
Node temp = HashList[index];
Node last = null;
//boolean flag=false;
while(!temp.getData().equals(node)&&temp!=null){
last=temp;
temp=temp.getNext();
}
if(temp!=null&&temp.getData().equals(node)&&last!=null){
last.setNext(temp.getNext());
}
}
//再次哈希
public void reHash(){
Node[] TempList = HashList;
size = size *2;
HashList=new Node[size];
Have=0;
//在哈希放入原HashList中去
for (int i=0;i<size/2;i++){
if(TempList[i]!=null){
add(TempList[i].getData());
//加入挂链中的内容
while(TempList[i].getNext()!=null){
TempList[i]=TempList[i].getNext();
add(TempList[i].getData());
}
}
}
}
//打印全部的出来
public void printAll(){
for (int i=0;i<size;i++){
Node temp =HashList[i];
while(temp!=null){
System.out.println(temp.getData());
temp=temp.getNext();
}
}
}
}
//节点的定义
class Node{
private Object data;//节点的值
public Node next;//下一个节点
public Node(Object data){
this.data=data;
}
//得到值
public Object getData(){
return data;
}
//得到下一个节点
public Node getNext(){
return next;
}
//设置下一个
public void setNext(Node next){
this.next=next;
}
}
输入数据测试:
package lesson1;
public class hashMain {
public static void main(String[] args){
HashCode code = new HashCode(10);
code.add(10);
code.add(20);
code.add(1);
code.add(2);
code.add(3);
code.add(4);
code.add(5);
code.add(6);
code.add(7);
code.add(8);
code.add(9);
code.add(11);
code.add(11);
code.add(11);
code.add(11);
code.remove(20);
code.printAll();
}
}
得到:
3 6 9 1 4 7 10 2 5 8 11
效率是绝对是比链表高的,
感兴趣的可以自己测试下。
Hash表 在追求效率方便还是有比较大的用处的。
本人也是刚刚接触这个东西,有什么不足请大家多多指教~
评论
2. 这个方法可能会返回负数
public int getHashCode(Object data){ return data.hashCode()*32767%size; }
3. 得注意放入对象的hashCode及equals方法
2. 这个方法可能会返回负数
public int getHashCode(Object data){ return data.hashCode()*32767%size; }
3. 得注意放入对象的hashCode及equals方法
发表评论
-
《动感地下城》,让宅男变猛男
2011-10-03 11:11 1558动感地下城 写在之前: 好久都没有发表文章了, ... -
RGP游戏的非主流应用——虚拟地图
2011-06-30 01:02 6052RGP游戏的非主流应用——虚拟地图 写在之前: 本 ... -
一个项目完整制作过程的分享
2011-05-22 14:23 8194St书店管理系统 写在文章之前: 本项 ... -
一个项目完整制作过程的分享
2011-05-22 14:18 0St书店管理系统 写在文章之前: 本项 ... -
eclipse下的1245个图标
2011-05-19 17:23 2101eclipse下的1245个图标 大家随便拿写 ... -
超级详细解析——字模
2011-05-17 21:09 6577超级详细解析——字模 一、简介 汉字库: 即 ... -
JavaSE 的MV模式(国际化)
2011-05-14 12:13 2719JavaSE 的 MV 模式 ... -
分享一个绿色版本的 JAR TO EXE工具(附上一个视频教程)
2011-03-15 14:05 1536如题,使用灰常简单 附上一个视频教程: -
偶然玩分形 java测试
2011-03-09 13:54 2547分形世界 我从拉丁文形容词fractus(分裂的)造出了fr ... -
Oracle, SQL Server, My SQL数据分页查询语句汇总
2011-03-05 23:16 1987之前一直在学习SQL Server,然而其的分 ... -
小议MVC模式开发
2011-02-27 22:08 1234做web项目是所经常提到的mvc模式。 MVC是三个 ... -
菜鸟 利用VE、截图 快速打造仿QQ绚丽界面
2011-02-12 02:52 2923自绘菜鸟 利用VE、截图 快速打造仿QQ绚丽界面 ... -
JAVA的几个重要概念小总结
2011-01-17 12:20 1377JAVA的几个重要概念小总结 方法声明: 写一个方 ... -
几个文字编码小总结
2011-01-17 12:03 1176ASCII 我们入门学习是最 ... -
超详细解释常用网络命令
2011-01-15 12:10 1557常用网络命令 PING请求 Ping www.google ... -
达通杯 赛后感想
2010-12-23 13:09 3557比赛结束两三天了今天才抽出了时间写写心得。 其实想想自己 ... -
自己动手实现高压缩比压缩软件 超详细解释(LZW算法)
2010-12-07 17:27 4947Lzw 针对大量的子串多次重复出现的压缩 之前 ... -
自己动手写压缩软件,超详细解释(哈夫曼实现)
2010-12-04 10:58 19612说到文件压缩大家很容 ... -
JAVA BMP解码 超详细解释
2010-11-21 23:02 13278首先,对于BMP 格式的图片大家都不感觉到陌生吧。 ... -
五子棋 图片版
2010-11-16 12:45 5493近来发现自绘的东西怎么都比不了自己PS加载图片所作的界面好看。 ...
相关推荐
SEO挂链工具 SEO挂链工具 SEO挂链工具
挂链工具
ftp挂链工具,真正的挂链工具无病毒无木马
ftp批量挂链,很好用,只要导入ftp地址用户名密码,自定义挂链代码,可以看到他的过程~
FTP密探%2B自动挂链完美破解FTP密探%2B自动挂链完美破解
黑链工具包,可以查询弱口令FTP,并实现全自动挂链,查链,PR查询,分类,掉链自动补链等等功能,是目前最好用,最稳定的黑链工具.
ftp暴力破解 挂链工具 暴力破解功能异常强大 ,挂链工具有时候需要配合手动比较好,提高网站权重的必备shi
这是一种seo的工具,但不建议使用。望大家适量用吧。
苹果FTP批量扫描,附带批量挂链软件,享受超级SEO优化代理的乐趣。。苹果FTP批量扫描苹果FTP批量扫描苹果FTP批量扫描
FTP扫描工具,输入关键字扫描弱口令FTP
网站SEO黑链智能收集批量挂链软件V6.16+注册机
网站提供利器
FTP挂链工具
FTP密探+批量挂链
苹果FTP密探扫描+挂链工具 SEO必备工具
苹果FTP批量查链挂链工具,自动扫描网上网站FTP 密码库和账号库目前够用 自己也要以下载更多的来替换掉
手机挂链圆珠笔PPT小插图素材下载,关键词:文具、圆珠笔、手机、手机挂链幻灯片插图素材,PPT小插图,PPT素材下载,PPTX格式;
电信设备-多功能移动手机挂链.zip
黑帽SEO——FTP扫描工具+FTP挂链工具
密探FTP批量挂黑、挂链工具.exe