您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

哈希表(图文)

第十三双眼睛2023-10-18【数据结构与算法】人已围观

简介哈希表

哈希表
散列表也叫哈希表，是根据关键码值而进行直接访问得数据结构，也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找得速度，这个映射函数叫左散列函数，存放记录得表叫做散列表。

package com.xingchen.day008;
import java.util.Scanner;
public class HashTableDemo {
public static void main(String[] args) {
HashTable hashTable = new HashTable(8);
String key = "";
Scanner scanner = new Scanner(System.in);
while (true) {
System.out.println("add:添加雇员");
System.out.println("list:显示雇员");
System.out.println("find:查找雇员");
System.out.println("exit:退出系统");
key = scanner.next();
switch (key) {
case "add" :
System.out.println("输入id");
int id = scanner.nextInt();
System.out.println("请输入名字");
String name = scanner.next();
Emp emp = new Emp(id, name);
hashTable.add(emp);
break;
case "list":
hashTable.list();
break;
case "find":
System.out.println("请输入id");
id = scanner.nextInt();
hashTable.findById(id);
break;
case "exit":
scanner.close();
System.exit(0);
break;
default:
break;
}

}
}
}
class Emp {
public int id;
public String name;
public Emp next;
public Emp(int id,String name) {
this.id= id;
this.name = name;
}
}
class HashTable {
private int size;
private EmpLinkList[] empLinkListArray;
public HashTable(int size) {
this.size = size;
this.empLinkListArray = new EmpLinkList[size];
for (int i = 0; i<size; i++) {
empLinkListArray[i] = new EmpLinkList();
}
}
public void add(Emp emp) {
//先根据员工的id,得到该员工应该被添加到哪条链表
int hashCode = hashFun(emp.id);
empLinkListArray[hashCode].add(emp);
}
//散列函数,使用最简单的取模法
public int hashFun(int id) {
return id % size;
}
public void list() {
for (int i = 0; i<size; i++) {
empLinkListArray[i].list();
}
}
public void findById(int id) {
int hashCode = hashFun(id);
Emp emp = empLinkListArray[hashCode].findById(id);
if (emp == null) {
System.out.println("没有找到");
return;
}
System.out.println(emp);
}
}
class EmpLinkList {
private Emp head;
// 添加雇员,假设id自增
public void add (Emp emp) {
if (head == null) {
head = emp;
return;
}
//如果不是第一个雇员，则使用一个辅助指针
Emp current = head;
while (true) {
if (current.next == null) {
break;
}else {
current = current.next;
}
}
//退出时，肯定找到了链表最后
current.next = emp;
}
//遍历链表
public void list () {
if (head == null) {
System.out.println("链表为空");
return;
}
Emp current = head;
while (true) {
System.out.println(current);
if (current.next == null) {
break;
} else {
current = current.next;
}
}
}
public Emp findById (int id) {
if (head == null) {
System.out.println("链表空");
return null;
}
Emp current = head;
while (true) {
if (current.id == id) {
break;
}
if (current.next == null) {
current = null;
break;
}
current = current.next;
}
return current;
}
}

Tags：

很赞哦！ ()

上一篇：斐波拉契（黄金分割）查找算法(图文)

下一篇：二叉树(图文)