summary
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.
Given table M, there is a function f(key). For any given keyword value key, after substituting into the function, if the address recorded in the table containing the keyword can be obtained, table M is called Hash table, and function f(key) is Hash function.
From Baidu Encyclopedia
In short, a hash table is a data structure, a nonlinear structure, and a table.
There is a hash function corresponding to it. Given a value of the hash function, the data corresponding to this value in the table can be quickly found through this function.
Therefore, in general, the meaning of hash table is to speed up the search speed and use it with hash function.
Generally, we implement the hash table by adding an array and a linked list (the specific structure is the same as the above figure). Define an array, and then create several linked lists. The number of linked lists created is equal to the capacity of the array. Then put the linked list in the array and the data to be stored in the linked list, so as to form a simple hash table.
Implement a hash table
To implement a hash table, you first need a linked list
Create a linked list
- Creating a linked list requires nodes. First, we create nodes
A simple employee class with next represents the node class - Nodes are objects and linked lists are objects, so you need to create a linked list class
This class is a linked list class. The linked list class has several properties and methods. Here we only realize its functions of adding, searching and traversal.
The linked list will be created successfully
Implementation table
The main body of the table is implemented in the above part of the code
First, an array of linked list type, and then an attribute representing the capacity of the array.
Then, the following is the constructor of the table, which receives a parameter for initializing the creation of the array and adding a linked list to the array. The hash table is now created.
But we need to use this data structure, so it has to have several basic methods. These methods must be based on the methods existing in the linked list, because from the bottom, we manipulate the data in the linked list.
Construction and use of a complete hash table
Hash function is very important in the use of hash table. It is its existence that can make our search faster
Hash function
A hash function is a function that maps the key value of an element in a hash table to the storage location of the element.
In general linear tables and trees, the relative positions of records in the structure are random, that is, there is no definite relationship with the record keywords. Therefore, a series of comparisons with keywords are required when searching records in the structure. This kind of search method is based on "comparison" "On the basis of, the efficiency of search depends on the number of comparisons made in the search process. Ideally, the required records can be found directly, so a definite corresponding relationship f must be established between the storage location of the record and its keywords, so that each keyword corresponds to a unique storage location in the structure.
From Baidu Encyclopedia
In short, hash function is a function that exists to facilitate the search or storage in the hash table. All functions that can improve the search speed of the hash table are called hash functions.
Here, we simply write a hash function, which takes the remainder of the array capacity according to the employee id number to write a hash function. See the following for details
We use the employee id to remainder the array capacity, and select the linked list in which the employee is placed according to the data obtained from the remainder. The data obtained from the remainder must be less than or equal to the maximum index of the array. When the data obtained is the same as an index, the employee is placed at the end of the linked list at the corresponding index position, so that some different employees can be placed in different places evenly In the linked list
The query of hash table is similar. First, get an index value by remainder, and then locate the linked list at the corresponding index position to traverse the linked list.
Here is a simple hash function
A complete hash table class should have some methods
We simply add some methods to the hash table according to the methods owned by the linked list:
test
First, simply set the array capacity to 6
no problem
All codes
import java.util.Scanner;
//Hashtable
//A data structure
public class Hashtable {
public static void main(String[] args) {
HashtableDemo hashtableDemo=new HashtableDemo(6);
Scanner scanner=new Scanner(System.in);
while (true) {
System.out.println("1,add to\n2,Exhibition\n3,lookup\n0,sign out");
String string=scanner.next();
if (string.equals("1")){
int n;
String name,N;
while (true){
System.out.print("input id");
N=scanner.next();
try {
n= Integer.parseInt(N);
System.out.print("Enter name");
name=scanner.next();
break;
}catch (Exception e){
System.out.println("Input error, please re-enter");
}
}
Employee employee=new Employee(n,name);
hashtableDemo.add(employee);
}else if (string.equals("2")){
hashtableDemo.list();
}else if (string.equals("3")){
int id;
String Id;
while (true){
System.out.print("input id");
Id=scanner.next();
try {
id= Integer.parseInt(Id);
try {
hashtableDemo.Select(id);
}catch (Exception e){
System.out.println(e);
}
break;
}catch (Exception e){
System.out.println("Input error, please re-enter");
}
}
}else if (string.equals("0")){
return;
}
}
}
}
class HashtableDemo{
private LinkdeList[] array;
private int size;
public HashtableDemo(int size) {//Initialize hash table
this.size=size;
array=new LinkdeList[size]; //Create array
for (int i = 0; i < size; i++) { //Initialize array
array[i]=new LinkdeList();
}
}
public void add(Employee employee){ //Add employee
array[Hashfun(employee.getId())].add(employee); //After the hash function is processed, the method of adding nodes to the linked list is called.
}
public void list(){ //Traversal hash table
for (int i = 0; i < size; i++) {
System.out.print("The first"+(i+1)+"that 's ok:");
array[i].list(); //Call the corresponding traversal method of the linked list for each linked list of the array
}
}
public int Hashfun(int id){
return id%size;
} //Hash function
public void Select(int id){
System.out.println(array[Hashfun(id)].get(id)); //After the hash function is processed, the search method of the linked list is called.
} //Search method
}
class Employee{ //Employee class, i.e. linked list node
private int id;
private String name;
public Employee next=null;
public int getId() {
return id;
}
public String getName() {
return name;
}
public Employee(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "Employee{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
}
class LinkdeList{ //A class that manages a linked list is a linked list class. Such an object represents a linked list
private Employee head; private Employee temp; private Employee end;
//There are three attributes. Head is the head node, temp is the auxiliary node, which is used to traverse the linked list, and end is used to record the tail of the linked list, which is used to add data later
public void add(Employee employee){ // Add node
if (head==null){
head=employee;
end=head;
}else {
end.next=employee;
end=end.next;
}
}
public void list(){// ergodic
temp=head;
if (head==null){
System.out.println("No data");
}
while (temp!=null){
System.out.println(temp);
temp=temp.next;
}
}
public Employee get(int id){// lookup
temp=head;
while (temp!=null){
if (temp.getId()==id){
return temp;
}
temp=temp.next;
}
throw new RuntimeException("not found");
}
}