哈希表（散列）
解决一个问题：
有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址…),当输入该员工的 id 时,要求查找到该员工的所有信息.
要求: 不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列）
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
看第二张图可知，哈希表这种数据结构实际上是把一维数组和单链表结合，数组中不存放数字而是存放一条单链表，在存储数据时，按照id号把数据散存在某一条单链表中。
散列函数有很多，这里用的是id取模的方式。
本问题的代码包括三个部分：员工节点、一条单链表、单链表数组管理器。
代码
员工节点
java">
//员工节点，存储id和姓名
class Emp{
public int id;
public String name;
public Emp next;
public Emp(int id, String name) {
this.id = id;
this.name = name;
}
}
单链表，包含增删改查，其中按顺序增加和删除时要考虑头节点为空，只有一个头节点和头节点的next为空的情况，因为在代码中没有专门的头节点，头节点就是第一个员工，而按顺序添加和删除需要找到对应节点的前一个节点，就要额外考虑情况。。
java">//员工单链表
class EmpLinkedList{
public Emp head;
public EmpLinkedList(){
this.head=null;
}
//按照顺序加入员工
public void insert(Emp emp){
//链表是空的，直接插
if(head==null){
head=emp;
return;
}
//要插在头节点位置
if(head.id>emp.id){
emp.next=head;
head=emp;
return;
}
//链表只有一个头节点且要插在头节点后面
if(head.next==null && head.id<=emp.id){
head.next=emp;
return;
}
Emp curEmp=head;
while (true){
//找到要插的前一个
if(curEmp.next.id>emp.id){
emp.next=curEmp.next;
curEmp.next=emp;
return;
}
curEmp=curEmp.next;
//插在链表最后
if(curEmp.next==null){
curEmp.next=emp;
return;
}
}
}
//按照id删除员工
public void del(int id){
if(head==null){
return;
}
if(head.next==null){
head=null;
return;
}
if(head.id==id){
head=head.next;
return;
}
Emp curEmp=head;
while (true){
if(curEmp.next.id==id){
curEmp.next=curEmp.next.next;
return;
}
curEmp=curEmp.next;
if(curEmp.next==null){
return;
}
}
}
//按照id查找员工,没找到就返回null
public Emp find(int id){
//链表为空，没找到他
if(head==null){
return null;
}
Emp curEmp=head;
while (true){
if(curEmp.id==id){
break;
}
curEmp=curEmp.next;
if(curEmp==null){
break;
}
}
return curEmp;
}
//增加新员工,直接加在最后
public void add(Emp emp){
//如果是第一名员工
if(head==null){
head=emp;
return;
}
//如果不是第一名员工，就要先找到链表的最后
Emp curEmp=head;
while (true){
if(curEmp.next==null){
curEmp.next=emp;
break;
}
curEmp=curEmp.next;
}
}
//遍历
public void list(int no){
if(head==null){
System.out.println("第"+(no+1)+"链表为空");
return;
}
Emp curEmp=head;
System.out.print("第"+(no+1)+"链表的数据为:");
while (true){
System.out.printf("=>id:%d;name:%s\t",curEmp.id,curEmp.name);
if(curEmp.next==null){
System.out.println("");
break;
}
curEmp=curEmp.next;
}
}
}
操作数组，调用单链表的方法，要注意初始化时要单独创建每一条单链表，也就是既要初始化数组，也要初始化每一条单链表。
java">//哈希表，多条链表管理器
class HashTab{
public EmpLinkedList[] hashTab;
public int size;
public HashTab(int size){
this.size=size;
//初始化数组
hashTab=new EmpLinkedList[size];
//初始化链表
for (int i = 0; i <size ; i++) {
hashTab[i]=new EmpLinkedList();
}
}
//按顺序插入员工
public void insert(Emp emp){
int i = hashFan(emp.id);
hashTab[i].insert(emp);
}
//删除员工
public void del(int id){
int i=hashFan(id);
hashTab[i].del(id);
}
//查找员工
public void find(int id){
int i = hashFan(id);
Emp emp = hashTab[i].find(id);
if(emp==null){
System.out.println("没有该员工的信息");
}else {
System.out.println("他的id："+emp.id+"，他的姓名："+emp.name);
}
}
//增加新员工
public void add(Emp emp){
int hashTabIndex=hashFan(emp.id);
hashTab[hashTabIndex].add(emp);
}
//遍历取得全部员工信息
public void list(){
for (int i = 0; i <size ; i++) {
hashTab[i].list(i);
}
}
//取得在哪条链表上增加
public int hashFan(int id){
return id%size;
}
}
测试代码
java">/**
* 使用哈希表存储公司员工信息
*/
public class HashTabDemo {
public static void main(String[] args) {
//创建员工信息表
HashTab hashTab=new HashTab(7);
Scanner sc=new Scanner(System.in);
while (true){
System.out.println("i:按顺序添加员工；a:添加员工；l：显示员工；f:查找员工；d:删除员工；e：退出");
String n=sc.next();
switch (n){
case "i":
System.out.println("请输入id：");
int id=sc.nextInt();
System.out.println("请输入姓名：");
String name=sc.next();
Emp emp=new Emp(id,name);
hashTab.insert(emp);
break;
case "a":
System.out.println("请输入id：");
id=sc.nextInt();
System.out.println("请输入姓名：");
name=sc.next();
emp=new Emp(id,name);
hashTab.add(emp);
break;
case "l":
hashTab.list();
break;
case "f":
System.out.println("请输入id：");
id=sc.nextInt();
hashTab.find(id);
break;
case "d":
System.out.println("请输入id：");
id=sc.nextInt();
hashTab.del(id);
break;
case "e":
sc.close();
System.exit(0);
default:
break;
}
}
}
}
