数据结构之哈希表的使用

今天初步学习了数据结构中的哈希表。
首先在概念上，哈希表和数组队列，链表一样，是一种用来储存数据的结构。它存在的价值是，当需要储存的数据的数量非常多时，比如腾讯储存qq号时，查找/删除某个数据就需要很大的时间复杂度。此时，就需要用特定的方式储存数据，这样就能大大降低查找的时间复杂度。比如，今天，用一种简单的方式，比如id号（三位数），将三位数上的数字加起来，然后将相同的数放在一个链表里，链表的每个节点储存了一个链表，将相同的数字按顺序排放。
下面是哈希表的源代码。

public class Hash {
		private NodeLinked array[] = new NodeLinked[100];
		//添加数据
		public void add(Colleger obj){
			String num = obj.id+"";
			int count = 0;
			for(int i=0;i<num.length();i++){
				count += ((int)num.charAt(i)-48);
			}
			if(array[count] == null){
				NodeLinked temp = new NodeLinked();
				temp.create(obj);
				array[count] =temp ;
			}else{
				array[count].create(obj);
			}
//			for(int i = 0;i<array[count].size;i++){
//			System.out.println(((Colleger)array[count].find(i).getObj()).id);
//			}
		}
	    //查找数据
		public Colleger get(int id){
			String num = id+"";
			int count = 0;
			for(int i=0;i<num.length();i++){
				count += ((int)num.charAt(i)-48);
			}
			for(int i = 0;i<array[count].size;i++){
				if(((Colleger)array[count].show(i)).id == id){
					return (Colleger)array[count].show(i);
				}
				}
			return null;
		}
		//删除数据
		public void delete(int id){
			String num = id+"";
			int count = 0;
			for(int i=0;i<num.length();i++){
				count += ((int)num.charAt(i)-48);
			}
			for(int i = 0;i<array[count].size;i++){
				if(((Colleger)array[count].show(i)).id == id){
					Colleger temp = (Colleger)array[count].delete(i);
					System.out.println(temp.name);
				}
				}
		}
}

然后还测试了一下哈希表的性能与普通数组的比较，代码如下。

public class Main {

	public static void main(String[] args) {
		Hash h = new Hash();
		//h.delete(173);
		//System.out.println(temp.name);
		LinkedList<Colleger> link = new  LinkedList<Colleger>();
		int num = 10000000;
		long start = System.currentTimeMillis();
		for(int i = 0;i<num;i++){
			link.add(new Colleger(i,"Colleger"+i));
		}
		long end = System.currentTimeMillis();
		System.out.println("这是链表的创建时间"+(end-start));
		long start2 = System.currentTimeMillis();
		for(int i = 0;i<num;i++){
			h.add(new Colleger(i,"Colleger"+i));
		}
		long end2 = System.currentTimeMillis();
		System.out.println("这是哈希表的创建时间"+(end2-start2));
		long start3 = System.currentTimeMillis();
		link.get(8000000);
		long end3 = System.currentTimeMillis();
		System.out.println("这是链表的查找时间"+(end3-start3));
		long start4 = System.currentTimeMillis();
		h.get(8000000);
		long end4 = System.currentTimeMillis();
		System.out.println("这是哈希表的查找时间"+(end4-start4));
	}

}

运行结果如下[img]

 [/img]