Hash (hash)

One . Hash function （Hash function)

meaning ：

Put any length of input , Extract data summary , It is converted into fixed length output by hash algorithm .

characteristic ：

1. The hash values are different , Then the input content must be different .

2. The hash has the same value , The values entered are not necessarily the same （ There is hash collision ）.

3. The value of the hash is irreversible （ The original input cannot be derived from the hash value ）

Hash Algorithm ：

Hash The algorithm has no fixed formula , Any algorithm that conforms to the hash idea can be called Hash Algorithm .MD5 and SHA-1 It can be regarded as the most widely used Hash The algorithm .

MD5 It is widely used to verify data integrity , Such as ： After downloading the file , You can generate a copy of MD5 File and source file MD5 comparing , If it's the same , The document is considered complete , otherwise , It may be because the download is missing 、 The data has been modified, which leads to the inconsistency between the downloaded file and the source file .

PS： Little knowledge , Even if it's MD5 Hash collision also occurs , However, the probability is extremely low, and it is difficult to make the hash values consistent by modifying the data manually ~ So basically, it can be considered MD5 The verification is accurate . If extremely high accuracy is required , If you don't want any hash collision possible , The source file can be processed once MD5 Get hash value A, Then do another test on the source file SHA-1 Get hash value B, And then A and B Connect and do it again MD5, By combining MD5 and SHA-1 To get the verification result , It should be highly accurate ~

Two . Hashtable （Hash table）

Array ： Reading data is fast , The efficiency of adding and deleting data is very low .

Linked list ： The efficiency of adding and deleting data is very high , The speed of readable data is very slow .

Hashtable ： I think it's a combination of array and linked list , Reading and writing can have higher efficiency .

Workflow of hash table ：

1. The user enters a set of key value pairs {key, value} data .

2. Use hash Function on user input key To deal with F(key).

3. adopt F(key) The value in the corresponding storage location is directly obtained from the processing result of .PS： You don't need to traverse one by one , Get value directly .

4. If the value in the corresponding position is empty , Put it directly in value that will do .

Hash collision ：

The fourth step of the above workflow , Once there is a value in the corresponding position , And this value corresponds to key Not equal to the current user input key, Hash collision occurs . Because of different input sources （key） after Hash It is possible to generate the same hash value after function processing .

There are many ways to deal with hash collisions , Take it here hashmap As a solution （ I think his plan is very good ~）. When we save data, we can save data in the form of linked list , When a hash conflict occurs , Just traverse the linked list , See if there are any similarities key Of , Cover if you have , Just add this new set of data at the end of the linked list . Then in order to speed up the search , When the number of linked lists is greater than 8 Time , We can convert the linked list into a red black tree .

PS： Even if hash collision occurs , Ideally, it is still evenly distributed under each hash value , If some hash values collide too many times , Resulting in uneven distribution , At this time, the efficiency of hash table becomes low , Nor is it the result we want , Consider a different hash algorithm .