哈希表
文章目录
- 哈希表
- 1. 问题引出
- 2. 基本介绍
- 3. 应用实例
1. 问题引出
看一个实际需求，google公司的一个上机题:有一个公司，当有新的员工来报道时，要求将该员工的信息加入(id,性别，年龄等)，当输入该员工的id时，要求查到该员工的所有信息。要求： 不使用数据库，尽量节省内存，速度越快越好=>哈希表(散列)。
2. 基本介绍
散列表 (Hash table，也叫哈希表)，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数据叫做散列表。
3. 应用实例
题目:有一个公司，当有新元哦概念股来报道时，就将该员工的信息加入(id,name)，当输入该员工的id时，要求找到该员工的所有信息
要求：不使用数据库，速度越快越好 => 哈希表
代码如下[包含 增 删 查]
class HashTab { //哈希表
//定义大小为size的EmpLinkedList数组
private int size;
private EmpLinkedList[] empLinkedLists;
public HashTab(int size) {
this.size = size;
//设置大小
empLinkedLists = new EmpLinkedList[size];
//但是注意！！！
//数组大小虽然决定了 但是数组里的元素默认初始化为null
//即每个EmpLinkedList = null;
//需要初始化
for (int i = 0; i < size; i++) {
empLinkedLists[i] = new EmpLinkedList();//初始化每个元素链表
}
}
public void findEmpById(int no) { //通过Id找对象
//empLinkedLists[hashFun(no)] 找到对应的链表
//.find(no) 在对应的链表中找相应的节点
empLinkedLists[hashFun(no)].find(no);
}
public void delete(int no){ //根据编号删除对应元素
//empLinkedLists[hashFun(emp.getId())] 找到对应的链表
//.delete在对应的链表中删除节点
empLinkedLists[hashFun(no)].delete(no);
}
public void add(Emp emp) { //添加元素到哈希表中
//empLinkedLists[hashFun(emp.getId())] 找到对应的链表
//.add添加对象到对应的链表中
empLinkedLists[hashFun(emp.getId())].add(emp);
}
public void list() { //显示哈希表中的数据
for (int i = 0; i < size; i++) {
empLinkedLists[i].list(i); //依次显示每一条链表的数据
}
}
public int hashFun(int no) { //散列函数 用来决定数据放哪一个链表
return no % size; //返回编号对size的取模
}
}
class EmpLinkedList { //定义Emp链表
private Emp head = null; //定义头节点
public void add(Emp emp) { //添加新员工 直接添加到最后一个位置
if (head == null) { //如果头节点是空的
head = emp; //直接把头节点指向次员工
return;
}
Emp temp = head;
while (temp.getNext() != null) {//遍历到最后一个节点退出循环
temp = temp.getNext(); //继续下一个节点
}
//退出循环后 此节点指向最后一个节点
temp.setNext(emp); //将最后一个节点next指向新的节点
}
public void delete(int no) { //根据no号删除对应的节点
if (head == null) {
System.out.println("此处无垠三变量");
return;
} else if (head.getId() == no) { //如果头节点就是要删除的对象
head = head.getNext(); //则直接头节点后移就行了
return;
}
Emp temp = head;
while (temp.getNext() != null) {
if (temp.getNext().getId() == no) { //如果下一个节点是删除的节点
temp.setNext(temp.getNext().getNext()); //将temp的next指向后面第二位
break;
}
temp = temp.getNext(); //否则后移 继续判断下一位
}
}
public void find(int no) { //查找对应no是否存在
if (head == null) {
System.out.println("目标不存在");
return;
}
Emp temp = head;
while (temp != null) {//遍历每一个节点
if (temp.getId() == no) { //说明找到了对应的目标
System.out.println(temp); //输出对应的信息
return;
}
temp = temp.getNext(); //继续下一个节点
}
//正常退出循环后 说明目标不存在
System.out.println("目标不存在");
}
public void list(int no) { //显示链表
if (head == null) { //说明为空
System.out.println("第" + (no + 1) + "条链表为空");
return;
}
Emp temp = head;
System.out.print("第" + (no + 1) + "条链表:");
while (temp != null) {//遍历每一个节点
System.out.print(temp + " ");
temp = temp.getNext(); //继续下一个节点
}
System.out.println();
}
}
class Emp { //定义Emp节点
private int Id; //编号
private String name; //名字
private Emp next; //指向下一个节点 默认为null
public Emp(int id, String name) { //构造器
Id = id;
this.name = name;
}
public Emp getNext() {
return next;
}
public void setNext(Emp next) {
this.next = next;
}
public int getId() {
return Id;
}
public void setId(int id) {
Id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
return "{" +
"Id=" + Id +
", name='" + name + '\'' +
", next=" + (next == null ? null : next.hashCode()) +
'}';
}
}
其实整个代码不难理解，就是在链表的基础上，创建了多个链表进行管理。看韩老师敲一遍代码，自己就能敲出来了。
![[Verilog] Verilog 操作符与表达式](https://img-blog.csdnimg.cn/direct/590491ae4b2d4883958f95287ca8dd1f.png)
