HashTable的Java实现及性能对比

1、HashTable的概述

   从基本层面讲，数据结构有数组与链表两种。数组具有查找快，但插入耗时的特点；链表具有插入快，但查找费时的特点。有没有可能在查找与插入之间取得平衡呢？哈希表的诞生回答了这个问题。

   构建一个好的哈希表，主要得考量哈希函数与解决冲突这两面。不管是哈希函数，还是解决冲突，往深里挖都是可以走得很远很远。

 

2、实现哈希表的思路

    直接上思维导图，思维上建立了，写个哈希表就不那么费力了。

 

 

public class HashTable<K, V> {
	private int size;//元素个数
	private static int initialCapacity=16;//HashTable的初始容量
	private Entry<K,V> table[];//实际存储数据的数组对象
	private static float loadFactor=0.75f;//加载因子
	private int threshold;//阀值，能存的最大的数max=initialCapacity*loadFactor
	
	//构造指定容量和加载因子的构造器
	public HashTable(int initialCapacity,float loadFactor){
		if(initialCapacity<0)
			throw new IllegalArgumentException("Illegal Capacity:"+initialCapacity);
		if(loadFactor<=0)
			throw new IllegalArgumentException("Illegal loadFactor:"+loadFactor);
		this.loadFactor=loadFactor;
		threshold=(int)(initialCapacity*loadFactor);
		table=new Entry[threshold];
	}
	
	//使用默认参数的构造器
	public HashTable(){
		this(initialCapacity,loadFactor);
	}
	
	//放入元素
	public boolean put(K key,V value){
		//取得在数组中的索引值
		int hash=key.hashCode();
		Entry<K,V> temp=new Entry(key,value,hash);
		if(addEntry(temp,table)){
			size++;
			return true;
		}
		return false;
	}
	
	//添加元素到指定索引处
	private boolean addEntry(HashTable<K, V>.Entry<K, V> temp,
			HashTable<K, V>.Entry<K, V>[] table) {
		//1.取得索引值
		int index=indexFor(temp.hash,table.length);
		//2.根据索引找到该位置的元素
		Entry<K,V> entry=table[index];
		//2.1非空，则遍历并进行比较
		if(entry!=null){
			while(entry!=null){
				if((temp.key==entry.key||temp.key.equals(entry.key))&&temp.hash==entry.hash
						&&(temp.value==entry.value||temp.value.equals(entry.value)))
						return false;
				else if(temp.key!=entry.key&&temp.value!=entry.value){
					if(entry.next==null)
						break;
					entry=entry.next;
				}
			}
			//2.2链接在该索引位置处最后一个元素上
			addEntryLast(temp,entry);
		}
		//3.若空则直接放在该位置
		setFirstEntry(temp,index,table);
		//4.插入成功，返回true
		return true;
	}
	
	//链接元素到指定索引处最后一个元素上
	private void addEntryLast(HashTable<K, V>.Entry<K, V> temp,
			HashTable<K, V>.Entry<K, V> entry) {
		if(size>threshold)
			reSize(table.length*4);
		entry.next=temp;
	}

	//初始化索引处的元素值
	private void setFirstEntry(HashTable<K, V>.Entry<K, V> temp, int index,
			HashTable<K, V>.Entry<K, V>[] table) {
		if(size>threshold)
			reSize(table.length*4);
		table[index]=temp;
		//注意指定其next元素，防止多次使用该哈希表时造成冲突
		temp.next=null;
	}

	//扩容容量
	private void reSize(int newSize) {
		Entry<K,V> newTable[]=new Entry[newSize];
		threshold=(int) (loadFactor*newSize);
		for(int i=0;i<table.length;i++){
			Entry<K,V> entry=table[i];
			//数组中，实际上每个元素都是一个链表，所以要遍历添加
			while(entry!=entry){
				addEntry(entry,newTable);
				entry=entry.next;
			}
		}
		table=newTable;
	}


	//计算索引值
	private int indexFor(int hash, int tableLength) {
		//通过逻辑与运算，得到一个比tableLength小的值
		return hash&(tableLength-1);
	}
	
	//取得与key对应的value值
	protected V get(K k){
		Entry<K,V> entry;
		int hash=k.hashCode();
		int index=indexFor(hash,table.length);
		entry=table[index];
		if(entry==null)
			return null;
		while(entry!=null){
			if(entry.key==k||entry.key.equals(k))
				return entry.value;
			entry=entry.next;
		}
		return null;
	}
	
	//内部类，包装需要存在哈希表中的元素
	class Entry<K,V>{
		Entry<K,V> next;
		K key;
		V value;
		int hash;
		
		Entry(K k,V v,int hash){
			this.key=k;
			this.value=v;
			this.hash=hash;
		}
	}
	
}

 

 注：（1）本代码中采用的hash算法是:第一步采用JDK给出的hashcode()方法，计算加入对象的一个哈希值，其中hashcode()在Object类中定义为：public native int hashcode();说明这是一个本地方法，它的具体实现跟本地机器相关。第二步是通过hashcode&(table.lenth-1)，返回一个比length小的值，即为索引值。

        （2）该代码解决冲突的办法是采用的“挂链法”。

        （3）代码中的加载因子loadFactor是参见HashMap的源码，据说0.75是一个耗时与占用内存的折中值。

        （4）插入元素时，若索引处位置非空，要与已有元素进行对比，根据java规范，并不强制不相等的两个对象拥有不相等的hashcode值，因此还需进一步调用equals方法进行判断。

 

3、与数组与链表进行性能对比

     数组直接采用的java.util.ArrayList;

     链表直接采用的java.util.LinkedList;

     代码如下：

public class Main {
	
	public static ArrayList<User> al;
	public static LinkedList<User> ll;

	public static void main(String[] args) {
		Main m = new Main();
		
		al = new ArrayList<User>();
		ll = new LinkedList<User>();
		
		m.insert();
		m.find(9999);
		
	}
	
	public void insert(){
		long l;
		//测试数组队列插入时间
		l = System.currentTimeMillis();
		for(int i=0; i<1000000; i++){
			User u = new User(i,"abc"+i);
			al.add(u);
		}
		l = System.currentTimeMillis() - l;
		System.out.println("ArrayList插入（用时）："+l);
		
	    //测试链表插入时间
		l = System.currentTimeMillis();
		for(int i=0; i<1000000; i++){
			User u = new User(i,"abc"+i);
			ll.add(u);
		}
		l = System.currentTimeMillis()-l;
		System.out.println("LinkedList插入（用时）："+l);
		
	}
	
	public void find(int id){
		long l;
		
		//测试数组队列查找时间
		l = System.currentTimeMillis();
		for(int i=0; i<1000000; i++){
			if(al.get(i).getId() == id){
				System.out.println("find it!");
				l = System.currentTimeMillis()-l;
				System.out.println("ArrayList查找时间："+l);
				break;
			}
		}

		//测试链表查找时间
		l = System.currentTimeMillis();
		for(int i=0; i<1000000; i++){
			if(ll.get(i).getId() == id){
				System.out.println("find it!");
				l = System.currentTimeMillis()-l;
				System.out.println("LinkedList查找时间："+l);
				break;
			}
		}	
	}
	
	//测试用的User类
	class User{
		private int id;
		private String name;
		
		public User(int id, String name){
			this.id = id;
			this.name = name;
		}
		
		public int getId(){
			return id;
		}
	}
}

 运行结果：

 现在来看看哈希表：

public class Manager {

	public static void main(String[] args) {
		HashTable<String,String> ht=new HashTable<String,String>();
		long beginTime=System.currentTimeMillis();
		for(int i=0;i<1000000;i++){
			ht.put(i+"", "test"+i);
		}
		long endTime=System.currentTimeMillis();
		System.out.println("The HashTable insert time is:"+(endTime-beginTime));
		
		long beginTime2=System.currentTimeMillis();
		ht.get(9999+"");
		long endTime2=System.currentTimeMillis();
		System.out.println("The HashTable Search time is:"+(endTime2-beginTime2));
	}

}

 运行结果：

 注：同是插入1000000数量级的元素，同是查找第9999个元素。其时间效率对比应该是很明显的。

 

4、总结及感言

     不弄懂散列表怎敢说自己是学习了数据结构的？

上学期的债今天终于偿还了。这一学习过程，深深体会到散列表这一数组与链表的综合体，的确是非常奇妙的。当然哈希表只是一个开始，是数组与链表的一个进阶。后面更博大精深的是树与图。

这一个过程中，首先是找到了两篇很有质量的博客，对于我理解散列表起到了关键作用，时常感慨互联网的伟大，就是每个互联网的参与者都贡献出自己的智慧，薪火相传，终究会酝酿出更大的智慧。

另一个就是查看源代码，才真的感受到代码之美，源代码聚集了无数程序员的智慧，其精炼，其逻辑的严密性，是不看不知道，一看就好中意。看来要持续进阶学习，源代码算是一条康庄大道。

 

参考资料：

JDK API Hashtable Hashtable源代码  

深入Java集合学习系列：HashMap的实现原理

Hash表分析以及Java实现