# [Data Structure and Algorithms] Hash Table

A Hash table is a data structure that is directly accessed based on a key value.
That is, it accesses records by mapping key code 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 list.

In the following figure, 16 arrays are defined, each of which holds a list of chains. When inserting data, the first step is to find out which list (array) the element is in by modularizing the number of arrays with its value, and then insert it as a list of chains

We have a computer question from google to learn the Hash table:

There is a company that asks for information about a new employee (id, gender, age, name, address...) When you enter the employee's id, you are asked to find all the information about the employee.

Requirement:

• Without a database, the faster the better=>hash table (hash)
• When adding, make sure to insert from low to high by id [Think: If id is not insert from low to high, but requires each chain list to be low to high, what can I do?]
• A hash table is implemented using a chain table without a header [that is, the first node of the chain table stores employee information]
• Ideas analyze and draw diagrams
• Code implementation [add/delete check (show all employees, query by id)]

code implementation

• Create a single element entity Emp in a chain table
• Create a linked list entity EmpLinkedList to store the above elements and add, delete, and change checking methods
Here, because the head er was not initialized at the beginning, you need to make a separate decision when deleting it
• Create HashTab, write hash function, and implement Hash table add-delete search method
```/**
* Hash table for data storage
*
* @author TimePause
* @create 2020-02-09 10:53
*/
public class HashDemo {

/**
* Employee class
*/
class Emp {
public int id;
public String name;
public Emp next;//next defaults to null

public Emp(int id, String name) {
this.id = id;
this.name = name;
}
}

/**
* Store employee information in a linked list
*/
class EmpLinkedList {
//Header pointer, executes the first Emp, so the head er of our list points directly to the first Emp
//***Default null, but if uninitialized here, null pointer exceptions will occur without initialization when deleting linked list nodes based on id***
//private Emp head=new Emp(0, ");//This initialization is OK, but the first element of each chain table is id=0,name=, which takes up extra space
private Emp head=null;

// Add Employee Method
public void add(Emp emp){
// If you add the first employee
if (head==null){
head = emp;
return;//Sign out
}
// If you are not adding the first employee, use a secondary pointer to help you navigate to the end
Emp curEmp = head;
while (true){
if (curEmp.next==null){//Instructions traversed to the end
break;//End the current cycle
}
//Otherwise move the pointer back
curEmp = curEmp.next;
}
// Add emp at the end of the list
curEmp.next = emp;
}

/**
* Delete node elements
* @param no
*/
public void del(int no){
//***If there is only one element in the list, simply emptying it is a deletion***
if (head!=null && head.next==null){
head = null;
return;
}else{
System.out.println("Chain list is empty,Cannot Delete");
}
//If normal. Delete node
Emp curEmp = head;
// Auxiliary variable flag, indicating whether the element being looked for exists
boolean flag = false;
while (true){
if (curEmp.next==null){//Indicates that the end of the chain has been reached
break;
}
if (curEmp.next.id==no){
flag = true;
break;
}
curEmp=curEmp.next;
}
if (flag){
curEmp.next = curEmp.next.next;
}else {
System.out.println("Node to delete does not exist");
}
}

//Traversing shows basic information about employees in a list of chains
public void list(int no){
if(head == null) { //Explanation chain list is empty
System.out.println("No. "+(no+1)+" Chain list is empty");
return;
}
System.out.print("No. "+(no+1)+" The information in the list is");
Emp curEmp = head; //Auxiliary Pointer
while(true) {
System.out.printf(" => id=%d name=%s\t", curEmp.id, curEmp.name);
if(curEmp.next == null) {//Explains that curEmp is already the last node
break;//Exit the current loop
}
curEmp = curEmp.next; //Move back, traverse
}
System.out.println();
}

// Finds employees based on id, returns Emp if found, and returns null if not found
public Emp findEmpById(int id){
// Determine if the list is empty
if (head==null){
System.out.println("Chain list is empty");
return null;
}
// If the list is not empty, look up the list
// First create an auxiliary variable
Emp curEmp = head;
while (true){
if (curEmp.id==id){
break;
}
//If not found at the end of the list, leave the current element empty and return
if (curEmp.next==null){
curEmp = null;
break;
}
curEmp = curEmp.next;//Move back
}
return curEmp;
}
}

/**
* Establish HashTab,Manage Multiple Chain Lists
*/
class HashTab{
private EmpLinkedList[] empLinkedListArray;//Store multiple chain lists
private int size;//Indicates how many chained lists there are

//constructor
public  HashTab(int size){
this.size = size;
// Initialize employee list array
this.empLinkedListArray = new EmpLinkedList[size];
// Do not forget to initialize each list!!!
for (int i = 0; i < size; i++) {
empLinkedListArray[i] = new EmpLinkedList();//size initializes several arrays as soon as possible
}
}

// Write hash functions for simple modulo
public int hashFun(int id){
return id % size;
}

//Add Employee
public void add(Emp emp){
// Based on employee id, query which chain the employee should add to
int empLinkedNo = hashFun(emp.id);
// Add emp to the corresponding list of chains
empLinkedListArray[empLinkedNo].add(emp);
}

/**
* Delete Employee
*/
public void del(int no){
int empLinkedNo = hashFun(no);
empLinkedListArray[empLinkedNo].del(no);

}

// Traverse through all linked lists, by traversing HashTab
public void list(){
for (int i = 0; i<size;i++) {
empLinkedListArray[i].list(i);
}
}

//Find employees based on the input id
public void findEmpById(int id) {
//Use hash function to determine which list to look for
int empLinkedListNO = hashFun(id);
// Query the data in that list based on id
Emp emp = empLinkedListArray[empLinkedListNO].findEmpById(id);
if(emp != null) {//find
System.out.printf("In%d Employees found in the chain list id = %d\n", (empLinkedListNO + 1), id);
}else{
System.out.println("The employee was not found in the hash table~");
}
}

}
```

When testing code, write an interface in the main() method to test

``` 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 Employee");
System.out.println("list: Show Employees");
System.out.println("find: Find Employees");
System.out.println("del: delete");
System.out.println("exit: Exit System");

key = scanner.next();
switch (key) {
case "add":
System.out.println("input id");
int id = scanner.nextInt();
System.out.println("Enter a 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 what you are looking for id");
id = scanner.nextInt();
hashTab.findEmpById(id);
break;
case "del":
System.out.println("Please enter the one you want to delete id");
id = scanner.nextInt();
hashTab.del(id);
break;
case "exit":
scanner.close();
System.exit(0);
default:
break;
}
}
}
}

```
186 original articles published. 880 praised. 230,000 visits+

Keywords: Google Database

Added by spamyboy on Mon, 02 Mar 2020 04:16:55 +0200