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

This article mainly introduces what is the use of hashing algorithm in java. It is very detailed and has a certain reference value. Friends who are interested must read it!

I. concept

A hash table is a structure that stores data by key-value (key-indexed). We only need to enter the value to be looked up, namely key, to find its corresponding value. The idea of hashing is simple: if all keys are integers, you can use a simple unordered array: use the key as an index, and the value is its corresponding value, so that you can quickly access the value of any key. This is the case for simple keys, which we extend to handle more complex types of keys.

There are two steps to using a hash lookup:

1. Use the hash function to convert the found key to the index of the array. Ideally, different keys would be converted to different index values, but in some cases we need to deal with situations where multiple keys are hashed to the same index value. So the second step in hashing lookups is to deal with conflicts.

two。 Handle hash collision conflicts. There are many ways to deal with hash collision conflicts, and zipper method and linear detection method will be introduced later in this article. A hash table is a classic example of a trade-off between time and space. If there is no memory limit, you can directly use the key as the index of the array. Then the complexity of all lookups is O (1); if there is no time limit, we can use unordered arrays and do sequential lookups, which requires very little memory. Hash tables use a moderate amount of time and space to strike a balance between these two extremes. You only need to adjust the hash function algorithm to make a choice in time and space.

In the Hash table, there is a definite relationship between the location of the record in the table and its keywords. In this way, we can know in advance the position of the keyword in the table and find the record directly through the subscript. Make ASL close to 0. 5%.

1) the Hash function is an image that maps a set of keywords to a set of addresses. Its setting is flexible, as long as the size of the set of addresses does not exceed the allowed range.

2) because the hash function is a compressed image, in general, it is easy to produce "conflict" phenomenon, that is, key1! = key2, and f (key1) = f (key2).

3) conflicts can only be minimized but not completely avoided, because the keyword set is usually large, its elements include all possible keywords, and the elements of the address set are only addresses in the hash table. When constructing this special "lookup table", in addition to choosing a "good" (as few conflicts as possible) hash function, you also need to find a way to "handle conflicts."

Second, the introduction of common hash algorithms:

1.MD4

MD4 (RFC 1320) is designed by Ronald L. Rivest of MIT in 1990, and MD is the abbreviation of Message Digest (message Summary). It is suitable for high-speed software implementation on 32-bit word-length processors-it is based on bit operations of 32-bit operands.

2.MD5

MD5 (RFC 1321) is an improved version of MD4 made by Rivest in 1991. It still groups the input in 512 bits, and its output is a cascade of four 32-bit words, the same as MD4. MD5 is more complex and slower than MD4, but safer, and performs better at anti-analysis and anti-differential.

3.SHA-1 and others

SHA1 is designed by NIST NSA to be used with DSA. It produces a hash of length 160bit for inputs with a length less than 264, so it is more resistant to exhaustion (brute-force). SHA-1 is designed based on the same principle as MD4 and imitates the algorithm.

Third, the principle of common hash algorithm

Hash table, which is designed from the point of view of fast access, is also a typical practice of "space for time". As the name implies, the data structure can be understood as a linear table, but the elements in it are not closely arranged, but there may be gaps.

A hash table (Hash table, also known as a hash table) is a data structure that is accessed directly based on key code values (Key value). That is, it accesses the record by mapping the key value to a location in the table to speed up the lookup. This mapping function is called a hash function, and the array in which records are stored is called a hash table.

For example, we store 70 elements, but we may have applied for 100 elements for these 70 elements. 70max 100mm 0.7, this number is called load factor. We do this for the purpose of "quick access". We arrange the storage location for each element based on a fixed function H whose results are randomly and evenly distributed as far as possible, so that the linear search of ergodic property can be avoided and fast access can be achieved. But because of this randomness, it will inevitably lead to a problem, that is, conflict. The so-called conflict means that two elements get the same address through the hash function H, so the two elements are called "synonyms". This is similar to 70 people going to a restaurant with 100 chairs for dinner. The hash function evaluates to a storage unit address, each of which is called a "bucket". If there are m buckets in a hash table, then the range of the hash function should be [05m MMI 1].

4. The application of Hash algorithm in information security is mainly reflected in the following three aspects:

1. Document check

The parity check and CRC check that we are familiar with do not have the ability to resist data tampering. To a certain extent, they can detect and correct channel errors in data transmission, but can not prevent malicious destruction of data.

The "digital fingerprint" characteristic of MD5 Hash algorithm makes it the most widely used file integrity checksum (Checksum) algorithm at present. Many Unix systems provide commands to calculate md5 checksum.

two。 Digital signature

Hash algorithm is also an important part of modern cryptographic system. Because the operation speed of asymmetric algorithm is slow, one-way hash function plays an important role in digital signature protocol. The digital signature of the Hash value, also known as the "digital abstract", can be considered statistically equivalent to the digital signature of the file itself. And such an agreement has other advantages.

3. Authentication protocol

Authentication protocol is also known as challenge-authentication mode: it is a simple and secure method when the transmission channel can be intercepted but cannot be tampered with.

The above is all the content of the article "what is the use of hashing algorithm in java". Thank you for reading! Hope to share the content to help you, more related knowledge, welcome to follow the industry information channel!

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.