Java 挂链 Hash表 手动实现

前些天一直在纠结的 挂链 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 楼 stchou 2010-11-19  

谢谢啦，我还没有注意到该问题，谢谢指导~

langyu 写道

1. 它的用处在哪，本意是做为set使用？
2. 这个方法可能会返回负数

public int getHashCode(Object data){            
    return data.hashCode()*32767%size;  
}  

3. 得注意放入对象的hashCode及equals方法

1 楼 langyu 2010-11-19  

1. 它的用处在哪，本意是做为set使用？
2. 这个方法可能会返回负数

public int getHashCode(Object data){            
    return data.hashCode()*32767%size;  
}  

3. 得注意放入对象的hashCode及equals方法