hash表简单实现

hash表简单实现

    1、什么是哈希表？
    哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

   2、如何实现实现哈希表

    哈希表的做法其实很简单，就是把Key通过一个固定的算法函数即所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。当然，不同的数据可能会出现相同的下标，那么就把这些数据用链表“连”起来放入对应下标数组。

     当使用哈希表进行查询等操作的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间便利数组存放的链表获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位  

   3、简单实现

    因为只是为了实现一体现这种思想的哈希表，所以写了一个简单的hashForUI实现方法，以下是具体的代码：

 

 

   用户类：这里没有使用泛型，只是简单的希望哈希表能够存储用户类的数据，并且以用户的ID来作为索引，进行添加和查找

/**
 * 用户信息类
 */
public class UserInfo {
	
    private String userName;
	private int id;
	
	//构造函数
	public UserInfo(String userName,int id){
		this.userName = userName;
		this.id = id;
	}
	
    public String getUserName() {
		return userName;
	}
	public void setUserName(String userName) {
		this.userName = userName;
	}
	public int getId() {
		return id;
	}
	public void setId(int id) {
		this.id = id;
	}

}

 

   节点类：这是用来作为存放在数组中的链表结点，每个节点存放的数据类型是UserInfo，有一个后继指向下一个链表节点

/**
 * 结点类，作为存放在数组中的链表结点
 *
 */
public class Node {
	
	private UserInfo user;
	private Node next;
	
	//构造函数
	public Node(UserInfo user ,Node next){
		this.user = user;
		this.next = next;
	}
	
	public UserInfo getUser() {
		return user;
	}
	public void setUser(UserInfo user) {
		this.user = user;
	}
	public Node getNext() {
		return next;
	}
	public void setNext(Node next) {
		this.next = next;
	}
	
}

 

   这是具体的实现方法：

   这里关键码值使用的是UserInfo的ID,哈希函数也只是简单的

/**
 * 构建hashForUI表，实现insert，delete,rehash等方法
 */
public class hashForUI{
	private static int length = 10;//创建哈希表的数组，初始化长度是length;
	public static Node[] array = new Node[length]; 
	private int count = 0;//表长
	private double loadFactor = 0.5;//装载因子
	
	//插入元素
	public void insert(UserInfo user){
		int index = calculate(user.getId());
		Node node = new Node(user,null);
		node.setNext(array[index]);
		array[index] = node;
		count ++;
		//判断是否需要rehash
		rehash();	
		}
	}
	//删除元素
	public boolean delete(UserInfo user){
		int index = calculate(user.getId());
		if(array[index] == null){//数组为空
			return false; 
		}else if(array[index].getUser().getId() == user.getId()){//第一个元素就是所找
			array[index] = array[index].getNext();
		}else{//第一个不是
			Node currentFirst = array[index];
			Node currentSecond = currentFirst.getNext();
			while(currentSecond != null){
				if(currentSecond.getUser().getId() == user.getId()){//第二个即所找
					currentFirst.setNext(currentSecond.getNext());
					count --;
					return true;
				}else{//后移
					currentFirst = currentSecond;
					currentSecond = currentSecond.getNext();					
				}
			}
		}
		return false;
	}
	//查找元素
	public UserInfo find(int id){
		int index = calculate(id);
		//System.out.println(index+"  "+id);
		for(Node current = array[index] ;current != null;current = current.getNext()){
			if(current.getUser().getId() == id){
				return current.getUser();
			}	
		}
		return null;	
	}
	//重新构建哈希表，每次增加数组长度100
	public void rehash(){
		//System.out.println((double)length/(double)count);
		if(((double)length/(double)count) < loadFactor){
			length = length*2;
			System.out.println(length);
			Node[] arrayCopy = new Node[length];
			//直接重新插入		
			for(int i = 0;i < array.length;i++){
				Node node = array[i];
				while(node != null){
					//System.out.println("&&&");
					UserInfo user = node.getUser(); 
					int index = calculate(user.getId());
					Node n = new Node(user,null);
					n.setNext(arrayCopy[index]);
					arrayCopy[index] = n;
					node = node.getNext();
				}
			}
			array = arrayCopy;
		}
	}
	//哈希表长
	public int length(){
		return count;
	}
	//哈希函数
	public int calculate(int x){
		return x%length;
		//return x.hashCode();
	}
	
}

 

/**
 * 测试类
 */
public class test {
	public static void main(String [] args){
		hashForUIh = new hashForUI();
		Long startTime1=System.currentTimeMillis();//记录开始时间
		for(int i = 0;i<650000;i++){
			UserInfo user = new UserInfo("User"+i,i);
			h.insert(user);
		}
		Long endTime1=System.currentTimeMillis();//记录结束时间
		System.out.println("hash插入元素所用时间"+(endTime1-startTime1));
		UserInfo user1 = new UserInfo("User"+1299,1299);
		boolean state = h.delete(user1);
		System.out.println(state);
		
		Long startTime2=System.currentTimeMillis();//记录开始时间
		user1 = h.find(1333);
		Long endTime2=System.currentTimeMillis();//记录结束时间
		System.out.println(user1.getUserName()+"    "+user1.getId());
		System.out.println("hash查找元素所用时间"+(endTime2-startTime2));	
	}
}

 运行结果：

hash插入元素所用时间1310
true
User1333    1333
hash查找元素所用时间0

 

如果输出每一次reHash后数组长度的改变，会发现当数据达到65W时，建立的数组大小是32W,也是相当巨大的………………

总之，只是简单实现了hash的思想，至于算法方面，有待提高~~~