Java简单实现链式哈希表

文章目录

什么是哈希表

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

试题

有一个公司，当有新员工来报道时，要求将员工的信息加入（id，性别，年龄，名字，住址），当输入员工的id时要求查找到员工的所有信息。
要求：
不使用数据库，速度越快越好。

代码

Emp：雇员类模拟结点

publicclassEmp{privateint id;privateString name;privateEmp next;//默认为空publicEmp(int id,String name){this.id = id;this.name = name;}
    getter and setter 方法
}

EmpLinkList：模拟一条链表

publicclassEmpLinkList{privateEmp head;//默认为空//添加雇员到链表末尾publicvoidaddEmp(Emp emp){if(head ==null){//添加第一个雇员
            head = emp;return;}//添加的不是第一个雇员Emp temp = head;//辅助指针while(true){if(temp.getId()== emp.getId()){System.out.println("该id已经存在");return;}if(temp.getNext()==null){//遍历到链表最后break;}
            temp = temp.getNext();}
        temp.setNext(emp);//添加雇员}//遍历链表publicvoidshowList(int no){if(head ==null){System.out.println("第"+no+"号链表为空");return;}Emp temp = head;System.out.print("第"+no+"号链表信息为：");while(true){System.out.print(" => id="+temp.getId()+",name="+temp.getName());if(temp.getNext()==null){break;}
            temp = temp.getNext();//后移遍历}System.out.println();}//根据id查找雇员publicEmpqueryById(int id){if(head ==null){System.out.println("id不存在");returnnull;}Emp temp = head;while(true){if(temp.getId()== id){break;}if(temp.getNext()==null){returnnull;}
            temp = temp.getNext();}return temp;}//根据id删除雇员publicvoiddeleteById(int id){if(head ==null){System.out.println("id不存在");return;}Emp temp = head;while(true){if(head.getId()== id){
                head = temp.getNext();System.out.println("删除成功");return;}if(temp.getNext().getId()== id){
                temp.setNext(temp.getNext().getNext());System.out.println("删除成功");return;}
            temp = temp.getNext();if(temp.getNext()==null){System.out.println("id不存在");break;}}}}

HashTable：模拟哈希表

publicclassHashTable{privateEmpLinkList[] empLinkListsArray;privateint size;publicHashTable(int size){this.size = size;this.empLinkListsArray =newEmpLinkList[size];for(int i =0; i < size; i++){
            empLinkListsArray[i]=newEmpLinkList();}}//添加雇员到hash表publicvoidadd(Emp emp){//根据员工id判断应该添加到哪条链表int empLinkListNo =hashFunc(emp.getId());
        empLinkListsArray[empLinkListNo].addEmp(emp);}//遍历hash表publicvoidshowHashTable(){for(int i =0; i <empLinkListsArray.length; i++){
            empLinkListsArray[i].showList(i);}}//根据输入id查找雇员publicvoidfindEmpById(int id){int empLinkListNo =hashFunc(id);Emp emp = empLinkListsArray[empLinkListNo].queryById(id);System.out.println(emp==null?"没有找到该雇员":"雇员的信息为:id="+emp.getId()+",name="+emp.getName());}//根据输入id删除雇员publicvoiddelete(int id){int empLinkListNo =hashFunc(id);
        empLinkListsArray[empLinkListNo].deleteById(id);}//散列函数:使用取模法publicinthashFunc(int id){return id % size;}}

测试类

publicclassTest{publicstaticvoidmain(String[] args){//创建hash表HashTable hash =newHashTable(7);String key ="";Scanner scanner =newScanner(System.in);while(true){System.out.println("add:添加雇员");System.out.println("show:显示雇员");System.out.println("find:查找雇员");System.out.println("delete:删除雇员");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 =newEmp(id,name);
                    hash.add(emp);break;case"show":
                    hash.showHashTable();break;case"find":System.out.println("请输入id");
                    id = scanner.nextInt();
                    hash.findEmpById(id);break;case"delete":System.out.println("请输入id");
                    id = scanner.nextInt();
                    hash.delete(id);break;case"exit":
                    scanner.close();System.exit(0);break;default:break;}}}}

输出结果

add:添加雇员
show:显示雇员
find:查找雇员
delete:删除雇员
exit:退出
add
请输入id
1
请输入雇员名字
张三

add
请输入id
8
请输入雇员名字
李四

add
请输入id
5
请输入雇员名字
王五

show
第0号链表为空
第1号链表信息为： => id=1,name=张三 => id=8,name=李四
第2号链表为空
第3号链表为空
第4号链表为空
第5号链表信息为： => id=5,name=王五
第6号链表为空

delete
请输入id
1
删除成功

show
第0号链表为空
第1号链表信息为： => id=8,name=李四
第2号链表为空
第3号链表为空
第4号链表为空
第5号链表信息为： => id=5,name=王五
第6号链表为空

exit

Process finished withexit code 0