简介
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
案例
有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,名字,住址..,当输入该员工的id时，要求查找到该员工的所有信息.
要求：
- 不使用数据库.速度越快越好=>哈希表(散列)
- 添加时，保证按照id从低到高插入
- 使用链表来实现哈希表,该链表不带表头
代码
class Employee {
public int id;
public String name;
public Employee next;
public Employee(int id, String name) {
this.id = id;
this.name = name;
}
}
class EmpLinkedList {
private Employee head;
/**
* 如果添加的员工已经存在，提醒
* 按照id从小到大的顺序添加
* @param employee 添加的员工对象
*/
public void add(Employee employee) {
if (head == null) {
head = employee;
return;
}
Employee temp = head;
if (head.next == null) {
if (temp.id > employee.id) {
employee.next = temp;
head = employee;
} else if (temp.id < employee.id) {
temp.next = employee;
} else {
System.out.println("id为" + employee.id + "的雇员已存在！");
}
return;
}
if (employee.id < head.id) {
employee.next = temp;
head = employee;
return;
}
boolean flag = false;
while (true) {
if (temp.next == null) {
break;
}
if (employee.id < temp.next.id) {
break;
} else if (employee.id == temp.id) {
flag = true;
break;
}
temp = temp.next;
}
if (!flag) {
employee.next = temp.next;
temp.next = employee;
} else {
System.out.println("id为" + employee.id + "的雇员已存在！");
}
}
/**
* 显示所有的信息
* @param no 第几个链表
*/
public void list(int no) {
if (head == null) {
System.out.println("第" + (no + 1) + "链表为空========");
return;
}
Employee temp = head;
System.out.print("第" + (no + 1) + "链表信息为：========");
while (true) {
System.out.print(" ==>id=" + temp.id + ",name = " + temp.name);
if (temp.next == null) {
break;
}
temp = temp.next;
}
System.out.println();
}
/**
*
* @param id 根据id查找
* @return 没用找到返回null
*/
public Employee findById(int id) {
if (head == null) {
System.out.println("链表为空");
return null;
}
Employee temp = head;
while (true) {
if (temp.id == id) {
break;
}
if (temp.next == null) {
temp = null;
break;
}
temp = temp.next;
}
return temp;
}
/**
*
* @param id 根据id删除员工
* @return 如果链表为空或者该员工不存在返回-1
*/
public int deleteById(int id) {
if (head == null) {
System.out.println("链表为空");
return -1;
}
if (head.id == id) {
head = head.next;
return id;
}
//标识是否找到
boolean flag = false;
Employee temp = head;
while (true) {
if (temp.next == null) {
break;
}
if (temp.next.id == id) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.next = temp.next.next;
return id;
} else {
return -1;
}
}
}
class HashTab {
private final EmpLinkedList[] empLinkedListArray;
private final int size;
public HashTab(int size) {
this.size = size;
empLinkedListArray = new EmpLinkedList[size];
//这里不能省略，否则数组里面的元素都是空的
for (int i = 0; i < size; i++) {
empLinkedListArray[i] = new EmpLinkedList();
}
}
/**
* 添加员工
* @param employee 添加的对象
*/
public void add(Employee employee) {
int index = hashFun(employee.id);
empLinkedListArray[index].add(employee);
}
/**
* @param id 根据id，写一个散列函数
* @return 该员工所在链表在数组中的索引
*/
public int hashFun(int id) {
return id % size;
}
/**
* 显示所有信息
*/
public void list() {
for (int i = 0; i < size; i++) {
empLinkedListArray[i].list(i);
}
}
/**
* @param id 根据id查找员工
*/
public void findById(int id) {
int index = hashFun(id);
Employee employee = empLinkedListArray[index].findById(id);
if (employee != null) {
System.out.println("在第" + (index + 1) + "条链表中找到雇员id = " + id + ",名字为：" + employee.name);
} else {
System.out.println("没用找到该雇员");
}
}
/**
* @param id 根据id删除员工
*/
public void deleteById(int id) {
int index = hashFun(id);
int result = empLinkedListArray[index].deleteById(id);
if (result != -1) {
System.out.println("删除成功");
} else {
System.out.println("链表为空或该雇员不存在");
}
}
}
测试
HashTab hashTab = new HashTab(7);
Scanner scanner = new Scanner(System.in);
String result;
while (true) {
System.out.println("add： 添加雇员");
System.out.println("list: 显示雇员");
System.out.println("find: 查找雇员");
System.out.println("delete：删除雇员");
System.out.println("exit: 退出系统");
result = scanner.next();
switch (result) {
case "add" :
System.out.println("请输入id");
int id = scanner.nextInt();
System.out.println("请输入名字");
String name = scanner.next();
Employee employee = new Employee(id,name);
hashTab.add(employee);
break;
case "list" :
hashTab.list();
break;
case "find" :
System.out.println("请输入要查找的id");
id = scanner.nextInt();
hashTab.findById(id);
break;
case "delete" :
System.out.println("请输入要删除的雇员的id");
id = scanner.nextInt();
hashTab.deleteById(id);
break;
case "exit" :
scanner.close();
System.out.println("系统退出成功=========");
System.exit(0);
break;
default:
System.out.println("输出错误！");
break;
}
}