哈希表

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

通过谷歌的一个上机题来讲述哈希表的应用实例
题目：
有一个公司，当有新的员工来报道时，要求将该员工的信息加入（id、性别、年龄、名字、住址等），当输入该员工的id时，要求查找到该员工所有信息。
要求：不使用数据库，速度越快越好=>哈希表(散列)
添加时，保证按照id从低到高插入[课后思考：如果id不是从低到高插入，但要求各链表仍是从低到高，怎么解决？]
1）使用链表来实现哈希表，该链表不带表头[即：链表的第一个结点就存放雇员信息]
2）思路分析并画出示意图
3）代码实现[增删改查（显示所有员工，按id查询）]

import java.util.Scanner;

public class HashTabDemo {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        //创建hash表
        HashTab hashTab=new HashTab(7);

        //写菜单
        String key="";
        Scanner scanner=new Scanner(System.in);
        while(true) {
            System.out.println("add: 添加雇员");
            System.out.println("list: 显示雇员");
            System.out.println("find: 查找雇员");
            System.out.println("exit: 退出系统");

            key=scanner.next();
            switch(key) {
            case "add":
                System.out.println("输入id");
                int id=scanner.nextInt();
                System.out.println("输入名字");
                String name=scanner.next();
                //创建雇员
                Emp emp=new Emp(id,name);
                hashTab.add(emp);
                break;
            case "list":
                hashTab.list();
                break;
            case "find":
                System.out.println("请输入要查找的id");
                id=scanner.nextInt();
                hashTab.findEmpById(id);
                break;
            case "exit":
                scanner.close();
                System.exit(0);
            default:
                break;
            }
        }
    }
}

    //创建HashTab管理多条链表
    class HashTab{
        private EmpLinkedList[] empLinkedListArray;
        private int size;      //表示有多少条链表

        //构造器
        public HashTab(int size) {
            this.size=size;
            //初始化empLinkedListArray
            empLinkedListArray=new EmpLinkedList[size];
            //?留坑，未将每个链表都进行初始化
            for(int i=0;i<size;i++) {
                empLinkedListArray[i]=new EmpLinkedList();
            }
        }

        //添加雇员
        public void add(Emp emp) {
            //根据员工的id，得到该员工应当添加到哪条链表
            int empLinkedListNO=hashFun(emp.id);
            //将emp添加到对应的链表中
            empLinkedListArray[empLinkedListNO].add(emp);
        }

        //遍历所有的链表，遍历hashtab
        public void list() {
            for(int i=0;i<size;i++) {
                empLinkedListArray[i].list(i);
        }
    }
        //根据输入的id，查找雇员
        public void findEmpById(int id){
            //使用散列函数确定到哪条链表查找
             int empLinkedListNO=hashFun(id);
             Emp emp=empLinkedListArray[empLinkedListNO].findEmpById(id);
             if(emp!=null) {
                 //找到
                 System.out.printf("在第%d条链表中找到雇员 id=%d\n",(empLinkedListNO+1),id);
             }else {
                 System.out.printf("在哈希表中，未找到该雇员");
             }
            }
        //编写一个散列函数，使用一个简单取模法
        public int hashFun(int id) {
            return id%size;
        }
    }

    //表示一个雇员
    class Emp{
        public int id;
        public String name;
        public Emp next;   //next默认未null
        public Emp(int id,String name) {
            super();
            this.id=id;
            this.name=name;
    }
}


    //创建一个EmpLinkedList,表示链表
    class EmpLinkedList{
        //头指针，执行第一个Emp，因此我们这个链表的head是直接指向第一个Emp
        private Emp head;//默认为null

        //添加雇员到链表
        //说明
        //1.假定，当添加固雇员时，id是自增长，即id的分配总是从小到大
        //因此我们将雇员直接加入到本链表的最后即可
        public void add(Emp emp) {
            //如果是添加第一个雇员
            if(head==null) {
                head=emp;
                return;
            }
            //如果不是第一个，使用辅助指针，定位到最后
            Emp curEmp=head;
            while(true) {
                if(curEmp.next==null) {
                    break;
                }
                curEmp=curEmp.next;    //后移
            }
            //退出时直接将emp加入链表
            curEmp.next=emp;
            }

        //遍历链表的雇员信息
        public void list(int no) {
            if(head==null) {
                //说明链表为空
                System.out.println("第 "+(no+1)+" 链表为空");
                return;
            }
            System.out.println("第 "+(no+1)+" 链表信息为");
            Emp curEmp=head; //辅助指针
            while(true) {
                System.out.printf("=>id=%d name=%s\t",curEmp.id,curEmp.name);
                if(curEmp.next==null) {//说明curEmp已经是最后结点
                    break;
                }
                curEmp=curEmp.next;  ///后移，遍历
            }
            System.out.println();
        }
        //根据id查找雇员
        //如果查找到，就返回true，如果没找到，就返回null
        public Emp findEmpById(int id) {
            //判断链表是否为空
            if(head==null) {
                System.out.println("链表为空");
                return null;
            }
            //辅助指针
            Emp curEmp=head;
            while(true) {
                if(curEmp.id==id) {
                    //找到
                    break;   //这时curEmp就指向要查找的雇员
                }
                //退出
                if(curEmp.next==null) {//说明遍历当前链表没有找到该雇员
                    curEmp=null;
                    break;
                }
                curEmp=curEmp.next;
            }
            return curEmp;
        }
    }

//6.7 手打，懵逼，不理解hashtable的原理；