Starting from the hash function, this article tells you exactly what hash ideas and hash table construction are.

Author: Code [K]

Source: CSDN Blog

Editor's Note: The original title was "Listing from Hash Functions, Hash Conflicts, and Open Dispersions. This article tells you exactly what hash ideas and hash table structures are."

Hash, generally translated as hash, hash, or transliteration to hash, is to transform an input of any length (also known as a pre-image) into a fixed-length output through a hash algorithm, and the output is the hash value.

• Valuing BTC through production costs, which will exceed $ 13,000 when halved
• Anti-epidemic survey report of the blockchain industry: What is the impact? What are the new opportunities?
• Bitcoin has fallen by 16% in two days, and the myth of hedging has been shattered?

Today we will explore together the mystery of the lowest level of hashing.

Hashing concept

A storage structure is constructed, and a certain function is used to establish a one-to-one mapping relationship between the storage position of its elements and his key code, and then the corresponding element is quickly found through this function when searching.

In short, it is to set a fixed function (hashFunc), and use this function to make the value of the inserted element correspond to the position of the element. When we need to find this element, we can find the value through this function (hashFunc).

Hash function

Hash function (English: Hash function), also known as hash algorithm, hash function, is a method to create a small digital "fingerprint" from any kind of data. The hash function compresses the message or data into a digest, making the amount of data smaller and fixing the format of the data.

This function scrambles the data and recreates a fingerprint called hash values (hash codes, hash sums, or hashes). The hash value is usually represented by a short string of random letters and numbers.

The hash function makes the calculated addresses evenly distributed throughout the space.

Insert and search elements

According to the key code of the element to be inserted, its storage location is calculated according to the hash function.

We use the hash function of the remainder division method to introduce: Example: The existing numbers of 1, 3, 4, 5, 6, and 9 are stored, and the result of the modulo operation of n% 10 is used as the hash address for element insertion. .

If you want to find an element, you only need to perform a hash function operation on the search element to get its storage address, and you can find the element.

Hash collision

When an element is inserted, the address calculated by the hash function is already occupied by other elements, which is called a hash collision.

Such as:

In order to better identify whether the current position is occupied, we need to mark each position

  enum state {EMPTY, FULL, DELETE}; 

Note: If we want to delete an element, we cannot delete it directly. If we delete directly, it will affect the current structure and cause the search of other elements to be wrong. So when we want to delete an element, we need to mark it as deleted. , Not empty.

Open hash

Open hashing is also called the chain address method . First, a hash function is used to calculate the hash address for a set of key codes. When there are key codes with the same address, all elements of the same address are linked by a single linked list. The head node is stored in the hash table.

Now, you should understand the idea of ​​hash and the structure of hash table, right? Welcome to share your thoughts with us in the comment area!

We will continue to update Blocking; if you have any questions or suggestions, please contact us!