- 浏览: 54583 次
- 性别:
- 来自: 长沙
最新评论
-
huyuancai1010:
Eclipse中配置Struts2并实现HelloWorld -
zl544434558:
领教了。很久没用struts了,记得不是很清楚了
Eclipse中配置Struts2并实现HelloWorld -
Wuaner:
楼主 你这里的 reHash, 是个什么概念? HashMap ...
挂链式Hash表的实现 -
jadethao:
作者辛苦了。
关于P2P的简单总结 -
剑&箫:
oolala 写道也买了一本,可是看了二章坚持不下去了。
本人 ...
《TCP/IP详解,卷1:协议》读书笔记之概述总结
最基本的数据结构是数组和链表,这两种数据结构各有优缺点,比如数组,查找容易,插入困难;而链表插入容易,查找困难。在作画图板的重绘时用的是自定义队列保存图形的形状,在自定义队列中是包装了对数组的各种操作,当时没注意到这种自定义队列的优缺点。今天以保存自己作的简单的IM系统的用户的账号为例,实现一个自己所理解的Hash表,以充分利用以上两种基本数据结构的优点。
首先要理解Hash表的相关概念:在相关教材上是这样定义的:根据设定的哈希函数和处理冲突的方法将一组关键字映像到一个有限的连续的地址集上,并以关键字在地址集中的“像”作为记录在表中的存储位置,这种表称为哈希表,这一映像过程称为哈希造表或散列。在构造哈希表的过程中最重要的是哈希函数的选择,此类函数要为均匀的哈希函数,也就是要具有一致性,再一个就是哈希冲突的解决,所谓的哈希的冲突就是经过哈希函数计算得到相同是下标值,最后一个就是reHash,也就是当表中数据的存储达到一定的程度时要重新经过哈希函数的计算存到更大的表中。哈希函数的构造方法有直接定址法、数字分析法、平方取中法、折叠法、除留余数法等,在这里我选择的是JDK的HashMap中优化好的哈希函数;而哈希冲突的解决有开放定址法、再哈希法、链地址法、建立一个公共溢出区等,在这里用的是链地址法,也就是经过哈希函数计算出数据的在数组中的存储位置、如果有相同的存储位置则构建链表将新加入的元素加到链表的末尾,简单的说就是数组中的元素存的是链表。话已经说到这里了,先上代码,代码中的注释比较清楚,就不多解释了,如有不正确的地方欢迎各位指出纠正。
下面是一个UserInfo类的代码
public class UserInfo {
//用户的昵称
public String nikeName;
//用户的jk号
public int jkNum;
//用户的密码
public String pwd;
/**
* 构造方法:根据昵称和账号创建一个用户对象
* @param nikeName:用户的昵称
* @param jkNum:用户的账号
*/
// public UserInfo(int jkNum){
// this.jkNum = jkNum;
// }
//下面为各个属性的get/set方法
public String getNikeName() {
return nikeName;
}
public void setNikeName(String nikeName) {
this.nikeName = nikeName;
}
public int getJkNum() {
return jkNum;
}
public void setJkNum(int jkNum) {
this.jkNum = jkNum;
}
public String getPwd() {
return pwd;
}
public void setPwd(String pwd) {
this.pwd = pwd;
}
}
下面是链表的结点类
public class LinkNode {
//结点存储的数值域:用户对象
private UserInfo user;
//指向下一个节点对象
private LinkNode node = null;
//下面为get/set方法
public UserInfo getUser() {
return user;
}
public void setUser(UserInfo user) {
this.user = user;
}
public LinkNode getNode() {
return node;
}
public void setNode(LinkNode node) {
this.node = node;
}
}
下面是实现的hash表
测试的代码:public class MyHash {
//数组的长度,即默认容量
private static int nodeLen=16;
//存放链表的数组
LinkNode[] node;
private int size;// 当前容量
private static float LOAD_FACTOR = 0.75f;// 重载因子
private int max;// 能存到的最大的数组下标
/**
* 构造方法:初始化一个存放链表的数组
*/
public MyHash(int init_Capaticy, float load_factor){
if (init_Capaticy < 0){
throw new IllegalArgumentException("Illegal initial capacity: "+ init_Capaticy);
}
if (load_factor <= 0 || Float.isNaN(load_factor)){
throw new IllegalArgumentException("Illegal load factor: " + load_factor);
}
this.LOAD_FACTOR = load_factor;
max = (int) (init_Capaticy * load_factor);
node = new LinkNode[init_Capaticy];
}
/**
* 重写默认的构造方法
*/
public MyHash(){
this(nodeLen,LOAD_FACTOR);
}
/**
* Hash函数
* @return:返回一个hash值
*/
private static int hash (Object o){ //根据对象的哈希码得到一个优化的哈希码,
//算法参照java.util.HashMap的hash()方法
int h = o.hashCode();
h += ~(h<<9);
h ^= (h>>>14);
h += (h<<4);
h ^= (h>>>10);
return h;
}
/**
* 根据Hash函数得到的hash值和数组的长度计算数据在数组中的位置
* @param hashCode
* @return:返回数据在数组中的存储位置
*/
private int indexFor(int hashCode){ //根据Hash码得到其索引位置
//算法参照java.util.HashMap的indexFor()方法
return hashCode & (node.length-1);
}
/**
* 向队列中查询数据
* @param jkNum
* @return
*/
public boolean getData(int jkNum){
//计算该用户的Hash值,并得到数组的下标
int index = indexFor(hash(jkNum));
//根据下标得到数组的元素
LinkNode tempNode = node[index];
if (null!=tempNode){//若链表不为空
//若不为空,遍历链表
while(null!=tempNode){
if (jkNum==tempNode.getUser().getJkNum()){
System.out.println("查询成功...");
return true;
}
tempNode = tempNode.getNode();
}
}
System.out.println("查询失败...");
return false;
}
/**
* 向队列指定位置放入数据
* @param user
* @return
*/
public boolean putData(UserInfo user){
LinkNode tempNode = new LinkNode();
tempNode.setUser(user);
if (setNode(node,tempNode)){
size++;
return true;
}
return false;
}
/**
* 当默认的数组达到重载时,重新设定新的数组
* @param newSize:新数组的长度
* @return
*/
public void reHash(int newSize){
//实例化一个新的数组
LinkNode[] newNode = new LinkNode[newSize];
max = (int) (newSize*LOAD_FACTOR);
//遍历原有数组,将原有数组的每一个元素重新存到新的数组中
for (int i=0;i<node.length;i++){
LinkNode tempNode = node[i];
while(null!=tempNode){
setNode(newNode,tempNode);
tempNode = tempNode.getNode();
}
}
node = newNode;
System.out.println("reHash成功...");
}
/**
* 将节点添加到链表中
* @param array:存链表的数组
* @param node:结点
* @return:添加成功返回ture,否则返回false
*/
public boolean setNode(LinkNode[] array,LinkNode tempNode){
//根据结点数据域的用户对象的jkNum计算hash值,并得出所存放数组中的下标值
int jkNum = tempNode.getUser().getJkNum();
int index = indexFor(hash(jkNum));
//根据下标找到对应的元素
LinkNode indexNode = array[index];
if (null!=indexNode){//如果指定下标值的数组元素不为空
//遍历该数组元素中链表
while(null!=indexNode){
if (tempNode.getUser().getJkNum()==indexNode.getUser().getJkNum()){
return false;
}
else {
if (null==indexNode.getNode()){//如果达到队尾,则中断循环
break;
}
//没有达到队尾,则继续遍历
indexNode = indexNode.getNode();
}
}
//当遍历到队尾,如果没有相同的元素,则将该元素挂到队尾
addNode2Last(indexNode,tempNode);
System.out.println("成功将此用户挂在链表末尾..."+index);
}
//如果指定下标元素为空,则设置为链表的一个元素
setFirstNode(array,tempNode,index);
size++;
return true;
}
/**
* 设置一个结点指向下一个结点
* @param lastNode:链表最后的一个结点
* @param tempNode:要添加的结点
*/
public void addNode2Last(LinkNode lastNode,LinkNode tempNode){
if (size>max){//如果达到重载时,则reHash
reHash(node.length*4);
}
lastNode.setNode(tempNode);
tempNode.setNode(null);
System.out.println("成功将一个结点指向下一个结点...");
}
/**
* 根据指定下标设置数组中对应位置的第一个元素
* @param array:数组
* @param firstNode:要设置的第一个元素
* @param index:指定的数组下标
*/
public void setFirstNode(LinkNode[] array,LinkNode firstNode,int index){
if (size>max){//如果达到重载时,则reHash
reHash(node.length*4);
}
//设置元素
array[index]=firstNode;
firstNode.setNode(null);
System.out.println("设置第一个元素成功...");
}
}
public static void main(String args[]){ MyHash ms = new MyHash(); for (int i=1001;i<1100;i++){ UserInfo user = new UserInfo(); user.setJkNum(i); LinkNode tempNode = new LinkNode(); tempNode.setUser(user); tempNode.setNode(null); ms.setNode(ms.node, tempNode); // ms.putData(user); } System.out.println("----------------"); // UserInfo user = new UserInfo(); // user.setJkNum(1001); ms.getData(9999); }
发表评论
-
Java动态加载小结
2012-03-04 01:15 3034上一节课老师讲了java类的动态装载与反射,上课时听的 ... -
String类常用方法总结
2011-08-30 14:34 1549自己对字符串的各种方法不太熟悉,今天把主要的方法都试了一遍,简 ... -
哈夫曼树小结
2011-08-12 00:44 3148所谓哈夫曼树,又称为最优二叉树,要了解哈夫曼树,首先先来了解几 ... -
线索二叉树小结
2011-08-11 23:52 1517在前面总结的链表是一种一对一的关系,而有一种一对多的关系就是树 ... -
Java中自定义链表总结
2011-08-10 01:15 1900在C/C++中可知链表是一种物理存储单元上非顺序的线性存储结构 ... -
以打砖块游戏来理解多线程
2011-08-08 01:51 1568前几天学习了多线程,现在总结自己做的一个打砖块的游戏,以此来加 ... -
多线程总结
2011-08-03 01:26 14511.进程,程序的区别 在上一篇总结中总结了进程与线程的区别, ... -
多线程入门总结
2011-08-02 01:35 1211什么是线程 提到线程,首先要了解进程。每个程序都有一个入口,在 ... -
画图板数据的存取
2011-07-31 13:40 1228前段时间作了个简单的画图板,能够画直线,矩形,椭圆,三角形四种 ... -
异常机制小结
2011-07-31 13:31 904什么是异常 异常是指程序运行时,可能由于外部系统的条件的变更而 ... -
输入输出流的总结
2011-07-30 15:40 1521我们都知道在电脑上对数据的存储有三种方式,一种是外存,一种是内 ... -
Java中文件的操作
2011-07-30 12:21 2119文件可分为目录文件、 ... -
JAVA常用集合框架
2011-07-25 00:40 1326Java中集合类定义主要是在java.util.*包下面,常用 ... -
java中常用关键字总结
2011-07-24 01:15 1400关键字的定义 所谓关键 ... -
Java基础之登陆界面开发入门
2011-06-21 00:40 2155在前面学了继承,就可 ... -
Java基础知识总结
2011-06-15 21:56 576这学期在学校初步接触了Java,感觉对Java挺有兴趣的。于是 ...
相关推荐
在IT行业中,"挂链工具"通常指的是用于网站优化,特别是搜索引擎优化(SEO)的一类软件或服务。这类工具的主要功能是帮助用户管理和优化他们网站的外部链接,也就是我们常说的"外链"。外链对于提升网站的搜索引擎...
FTP批量挂链工具是一种针对网站管理的工具,主要用于在多个FTP服务器上快速部署特定的链接代码,例如“黑链”。这种工具通常被用于SEO优化、网站推广或是非法的黑帽SEO活动,因为“挂黒链”指的是在网站上不透明地...
SEO(Search Engine Optimization)挂链工具是用于提升网站在搜索引擎排名的一种辅助软件。它通过自动或半自动的方式在互联网上创建指向目标网站的链接,以此提高网站的可见性和权重。在SEO领域,链接被认为是投票,...
"FTP挂链工具"就是这类操作的一种辅助软件,它利用FTP(File Transfer Protocol)协议,允许用户远程管理服务器上的文件,包括上传、下载、删除等操作。 FTP挂链工具的主要功能是帮助用户便捷地在目标服务器上植入...
【网站提供挂链】是指网站为用户或站长提供的一个服务,允许他们将自己的链接挂在网站上,以提升其网站的曝光度、流量或者搜索引擎排名。挂链通常被用作一种网络营销策略,通过与其他网站建立链接关系,可以提高自身...
黑链工具包,可以查询弱口令FTP,并实现全自动挂链,查链,PR查询,分类,掉链自动补链等等功能,是目前最好用,最稳定的黑链工具.
FTP扫描工具有时会被滥用,用于在未授权的情况下在FTP服务器上放置恶意链接,这种行为被称为黑帽SEO,会对被挂链的网站和网络环境带来负面影响。 为了有效利用FTP扫描工具,用户需要了解以下知识点: 1. **FTP协议...
这是一种seo的工具,但不建议使用。望大家适量用吧。
FTP批量扫描技术是一种网络工具,主要用于自动化地查找和连接FTP服务器,从而实现快速搜索和管理大量FTP站点。在IT行业中,这项技术常被用于网站管理员、SEO专家或网络安全专业人士进行大规模的数据采集、备份或者...
ftp暴力破解 挂链工具 暴力破解功能异常强大 ,挂链工具有时候需要配合手动比较好,提高网站权重的必备shi
网站SEO黑链智能收集批量挂链软件V6.16+注册机
FTP密探+批量挂链
描述中提到的“挂链过程next易混易错”是指在构建新链表的过程中,正确连接next指针可能会出现混淆和错误。这通常是由于在处理随机指针的同时还要处理常规的next指针,需要仔细管理两个指针的关系,以避免逻辑上的...
FTP密探%2B自动挂链完美破解FTP密探%2B自动挂链完美破解
FTP挂链工具是一种用于在互联网上进行文件传输的软件应用,它使得用户能够方便地将本地计算机上的文件上传到远程服务器,或者从服务器下载文件到本地。FTP(File Transfer Protocol)是互联网上的一种标准协议,专门...
苹果FTP批量查链挂链工具是一款专为苹果用户设计的高效工具,主要用于自动化地检查FTP服务器的连接状态和挂链情况。在IT行业中,FTP(File Transfer Protocol)是一种广泛使用的网络协议,允许用户通过网络传输文件...
"苹果FTP密探扫描+挂链"工具是针对SEO(Search Engine Optimization,搜索引擎优化)的专业工具,它结合了FTP扫描和链接挂载的功能,帮助用户更好地管理和优化其网站的搜索引擎排名。 FTP扫描功能主要是对目标...
【标题】:“批量扫描工具和批量挂链工具1”指的是在网络优化中使用的工具,主要用于提升网站权重和搜索引擎排名。这类工具通常包括两个主要功能:批量扫描和批量挂链。 【批量扫描工具】:批量扫描工具的主要作用...
2. **功能详解**:逐一解析挂链的各项功能,如SIM卡读取功能如何帮助用户在没有备用手机的情况下更换SIM卡,数据传输功能如何实现手机与其他设备的便捷互联,以及应急电源功能的容量和充电效率等。 3. **技术规格**...
黑帽SEO——FTP扫描工具+FTP挂链工具