Basic introduction of hash table
Hash table (also known as hash table) is a data structure that is accessed directly according to the key value. That is, to speed up the search by mapping it to a key in the table. This mapping function is called hash function, and the array storing records is called hash table.
(the bottom layer of hash table is array)
There are two ways to implement hash tables:
1. Array + linked list
2. Array + Red Black binary tree
Managing employee information using hash tables
Title: in a company, when a new employee comes to report, it is required to add the employee's information (id, name, gender, telephone). When entering the employee's id, it is required to find all the information of the employee
requirement:
Without a database, the faster the better
When adding, ensure to insert from low to high according to the id
Use the linked list to realize the hash table, which does not have a header
Train of thought analysis:
Add employee information
Create a node class to store employee information (id, name, sex, phone)
Create a fixed length array as a hash table, and each array element of the hash table stores a chain header node
Hash according to the employee ID to be added by the hash function (for example, the hash function is constructed by a simple modular method: H (k) = ID% size. If the id=1001 array length is 7, the remaining key is 0, and the corresponding array subscript is 0)
According to the key value after id hashing, link the employee node of the corresponding id to the back of the linked list under the corresponding array subscript
Find the employee information of the corresponding id:
Get the key value according to the id hash
Query in the linked list of the array subscript corresponding to the key value
Code implementation:
package HashCode;
import java.util.Scanner;
public class HashCode {
public static void main(String[] args) {
//Create a HashTab object
HashTab hashTab = new HashTab(7);
//Write a simple menu
int n;
Scanner scanner = new Scanner(System.in);
while(true) {
System.out.println("1: Add employee");
System.out.println("2: Show employees");
System.out.println("3: Find employees");
System.out.println("4: Exit the system");
n = scanner.nextInt();
switch (n) {
case 1:
System.out.println("input id");
int id = scanner.nextInt();
System.out.println("Enter name");
String name = scanner.next();
System.out.println("Enter gender");
String sex = scanner.next();
System.out.println("Enter phone");
String phone = scanner.next();
//Create employee
Emp emp = new Emp(id, name,sex,phone);
hashTab.addemp(emp);
break;
case 2:
hashTab.hashList();
break;
case 3:
System.out.println("Please enter the to find id");
id = scanner.nextInt();
hashTab.hashfind(id);
break;
case 4:
scanner.close();
System.exit(0);
default:
break;
}
}
}
}
//Add employee
class Emp{
public int id;
public String name;
public String sex;
public String phone;
public Emp next;
public Emp(int id,String name,String sex,String phone){
super();
this.id=id;
this.name=name;
this.phone=phone;
this.sex=sex;
}
}
//Create employee linked list and add employee information
class empLinkList{
public Emp head;//The header node is empty by default
//Add an employee to the linked list
public void add(Emp emp){
//If it's the first employee
if(head==null){
head=emp;
return;
}
//If it is not the first employee, add an auxiliary pointer to help locate to the end of the linked list
Emp curemp=head.next;//Auxiliary pointer
while(true){
//If it has reached the last position of the linked list, it will stop
if(curemp==null){
break;
}
//If the last position is not reached, the pointer continues to move back
curemp=curemp.next;
}
//When exiting, directly add em to the linked list
curemp=emp;
}
//Traverse linked list employee information
public void show(int no){
if(head==null){
System.out.println("The first" + (no+1) +"The linked list is empty");
return;
}
System.out.print("The first" + (no+1) +"The information of employees in the linked list is:");
Emp curemp=head;
while(true){
System.out.print("staff id:"+curemp.id+" Employee name:"+curemp.name);
if(curemp.next==null){
break;
}
curemp=curemp.next;
}
System.out.println();
}
//Find employee information by id
public Emp findempId(int id){
if(head==null){
System.out.printf("The linked list is empty");
return null;
}
//If the linked list is not empty, add an auxiliary pointer
Emp curemp=head;
while(true){
//If found, the search pointer points to curemp id
if(curemp.id==id){
break;
}
//If not found, the pointer continues to move back
curemp=curemp.next;
}
//Find the employee corresponding to the specified id and return the employee information
return curemp;
}
}
//Create HashTab to manage multiple linked lists
class HashTab{
//Define a hash array
private empLinkList[] empLinkListArray;
//Get array length
public int size;
public HashTab(int size){
super();
this.size=size;
empLinkListArray=new empLinkList[size];
for(int i=0;i<size;i++){
empLinkListArray[i]=new empLinkList();
}
}
//Write hash function and use simple modulo method
public int hashtab(int id){
return id%size;
}
//Add the corresponding employee to the linked list according to the employee id
public void addemp(Emp emp){
int empno=hashtab(emp.id);
empLinkListArray[empno].add(emp);
}
//Traverse employee linked list
public void hashList(){
for(int i=0;i<size;i++){
empLinkListArray[i].show(i);
}
}
//Find the employee based on the entered id
public void hashfind(int id){
int empno=hashtab(id);
Emp emp=empLinkListArray[empno].findempId(id);
if(emp==null){
System.out.printf("There is no information about this employee");
return;
}else{
System.out.printf("The employee information is:");
System.out.println("staff id: "+emp.id+" Gender:"+emp.sex+" full name:"+emp.name+" Telephone:"+emp.phone);
}
}
}
test
"C:\Program Files\Java\jdk1.8.0_191\bin\java.exe" "-javaagent:D:\IDEA\IntelliJ IDEA Community Edition 2020.2.3\lib\idea_rt.jar=63600:D:\IDEA\IntelliJ IDEA Community Edition 2020.2.3\bin" -Dfile.encoding=UTF-8 -classpath "C:\Program Files\Java\jdk1.8.0_191\jre\lib\charsets.jar;C:\Program Files\Java\jdk1.8.0_191\jre\lib\deploy.jar;C:\Program Files\Java\jdk1.8.0_191\jre\lib\ext\access-bridge-64.jar;C:\Program Files\Java\jdk1.8.0_191\jre\lib\ext\cldrdata.jar;C:\Program Files\Java\jdk1.8.0_191\jre\lib\ext\dnsns.jar;C:\Program Files\Java\jdk1.8.0_191\jre\lib\ext\jaccess.jar;C:\Program Files\Java\jdk1.8.0_191\jre\lib\ext\jfxrt.jar;C:\Program Files\Java\jdk1.8.0_191\jre\lib\ext\localedata.jar;C:\Program Files\Java\jdk1.8.0_191\jre\lib\ext\nashorn.jar;C:\Program Files\Java\jdk1.8.0_191\jre\lib\ext\sunec.jar;C:\Program Files\Java\jdk1.8.0_191\jre\lib\ext\sunjce_provider.jar;C:\Program Files\Java\jdk1.8.0_191\jre\lib\ext\sunmscapi.jar;C:\Program Files\Java\jdk1.8.0_191\jre\lib\ext\sunpkcs11.jar;C:\Program Files\Java\jdk1.8.0_191\jre\lib\ext\zipfs.jar;C:\Program Files\Java\jdk1.8.0_191\jre\lib\javaws.jar;C:\Program Files\Java\jdk1.8.0_191\jre\lib\jce.jar;C:\Program Files\Java\jdk1.8.0_191\jre\lib\jfr.jar;C:\Program Files\Java\jdk1.8.0_191\jre\lib\jfxswt.jar;C:\Program Files\Java\jdk1.8.0_191\jre\lib\jsse.jar;C:\Program Files\Java\jdk1.8.0_191\jre\lib\management-agent.jar;C:\Program Files\Java\jdk1.8.0_191\jre\lib\plugin.jar;C:\Program Files\Java\jdk1.8.0_191\jre\lib\resources.jar;C:\Program Files\Java\jdk1.8.0_191\jre\lib\rt.jar;D:\java-idea\out\production\java-idea" HashCode.HashCode 1: Add employee 2: Show employees 3: Find employees 4: Exit the system 1 input id 0 Enter name Li Yu Enter gender female Enter phone 17789560431 1: Add employee 2: Show employees 3: Find employees 4: Exit the system 1 input id 1 Enter name Zhang Huan Enter gender female Enter phone 17895567434 1: Add employee 2: Show employees 3: Find employees 4: Exit the system 1 input id 2 Enter name Jun Wang Enter gender male Enter phone 1789594327 1: Add employee 2: Show employees 3: Find employees 4: Exit the system 1 input id 3 Enter name Xiao Ling Enter gender female Enter phone 1909455792334 1: Add employee 2: Show employees 3: Find employees 4: Exit the system 1 input id 4 Enter name Dou Hao Enter gender male Enter phone 1894567321 1: Add employee 2: Show employees 3: Find employees 4: Exit the system 1 input id 5 Enter name Liu Yi Enter gender male Enter phone 1795454765738 1: Add employee 2: Show employees 3: Find employees 4: Exit the system 2 The information of the first linked list employee is: 0 Li Yu The information of employees in the second linked list is: 1 Zhang Huan The information of employees in the third linked list is: 2 Wang Jun The information of employees in the fourth linked list is: 3 Xiao Ling The information of employees in the 5th linked list is: 4 The information of employees in the 6th linked list is: 5 Liu Yi The 7th linked list is empty 1: Add employee 2: Show employees 3: Find employees 4: Exit the system 3 Please enter the to find id 4 The employee information is: employee id 4 Gender male name Dou Hao Tel 1894567321 1: Add employee 2: Show employees 3: Find employees 4: Exit the system 4 Process finished with exit code 0