`
剑&箫
  • 浏览: 54583 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

挂链式Hash表的实现

    博客分类:
  • Java
阅读更多

 

       最基本的数据结构是数组和链表,这两种数据结构各有优缺点,比如数组,查找容易,插入困难;而链表插入容易,查找困难。在作画图板的重绘时用的是自定义队列保存图形的形状,在自定义队列中是包装了对数组的各种操作,当时没注意到这种自定义队列的优缺点。今天以保存自己作的简单的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);
		
	}

 

 

2
1
分享到:
评论
1 楼 Wuaner 2012-09-12  
楼主 你这里的 reHash, 是个什么概念? HashMap里是怎么做的那?应该不是这样简单的重造数组吧。

相关推荐

    挂链工具

    在IT行业中,"挂链工具"通常指的是用于网站优化,特别是搜索引擎优化(SEO)的一类软件或服务。这类工具的主要功能是帮助用户管理和优化他们网站的外部链接,也就是我们常说的"外链"。外链对于提升网站的搜索引擎...

    FTP批量挂链工具 批量挂黒链

    FTP批量挂链工具是一种针对网站管理的工具,主要用于在多个FTP服务器上快速部署特定的链接代码,例如“黑链”。这种工具通常被用于SEO优化、网站推广或是非法的黑帽SEO活动,因为“挂黒链”指的是在网站上不透明地...

    SEO挂链工具SEO挂链工具

    SEO(Search Engine Optimization)挂链工具是用于提升网站在搜索引擎排名的一种辅助软件。它通过自动或半自动的方式在互联网上创建指向目标网站的链接,以此提高网站的可见性和权重。在SEO领域,链接被认为是投票,...

    黑链专用ftp挂链工具

    "FTP挂链工具"就是这类操作的一种辅助软件,它利用FTP(File Transfer Protocol)协议,允许用户远程管理服务器上的文件,包括上传、下载、删除等操作。 FTP挂链工具的主要功能是帮助用户便捷地在目标服务器上植入...

    网站提供挂链

    【网站提供挂链】是指网站为用户或站长提供的一个服务,允许他们将自己的链接挂在网站上,以提升其网站的曝光度、流量或者搜索引擎排名。挂链通常被用作一种网络营销策略,通过与其他网站建立链接关系,可以提高自身...

    黑链工具包,全自动挂链,查链,PR查询,分类,自动补链

    黑链工具包,可以查询弱口令FTP,并实现全自动挂链,查链,PR查询,分类,掉链自动补链等等功能,是目前最好用,最稳定的黑链工具.

    FTP扫描工具挂链专用

    FTP扫描工具有时会被滥用,用于在未授权的情况下在FTP服务器上放置恶意链接,这种行为被称为黑帽SEO,会对被挂链的网站和网络环境带来负面影响。 为了有效利用FTP扫描工具,用户需要了解以下知识点: 1. **FTP协议...

    批量扫描工具和批量挂链工具

    这是一种seo的工具,但不建议使用。望大家适量用吧。

    苹果FTP批量扫描,附带批量挂链软件

    FTP批量扫描技术是一种网络工具,主要用于自动化地查找和连接FTP服务器,从而实现快速搜索和管理大量FTP站点。在IT行业中,这项技术常被用于网站管理员、SEO专家或网络安全专业人士进行大规模的数据采集、备份或者...

    ftp暴力破解 挂链工具

    ftp暴力破解 挂链工具 暴力破解功能异常强大 ,挂链工具有时候需要配合手动比较好,提高网站权重的必备shi

    网站SEO黑链智能收集批量挂链软件V6.16+注册机

    网站SEO黑链智能收集批量挂链软件V6.16+注册机

    FTP密探+批量挂链.zip

    FTP密探+批量挂链

    拷贝具有随机指针节点的链表,

    描述中提到的“挂链过程next易混易错”是指在构建新链表的过程中,正确连接next指针可能会出现混淆和错误。这通常是由于在处理随机指针的同时还要处理常规的next指针,需要仔细管理两个指针的关系,以避免逻辑上的...

    FTP密探%2B自动挂链完美破解

    FTP密探%2B自动挂链完美破解FTP密探%2B自动挂链完美破解

    FTP挂链工具

    FTP挂链工具是一种用于在互联网上进行文件传输的软件应用,它使得用户能够方便地将本地计算机上的文件上传到远程服务器,或者从服务器下载文件到本地。FTP(File Transfer Protocol)是互联网上的一种标准协议,专门...

    苹果FTP批量查链挂链工具

    苹果FTP批量查链挂链工具是一款专为苹果用户设计的高效工具,主要用于自动化地检查FTP服务器的连接状态和挂链情况。在IT行业中,FTP(File Transfer Protocol)是一种广泛使用的网络协议,允许用户通过网络传输文件...

    苹果FTP密探扫描+挂链

    "苹果FTP密探扫描+挂链"工具是针对SEO(Search Engine Optimization,搜索引擎优化)的专业工具,它结合了FTP扫描和链接挂载的功能,帮助用户更好地管理和优化其网站的搜索引擎排名。 FTP扫描功能主要是对目标...

    批量扫描工具和批量挂链工具1

    【标题】:“批量扫描工具和批量挂链工具1”指的是在网络优化中使用的工具,主要用于提升网站权重和搜索引擎排名。这类工具通常包括两个主要功能:批量扫描和批量挂链。 【批量扫描工具】:批量扫描工具的主要作用...

    电信设备-多功能移动手机挂链.zip

    2. **功能详解**:逐一解析挂链的各项功能,如SIM卡读取功能如何帮助用户在没有备用手机的情况下更换SIM卡,数据传输功能如何实现手机与其他设备的便捷互联,以及应急电源功能的容量和充电效率等。 3. **技术规格**...

    黑帽SEO——FTP扫描工具+FTP挂链工具

    黑帽SEO——FTP扫描工具+FTP挂链工具

Global site tag (gtag.js) - Google Analytics