A basic introduction to hash tables
A Hash table (also called a Hash table) is a data structure that is directly accessed based on Key values. That is, it accesses records by mapping key values to a location in the table to speed up lookups. This mapping function is called a hash function, and the array of records is called a hash table.
Hash table (hash)-Google computer problems
Take a look at a practical demand, a Google computer problem:
One company, when a new employee comes to report, requires that the employee’s information be added (ID, gender, age, address…). When the id of the employee is entered, all information about the employee is required to be found.
Requirements: No database, save as much memory as possible, as fast as possible => hash table (hash)
Thought analysis
- Hash tables are implemented using linked lists without headers [i.e., employee information is stored at the first node of the list]
- Code implementation [add, delete, change and check (display all employees, query by ID)]
code
package com.company;
import java.util.Scanner;
public class HashTabDemo {
public static void main(String[] args) {
// Create a hash table
HashTab hashTab = new HashTab(7);
// Write a simple menu
String key = "";
Scanner scanner = new Scanner(System.in);
while (true) {
System.out.println("Add: Add an employee");
System.out.println("List: display employees");
System.out.println("Find an employee.");
System.out.println("Delete: delete employee");
System.out.println("Exit: Exit the system");
key = scanner.next();
switch (key) {
case "add":
System.out.println("Enter the id");
int id = scanner.nextInt();
System.out.println("Enter your name");
String name = scanner.next();
// Create an employee
Emp emp = new Emp(id, name);
hashTab.add(emp);
break;
case "list":
hashTab.list();
break;
case "find":
System.out.println("Please enter the ID you are looking for.");
id = scanner.nextInt();
hashTab.findEmpById(id);
break;
case "delete":
System.out.println("Please enter the ID you want to delete");
id = scanner.nextInt();
hashTab.deleteEmpById(id);
break;
case "exit":
scanner.close();
System.exit(0);
default:
break; }}}}// Create a HashTab to manage multiple lists
class HashTab {
private EmpLinkedList[] empLinkedListArray;
private int size; // Indicates how many lists there are
/ / the constructor
public HashTab(int size) {
this.size = size;
// Initialize empLinkedListArray
empLinkedListArray = new EmpLinkedList[size];
/ /? Leave a pit and do not initialize each list separately
for (int i = 0; i < size; i++) {
empLinkedListArray[i] = newEmpLinkedList(); }}// Add an employee
public void add(Emp emp) {
// Get the list to which the employee should be added based on the employee id
int empLinkedListNO = hashFun(emp.id);
// Add the EMP to the corresponding list
empLinkedListArray[empLinkedListNO].add(emp);
}
// Iterate over all linked lists, iterate over hashtab
public void list(a) {
for (int i = 0; i < size; i++) { empLinkedListArray[i].list(i); }}// Find the employee based on the entered ID
public void findEmpById(int id) {
// Use the hash function to determine which list to look up
int empLinkedListNO = hashFun(id);
Emp emp = empLinkedListArray[empLinkedListNO].findEmpById(id);
if(emp ! =null) {/ / find
System.out.printf("Find employee ID = %d\n in list %d", (empLinkedListNO + 1), id);
} else {
System.out.println("The employee was not found in the hash table."); }}// Delete the employee based on the entered ID
public void deleteEmpById(int id) {
// Use the hash function to determine which list to delete
int empLinkedListNO = hashFun(id);
boolean flag = empLinkedListArray[empLinkedListNO].deleteEmpById(id);
if (flag) {/ / find
System.out.printf("Found employee ID = %d in list %d, deleted successfully \n", (empLinkedListNO + 1), id);
} else {
System.out.println("Employee not found in hash table, cannot delete ~"); }}// Write the hash function, using a simple modulo method
public int hashFun(int id) {
returnid % size; }}// Represents an employee
class Emp {
public int id;
public String name;
public Emp next; //next defaults to null
public Emp(int id, String name) {
super(a);this.id = id;
this.name = name; }}// Create an EmpLinkedList
class EmpLinkedList {
// The first Emp is executed, so the head of our list points directly to the first Emp
private Emp head; / / null by default
// Add employees to the linked list
/ / that
//1. Assume that when an employee is added, the ID is self-growing, that is, the id is always assigned from small to large
// So we add the employee directly to the end of the list
public void add(Emp emp) {
// Add the first employee
if (head == null) {
head = emp;
return;
}
// If it is not the first employee, an auxiliary pointer is used to help locate to the end
Emp curEmp = head;
while (true) {
if (curEmp.next == null) {// to the end of the list
break;
}
curEmp = curEmp.next; / / move backward
}
// Add emP directly to the list on exit
curEmp.next = emp;
}
// Iterate through the list of employees
public void list(int no) {
if (head == null) { // Indicates that the linked list is empty
System.out.println("The first" + (no + 1) + "Linked list is empty");
return;
}
System.out.print("The first" + (no + 1) + "The linked list information is");
Emp curEmp = head; // Auxiliary pointer
while (true) {
System.out.printf(" => id=%d name=%s\t", curEmp.id, curEmp.name);
if (curEmp.next == null) {// Indicates that curEmp is the last node
break;
}
curEmp = curEmp.next; // move back, traverse
}
System.out.println();
}
// Find employees by ID, return Emp if found, null if not
public Emp findEmpById(int id) {
// Check whether the list is empty
if (head == null) {
System.out.println("Linked list is empty");
return null;
}
// Auxiliary pointer
Emp curEmp = head;
while (true) {
if (curEmp.id == id) {/ / find
break;// curEmp points to the employee
}
/ / exit
if (curEmp.next == null) {The employee was not found by traversing the current linked list
curEmp = null;
break;
}
curEmp = curEmp.next;/ / after
}
return curEmp;
}
// According to delete employee, if delete successfully, 1, if not found, return 0
public boolean deleteEmpById(int id) {
boolean flag = false; // Indicates whether the node to be deleted is found
// Check whether the list is empty
if (head == null) {
System.out.println("Linked list is empty");
return flag;
}
// Auxiliary pointer
Emp curEmp = head;
while (true) {
if (curEmp.next == null) { // We are at the end of the list
break;
}
if (curEmp.next.id == id) {
// Temp is the previous node of the node to be deleted
curEmp.next = curEmp.next.next;
flag = true;
break;
}
curEmp = curEmp.next;
}
returnflag; }}Copy the code