One 、 Hashtable

Hash table is a kind of key corresponding value (key-indexed) Structure to store data , Just enter the key you want to find key, You can find the corresponding value .
Key as index , In this way, you can quickly access the value of any key .

1.1 hash function

Hash function is a function that maps the key value of an element in a hash table to its storage location .
The elements in the hash table are determined by the hash function . The key word of the data element K As an independent variable , Through certain functional relations （ It's called a hash function ）, The calculated value , That is, the storage address of the element .
A suitable hash function , You need to have the following two points

1. Homogeneity 　k The values of are evenly distributed in the hash table ;
2. Simple 　 To improve the speed of address calculation ;

1.2 Hash Collisions

Different values , The hash value calculated by the hash function may be the same

Suppose we will need to save the number n, Stored index value = n % 10
Now we need to 20 Save in this form , The calculated key value is 0, But the location already has data , That is, there is a hash conflict .

1.3 Resolve hash conflict

1.3.1 Open address method

Open addressing is when there is a conflict , Just look for the next empty hash address , As long as the hash table is large enough , Empty hash addresses can always be found , Then store the data in this location .

1.3.2 Chain address ( a key )

Treat the nodes of each hash table as the head of a linked list, the root node of a tree, or other data structures .
for example , Treat the node of the hash table as the head of a linked list . take 20 The hash table stored between .