Java代码实现哈希表(google 公司的上机题)
1哈希表(散列)-Google上机题
1)看一个实际需求,google公司的一个上机题:
2)有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址..),当输入该员工的id时,要求查
找到该员工的所有信息.
3)要求:不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列)
2哈希表的基本介绍
散列表(Hashtable,也叫哈希表),是根据关键码值(Keyvalue)而直接进行访问的数据结构。也就是说,它通
过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组
叫做散列表。
3.google公司的一个上机题:
有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,名字,住址..),当输入该员工的id时,
要求查找到该员工的所有信息.
要求:
1)不使用数据库,,速度越快越好=>哈希表(散列)
2)添加时,保证按照id从低到高插入
3)使用链表来实现哈希表,该链表不带表头[即:链表的第一个结点就存放雇员信息]
4)思路分析并画出示意图
5)代码实现
publicclassHashTableDemo{ publicstaticvoidmain(String[]args){ HashTablehashTable=newHashTable(7); Stringkey=""; Scannerscanner=newScanner(System.in); while(true){ System.out.println("add:添加雇员"); System.out.println("list:查看雇员"); System.out.println("find:查找雇员"); System.out.println("del:删除雇员"); System.out.println("exit:退出"); key=scanner.next(); switch(key){ case"add": System.out.println("请输入id:"); intid=scanner.nextInt(); System.out.println("请输入名字:"); Stringname=scanner.next(); Empemp=newEmp(id,name); hashTable.add(emp); break; case"list": hashTable.list(); break; case"find": System.out.println("请输入id:"); intid2=scanner.nextInt(); hashTable.findEmpById(id2); break; case"del": System.out.println("请输入id:"); intid3=scanner.nextInt(); hashTable.del(id3); break; case"exit": System.exit(10); default: break; } } } }
//emp classEmp{ publicintid; publicStringname; publicEmpnext; publicEmp(intid,Stringname){ super(); this.id=id; this.name=name; } }
//EmpLinkedList classEmpLinkedList{ //头指针,执行第一个Emp,因此我们这个链表的head,是直接指向第一个Emp privateEmphead; //id是自增长的 publicvoidadd(Empemp){ //如果是添加一个雇员 if(head==null){ head=emp; return; } //如果不是第一个 EmpcurEmp=head; while(true){ if(curEmp.next==null){ break; } curEmp=curEmp.next; } curEmp.next=emp; } publicvoidlist(intno){ if(head==null){ System.out.println("第"+(no+1)+"条链表为空!"); return; } System.out.println("第"+(no+1)+"条链表信息为:"); EmpcurEmp=head; while(true){ System.out.printf("=>id=%dname=%s\t",curEmp.id,curEmp.name); if(curEmp.next==null){ break; } curEmp=curEmp.next; } System.out.println(); } //根据id查找雇员 publicEmpfindEmpByid(intid){ if(head==null){ System.out.println("链表为空"); returnnull; } EmpcurEmp=head; while(true){ if(curEmp.id==id){ break; } if(curEmp.next==null){ System.out.println("遍历完了,没有找到!"); curEmp=null; break; } curEmp=curEmp.next; } returncurEmp; } //根据id进行删除 publicbooleandel(intid){ booleanflag=false; if(head==null){ System.out.println("当前链表为空!"); returnflag; } if(head.id==id){ head=null; flag=true; returnflag; } EmpcurEmp=head; while(true){ //找到了改雇员 if(curEmp.next.id==id){ curEmp.next=curEmp.next.next; curEmp.next=null; return(flag==false); } //没有找到 if(curEmp.next==null){ System.out.println("没有找改雇员!"); curEmp=null; returnflag; } curEmp=curEmp.next; } } }
//哈希表 classHashTable{ privateEmpLinkedList[]empLinkedListArr; privateintsize; publicHashTable(intsize){ super(); this.size=size; empLinkedListArr=newEmpLinkedList[size]; for(inti=0;i注意:不要把链表的第一个节点(头节点)删除了,不然整条链表没了。(还可以改良)
思考:如果id不是从低到高插入,但要求各条链表仍是从低到高,怎么解决?
到此这篇关于Java哈希表(google公司的上机题)的文章就介绍到这了,更多相关java哈希表内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票!
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。