挂链式Hash表的实现

 

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

 

 

评论

1 楼 Wuaner 2012-09-12  

楼主 你这里的 reHash， 是个什么概念？ HashMap里是怎么做的那？应该不是这样简单的重造数组吧。