[数据结构与算法]数据结构与算法——哈希表

1.基本介绍

• 散列表（Hash Table）,根据关键码值而直接进行访问的数据结构，它通常将关键码映射到表中一个位置来访问记录，以加快查找速度
  
• 由数组+链表构成

2.例题

一公司，当有新来员工时，将员工信息（id，name…）加入，当输入该员工id时，要查找到该员工的所有信息，要求不使用数据库，且越快越好

public class HashTabDome {

	public static void main(String[] args) {
		
		//涉及内部类的访问
		HashTabDome hashDome = new HashTabDome();
		HashTab hash = hashDome.new HashTab(7);
		
		Emp emp = hashDome.new Emp(2,"hh");
		hash.add(emp);
		
		Emp emp1 = hashDome.new Emp(4,"hh");
		hash.add(emp1);
		
		Emp emp2 = hashDome.new Emp(11,"hh");
		hash.add(emp2);
		
		hash.list();
		
		System.out.println("=============");
		
		hash.findEmpById(11);
		

	}
	
	class Emp{
		public int id;
		public String name;
		public Emp next;
		public Emp(int id,String name){
			super();
			this.id=id;
			this.name=name;
		}
	}
	
	class EmpLinkedList{
		private Emp head;
		/**
		 * 添加员工
		 * @param emp
		 */
		public void add(Emp emp){
			if(head==null){
				head=emp;
				return;
			}
			Emp curEmp=head;
			while(true){
				if(curEmp.next==null){
					break;
				}
				curEmp=curEmp.next;
			}
			curEmp.next=emp;
		}
		/**
		 * 遍历链表的雇员信息
		 */
		public void list(int no){
			if(head==null){
				System.out.println("第 "+(no)+" 条链表为空");
				return;
			}
			System.out.print("第 "+(no)+" 条链表为：");
			Emp curEmp = head;
			while(true){
				System.out.print("id="+curEmp.id+",name="+curEmp.name+"\t");
				if(curEmp.next==null){
					break;
				}
				curEmp=curEmp.next;
			}
			System.out.println();
		}
		/**
		 * 根据id查找雇员
		 * @param id
		 * @return
		 */
		public Emp findEmpById(int id){
			if(head==null){
				System.out.println("链表为空");
				return null;
			}
			Emp curEmp = head;
			while(true){
				if(curEmp.id==id){//找到
					break;
				}
				if(curEmp.next==null){
					curEmp=null;
					break;
				}
				curEmp=curEmp.next;
			}
			return curEmp;
		}
	}
	
	class HashTab{
		private EmpLinkedList[] empLinkedList;
		private int size;//有多少条链表
		
		public HashTab(int size){
			this.size=size;
			empLinkedList = new EmpLinkedList[size];
			//记得初始化每一个数组元素
			for(int i=0;i<empLinkedList.length;i++){
				empLinkedList[i]=new EmpLinkedList();
			}
		}
		
		/**
		 * 添加雇员
		 * @param emp
		 */
		public void add(Emp emp){
			//根据员工的id,得到该员工应当添加到那条链表
			int empLinkedListNo = hashFun(emp.id);
			//将emp添加到对应的链表中
			empLinkedList[empLinkedListNo].add(emp);
		}
		
		/**
		 * 遍历所有链表
		 */
		public void list(){
			for(int i=0;i<size;i++){
				empLinkedList[i].list(i);
			}
		}
		
		/**
		 * 根据输入的id查找雇员
		 * @param id
		 */
		public void findEmpById(int id){
			//使用散列函数确定那条链表查找
			int empLinkedListNo = hashFun(id);
			Emp emp=empLinkedList[empLinkedListNo].findEmpById(id);
			if(emp!=null){
				System.out.println("在第"+empLinkedListNo+"条链表中找到雇员id="+id);
			}else{
				System.out.println("在哈希表中，没有找到该雇员~");
			}
		}
		
		/**
		 * 编写散列函数 使用一个简单取模法
		 * @param id
		 * @return
		 */
		public int hashFun(int id){
			return id%size;
		}
	}

}