1. Hash table (hash) - Google computer questions
- Let's take a look at the actual demand. A computer question from google:
- In a company, when a new employee comes to report, it is required to add the employee's information (id, gender, age, address...). When entering the employee's id, it is required to find all the information of the employee
- Requirements: do not use the database, save memory as much as possible, the faster the better = > hash table (hash)
2. Basic introduction to hash table
Hash table (also known as hash table) is a data structure that is accessed directly according to the key value. That is, it accesses records by mapping key values to a location in the table to speed up the search. This mapping function is called a hash function, and the array of records is called a hash table.
3. A computer problem of google
In a company, when a new employee comes to report, it is required to add the employee's information (id, gender, age, name, address...). When entering the employee's id, it is required to find all the information of the employee
requirement:
- Without database, the faster the better = > hash table (hash)
- When adding, ensure that the id is inserted from low to high [think after class: if the id is not inserted from low to high, but each linked list is still required to be inserted from low to high, how to solve it?]
- Use the linked list to implement the hash table. The linked list does not have a header [that is, the first node of the linked list stores employee information]
- Analyze the idea and draw a schematic diagram
- Code implementation [add, delete, modify and query (display all employees, query by id)]
Explanation of the diagram:
- There are many linked lists in the hash table. Use size to indicate how many linked lists are in the hash table
- Each linked list stores employee information, namely emp
- In Emp, there are only three properties
- Each operation is performed by the hash table on the EmpLinkedList, so you need to write the specific implementation method in the EmpLinkedList and write the method call in the hash table
Code implementation:
package com.zhao;
import java.util.Scanner;
/**
* @version v1.0
* @ProjectName: data structure
* @ClassName: HashTabDemo
* @Description: Hashtable
* @Author: Mr. Zhao
* @Date: 2021/12/21 9:47
*/
public class HashTabDemo {
public static void main(String[] args) {
//Create 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 employee");
System.out.println("list: Show employees");
System.out.println("find: Find employees");
System.out.println("exit: Exit the system");
key = scanner.next();
switch (key) {
case "add":
System.out.println("input id");
int id = scanner.nextInt();
System.out.println("Enter name");
String name = scanner.next();
//Create employee
Emp emp = new Emp(id, name);
hashTab.add(emp);
break;
case "list":
hashTab.list();
break;
case "find":
System.out.println("Please enter the to find id");
id = scanner.nextInt();
hashTab.findEmpById(id);
break;
case "exit":
scanner.close();
System.exit(0);
default:
break;
}
}
}
}
class HashTab {
private EmpLinkedList[] empLinkedListArray;
/**
* Indicates how many linked lists there are
*/
private int size;
/**
* constructor
* @param size How many of the linked list
*/
public HashTab(int size) {
this.size = size;
//Initialize empLinkedListArray
empLinkedListArray = new EmpLinkedList[size];
//？ Leave a hole. Don't initialize each linked list separately at this time
for(int i = 0; i < size; i++) {
empLinkedListArray[i] = new EmpLinkedList();
}
}
/**
* Add employee
* @param emp Employee information
*/
public void add(Emp emp) {
//According to the employee's id, get the linked list to which the employee should be added
int empLinkedListNO = hashFun(emp.id);
//Add emp to the corresponding linked list
empLinkedListArray[empLinkedListNO].add(emp);
}
/**
* Traverse all linked lists and hashtab
*/
public void list() {
for(int i = 0; i < size; i++) {
empLinkedListArray[i].list(i);
}
}
/**
* Write hash functions, using a simple modular method
* @param id emp id of
* @return
*/
public int hashFun(int id) {
return id % size;
}
/**
* Find the employee based on the entered id
* @param id User id
*/
public void findEmpById(int id) {
//Use the hash function to determine which linked list to look up
int empLinkedListNO = hashFun(id);
Emp emp = empLinkedListArray[empLinkedListNO].findEmpById(id);
if(emp != null) {//find
System.out.printf("In the first%d Employee found in linked list id = %d\n", (empLinkedListNO + 1), id);
}else{
System.out.println("The employee was not found in the hash table~");
}
}
}
/**
* Represents an employee
* id:Employee id
* name: Employee's name
* next: The next position is empty by default
*/
class Emp {
public int id;
public String name;
public Emp next;
public Emp(int id, String name) {
super();
this.id = id;
this.name = name;
}
}
/**
* Create an EmpLinkedList to represent a linked list
*/
class EmpLinkedList {
/**
* The header pointer executes the first Emp, so the head of our linked list directly points to the first Emp
* Default null
*/
private Emp head;
/**
* Add employee to linked list
* explain
* 1. Suppose that when an employee is added, the id is self increasing, that is, the id allocation is always from small to large
* Therefore, we can add the employee directly to the end of this linked list
* @param emp Added employee
*/
public void add(Emp emp) {
//If you are adding the first employee
if(head == null) {
head = emp;
return;
}
//If not the first employee, an auxiliary pointer is used to help locate the last employee
Emp curEmp = head;
while(true) {
if(curEmp.next == null) {
//Description to the end of the linked list
break;
}
//Move back
curEmp = curEmp.next;
}
//When exiting, add emp directly to the linked list
curEmp.next = emp;
}
/**
* Traversal linked list
* @param no Subscript of linked list
*/
public void list(int no) {
//The linked list is empty
if (head == null) {
System.out.println("The first "+(no+1)+" The linked list is empty");
return;
}
System.out.println("The first "+(no+1)+" The information of the linked list is");
Emp curEmp = head;
while(true) {
System.out.printf(" => id=%d name=%s\t", curEmp.id, curEmp.name);
//If the next position of the auxiliary pointer is empty, it means that it has come to the end
if (curEmp.next == null) {
break;
}
//Backward traversal
curEmp = curEmp.next;
}
System.out.println();
}
/**
* Find the employee based on the entered id
* @param id Employee id
* @return
*/
public Emp findEmpById(int id) {
//Determine whether the linked list is empty
if(head == null) {
System.out.println("The linked list is empty");
return null;
}
//Auxiliary pointer
Emp curEmp = head;
while(true) {
//find
if(curEmp.id == id) {
//At this point, curEmp points to the employee to be found
break;
}
//sign out
//Description: the employee cannot be found by traversing the current linked list
if(curEmp.next == null) {
curEmp = null;
break;
}
//in the future
curEmp = curEmp.next;
}
return curEmp;
}
}