Shulou(Shulou.com)06/01 Report--

This article mainly explains "how to use the Hash algorithm". The content in the article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn how to use the Hash algorithm.

Overview

   Hash, generally translated as "hash", is also transliterated as "hash", that is, the input of any length (also known as pre-mapping, pre-image) is transformed into a fixed-length output by hashing algorithm, which is the hash value. This transformation is a compressed mapping, that is, the space of the hash value is usually much smaller than that of the input, and different inputs may be hashed into the same output, and it is not possible to uniquely determine the input value from the hash value. To put it simply, it is a function that compresses a message of any length into a message digest of a fixed length.

   Hash is mainly used for encryption algorithms in the field of information security. It converts messages of different lengths into messy 128bit codes, which are called hash values. It can also be said that hash is to find a mapping relationship between data content and data storage address.

Basic concept

   if there is a record equal to the keyword K in the structure, it must be in the storage location of f (K). As a result, the checked records can be obtained directly without comparison. The corresponding relation f is called hash function (Hash function), and the table established according to this idea is called hash table.

   may get the same hash address for different keywords, that is, key1 ≠ key2, and f (key1) = f (key2), this phenomenon is called conflict. Keywords with the same function value are synonymous with the hash function. To sum up, according to the hash function H (key) and the method of dealing with conflicts, a set of keywords is mapped to a finite continuous address set (interval), and the "image" of the keywords in the address set is taken as the storage location in the table. This kind of table is called hash table. This mapping process is called hash table or hash, and the resulting storage location is called hash address.

   if for any keyword in the keyword set, the probability of mapping to any address in the address set by the hash function is equal, then this kind of hash function is called the uniform hash function (Uniform Hash function), which makes the keyword get a "random address" through the hash function, thus reducing the conflict.

The Construction method of Hash function

The principle for    to construct a hash function is that the ① function itself is easy to calculate, and the address calculated by ② is evenly distributed, that is, the probability corresponding to different addresses for any keyword KLF (k) is equal, in order to reduce conflicts as much as possible.

   the following describes five common methods for constructing hash functions.

1. Direct addressing method

   takes a keyword or a linear function value of a key as a hash address. That is, H (key) = key or H (key) = a*key+b, where an and b are constants (this hash function is called its own function).

two。 Digital analysis method

If    knows the keyword set in advance and the number of bits of each keyword is more than that of the address code of the hash table, it can select several bits with more uniform distribution from the keywords to form a hash address. For example, there are 80 records with the keyword 8-bit decimal integer d1d2d3... D7d8. If the hash table is 100 in length, the address space of the hash table is: 0099. Assuming that after analysis, the values of d4 and d7 in each keyword are evenly distributed, the hash function is h (key) = h (d1d2d3 … D7d8) = d4d7. For example, h (81346532) = 43 # h (81301367) = 06. On the contrary, suppose that after analysis, the values of D1 and D8 in each keyword are extremely uneven, D1 is equal to 5 and D8 is equal to 2, in this case, if the hash function is: h (key) = h (d1d2d3 … D7d8) = d1d8, then the address code of all keywords is 52, which is obviously not desirable.

3. Square centering method

When it is impossible to determine which bits in the keyword are evenly distributed, you can first find the square value of the keyword, and then take the middle bits of the square value as the hash address as needed. This is because: the middle bits after the square are related to each bit in the keyword, so different keywords will produce different hash addresses with a higher probability.

4. piecewise superposition method

   divides the keyword into equal parts according to the number of bits in the hash table (the last part can be shorter), then adds these parts, and the result is the hash address of the keyword when the highest carry is discarded. The specific methods are folding method and displacement method. The shift method is to add the low alignment of each part after segmentation, and the folding method is to fold back and forth along the partition boundary from one end to the other (odd segments are positive order, even segments are inverse order), and then add each segment. For example: key=12360324711202065, if the hash table length is 1000, the keyword should be divided into 3-bit segments, the lowest two digits 65 should be removed here, and the shift stack and fold stack should be performed respectively, and the hash address should be 105 and 907.

5. The method of division and residue

   assumes that the length of the hash table is m, p is the largest prime less than or equal to m, then the hash function is h (k) = k% p, where% is the remainder operation of modulo p.

6. Pseudo-random number method

   uses a pseudorandom function as a hash function, that is, h (key) = random (key).

Ways to deal with conflicts

   can reduce conflicts by constructing hash functions with good performance, but it is generally impossible to avoid conflicts completely, so conflict resolution is another key problem of hash method. There are conflicts between creating a hash table and looking up a hash table, and the way to resolve the conflict should be the same in both cases. Let's take the creation of a hash table as an example to illustrate how to resolve conflicts. There are four common ways to resolve conflicts:

1. Open addressing method

   method is also called rehashing method. Its basic idea is: when the hash address of the keyword key is conflicted, another hash address p1 is generated based on p, and then another hash address p2, based on p, is generated based on p. Until a non-conflicting hash address pi is found and the corresponding element is stored in it This method has a general form of rehash function:

   Hi= (H (key) + di)% Miya1 Magi 2, … , n

   where H (key) is a hash function, m is a table length, and di is called an incremental sequence. If the value of the incremental sequence is different, the corresponding re-hashing is also different. There are three main types:

Linear detection rehash

   dii=1,2,3, … , mmur1

The characteristic of    is that when a conflict occurs, the next cell in the table is checked sequentially until an empty unit is found or the whole table is searched.

Secondary detection and rehashing

Di= 1 ^ 2,-1 ^ 2, 2 ^ 2,-2 ^ 2, … , k ^ 2,-k ^ 2 (k

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.