一、哈希表(散列)
1. 问题引入
2. 解决办法
哈希表实现方法有: 1)数组+链表 2)数组+二叉树
底层实现:
解释: 有一个R=[15*N]的数组, 当要找某条数据的时候, 用该数值m%15解释ji解释 ,到第X行
3. 代码实现
逻辑分析:
1. 创建emp员工类
1. 创建empLinkedList, 把具有相似属性的员工组成一个list
1. 创建hash表,将每个empLinkedList的首节点串起来,组成一个array. 管理多条链表
step1: 创建员工表
// 雇员类
class Emp {
public int id;
public String name;
public Emp next; // next默认为空
public Emp(int id, String name) {
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Emp getNext() {
return next;
}
public void setNext(Emp next) {
this.next = next;
}
}
step2: 创建员工list表,将具有某些属性的员工放入同一个list中。 根据模来决定
// EmpLinkedList, 创建hashtable的元素类
class EmpLinkedList {
// 该类中有头节点信息
private Emp head = null;
// 添加雇员
// 链表从前往后添加,默认自增长
public void add(Emp emp) {
// 如果是第一个雇员
if (head == null) {
head = emp;
return;
}
// 如果不是第一个雇员,则需要一个辅助指针指向最后
Emp currentEmp = head;
while (true) {
if (currentEmp.getNext() == null) {
// 说明已经到了最后一个节点
currentEmp.setNext(emp);
break;
} else {
currentEmp = currentEmp.getNext();
}
}
}
// 遍历链表
public void list(int no) {
if (head == null) {
System.out.println("第" + (no + 1) + "条链表为空!");
return;
}
Emp currentEmp = head;
while (true) {
System.out.println("第" + (no + 1) + "条链表信息是:");
System.out.printf("=>id=%d name=%s \t", currentEmp.getId(), currentEmp.getName());
if (currentEmp.getNext() == null) {
break;
} else {
currentEmp = currentEmp.getNext();
}
}
}
// 根据id查找雇员
public Emp findEmpById(int id) {
// 如果找到了,就返回雇员信息,如果没有找到,就返回-1
if (head == null) {
// 当前链表为空
System.out.println("当前链表为空!");
return null;
}
// 辅助指针
Emp temp = head;
while (true) {
if (temp.getId() == id) {
break;
}
//退出
if (temp.getNext() == null) {
// 到了最后一个节点了
System.out.println("目标雇员不存在!");
temp = null;
break;
}
temp = temp.getNext();
}
return temp;
}
}
step3: 创建一个数组,保存所有list的首节点
// hash表,管理多条链表
class HashTableArray {
private int size; // 表示共有多少条数据
private EmpLinkedList[] empLinkedListsArray; // 数组的形似,可以用数组的下标对其赋值
public HashTableArray(int size) {
// 初始化array的规模
this.size = size;
empLinkedListsArray = new EmpLinkedList[size];
// 不要忘记,当前只是有了HashTableArray, 但是其元素为空,所有要初始化其元素(即创建员工list表)
for (int i = 0; i < size; i++) {
empLinkedListsArray[i] = new EmpLinkedList();
}
}
// 添加雇员信息
public void add(Emp emp) {
// 根据员工id来判断应该添加到哪条链表中
int empLinkedListNo = hashFun(emp.getId());
// 将emp加入到该条链表中
// 下标对应的数组
empLinkedListsArray[empLinkedListNo].add(emp); // EmpLinkedList节点信息组成的数组,EmpLinkedList本身就是链表有add()
}
// 编写一个散列函数,取膜法
public int hashFun(int id) {
return id % size;
}
// 遍历所有的链表
public void list() {
// 遍历所有的hashTable
for (int i = 0; i < size; i++) {
empLinkedListsArray[i].list(i);
}
}
// 根据输入的id查找雇员
public Emp findEmpById(int id) {
// 首先仍然根据散列来定位到具体某条链表
int empLinkedListNo = hashFun(id);
// 下标对应的数组
Emp temp = empLinkedListsArray[empLinkedListNo].findEmpById(id);
if (temp == null) {
System.out.println("要查找的员工不存在!");
}
return temp;
}
}
step4: 创建键盘交互
HashTableArray arr = new HashTableArray(20);
// 写一个菜单,让用户通过键盘输入值进行交互
String key = " ";
Scanner newScan = new Scanner(System.in);
while (true) {
System.out.println("Add:添加雇员!");
System.out.println("List:打印列表!");
System.out.println("Find:查找雇员!");
System.out.println("Exit:退出系统!");
key = newScan.next();
switch (key) {
case "Add":
System.out.println("请输入id!");
int id = newScan.nextInt();
System.out.println("请输入名字!");
String name = newScan.next();
// 根据输入的信息创建员工
Emp emp = new Emp(id, name);
arr.add(emp);
break;
case "List":
System.out.println("打印出所有员工信息:\n");
arr.list();
break;
case "Find":
System.out.println("请输入要查找的员工编号:");
int findId = newScan.nextInt();
arr.findEmpById(findId);
break;
case "Exit":
newScan.close();
System.exit(0);
default:
break;
}
}