[hash table basics]

What is a hash table

Hashtable （Hash table, Also called a hash table ）, According to the key code value (Key value) Data structures that are accessed directly . in other words , It accesses records by mapping key values to a location in a table , To speed up the search . This mapping function is called the hash function , The array that holds the records is called a hash table .

The official explanation may be a little confused , Frankly speaking, an array is actually a hash table .

Hash is a very common lookup data structure , It can be O(1) Data search under the time complexity of .
For example, I have a set with the following data , And I want to quickly find out if a data is in this set , What should I do ？

In general, you can use traversal , But if there is too much data , Then the cost of each traversal will be unacceptable .

that , If they are ordered , You can use the tree data structure for binary search , The efficiency is also very high , But unfortunately, our data are out of order .

So someone thought of a very clever way to find it , Is the data to be found （ Hereinafter referred to as key ） Perform a calculation to get an array subscript value , Then put this value into the corresponding array .

In the future, we will calculate the key every time we look for it to get an array subscript value , Then get the data corresponding to the array through the subscript , You can know if it exists in this array .

The data structure of this data lookup is called hash table , The method of calculating the key is called the hash function .

What is a hash function

Hash function can convert the given data into irregular values of fixed length . The converted irregular values can be used as data summary in various scenarios .

We can think of hash function as a blender , As shown in the figure below .

Put the data into the blender

After hash function calculation , The mixer outputs irregular values of fixed length . The irregular value output is “ Hash value ”. Although the hash value is a number , But it is often expressed in hexadecimal .

The computer uses binary to manage all data , Although the hash value is expressed in hexadecimal , But it's also data , The computer is storing hash values , It will be converted into binary by calculation for management .

Characteristics of hash function

1. The length of the hash value is independent of the size of the input data
2. Enter the same data , The output hash value must also be the same
3. Enter similar data , The output hash value must be different
4. The input data is completely different , But the output hash value may be the same . This situation is called “ Hash Collisions ”
5. Hash value is irreversible , It is impossible to deduce the original data from the hash value .

Hash Collisions

Hash conflict means that multiple different keys are hashed to the same array subscript position , The case is as follows ：

In the diagram above , ear 、 Duo 、 No The array subscripts of these three words after hashing are 0, And because it's three different values , Therefore, you can't directly overwrite... On the array , Then we need a way to save these three values .

Generally, there are two ways to solve hash conflicts , Zipper method and open address method .

Zipper method ： Is to maintain a linked list at the conflicting subscript elements , All conflicting elements are put on the linked list in turn ：

In the diagram above , Put the conflicting two keys in the linked list in order , The next time you search, you only need to view the array elements and traverse the linked list .
In fact, zipper method is to choose the appropriate size of hash table , This will not waste a lot of memory because the array is empty , It won't waste too much time searching because the list is too long .

Open address method ： It is a relatively simple method to solve conflicts , Its principle is very simple ：

It's in the first ear The word has taken up the subscript 0 after , the second Duo The word goes back to find the free subscript , After finding it, set yourself in , therefore Duo The word is subscript 1 It's about , and No The word is subscript 2 It's about .

Depending on how you look for subscripts , The open address method can be divided into the following ：

In fact, the principles are almost the same , All search for spare subscripts based on the current subscript , But the steps are different .

Three common hash structures

1. Array （array)
2. aggregate （set）
3. mapping （map）
   stay C++ in ,set and map The following three data structures are provided respectively , Its underlying implementation and advantages and disadvantages are shown in the table below ：
   
   

The disadvantages of hash tables

1. Too many hash conflicts can lead to partial lookups .
2. Can't do range lookup .

For the first disadvantage , Generally, there will not be too many conflicts in normal use

For the second disadvantage , This is an unavoidable hard injury to the hash table , Under the need to find the scope , Or tree data structure can better take into account range search and exponential speed .

Of course, when the hash table records a large amount of data , Processing recorded data is fast , The average operating time is a small constant . This is enough to cover up many shortcomings .