Hash these knowledge you should also know

What is Hash

Hash is translated as hash in Chinese, and it is also called "hash". It is a general term for a class of functions.The input of any length (also known as pre-map, pre-image) is transformed into a fixed-length output through a hashing algorithm, and the output is the hash value.This transformation is a compressed map, that is, the space of the hash value is usually much smaller than the space of the input, and different inputs may hash to the same output, so it is impossible to determine the unique input value from the hash value.

Simply put, it is a function that compresses a message of any length into a message digest of a fixed length.

The role of Hash

hash is a function of compressing a message of any length into a message digest of a certain length.Equivalent to the fingerprint of a file.

Because the file is unlimited, the number of bits that can be represented by the mapped string is limited.Therefore, there may be different keys corresponding to the same Hash value.That's the possibility of a collision.

Hash storage data

The essence of the hash table is actually an array, and the key-value pair Entry is usually stored in the hash table.

The student number here is a key, and the hash table uses the hash function to calculate a value based on the key value. This value is the subscript value, which is used to determine where in the hash table the entry should be stored.

Hash collision solution

The solution to hash collision is open addressing method and zipper method.

Open addressing means that if the current array position 1 is occupied, it will be placed in the next position 2. If 2 is also occupied, it will continue to search until an empty position is found.

The zipper method uses a linked list. At this time, position 1 does not only store the Entry. At this time, the Entry also saves an additional next pointer, pointing to another position outside the array, and arranges Li Si in theHere, the next pointer in Zhang San's Entry points to Li Si's location, which is the stored memory address of this location.If there is still a conflict, put the conflicting Entry in a new position, and then Li Si's Entry points to it, thus forming a linked list.

Open addressing and zipping both try to find the next empty location to store the conflicting value.

Practical uses of Hash

Unique verification

• In java, it is used to judge whether the variables are equal and put into hashCode(), and together generate an integer that will not collide as much as possible

Data integrity verification:

• After downloading a file from the Internet, you can confirm whether the downloaded file is damaged by comparing the Hash value (such as MD5, SHA1) of the file.If the Hash value of the downloaded file is consistent with the Hash value given by the file provider, it proves that the downloaded file is intact

Quick Find:

• HashMap

Privacy Protection:

• When important data must be exposed, someone can choose to expose its Hash value (such as MD5) to ensure the security of the original data.For example, when logging in to a website, you can only save the hash value of the user's password. In each login verification, you only need to compare the hash value of the entered password with the hash value saved in the database. The website does not need to knowUser's password.In this way, when the website data is stolen, the user will not endanger the security of other websites because of the theft of their own password.

Author: Arrom
Link: https://juejin.cn/post/7127862424887099406
Source: Rare Earth Nuggets