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

This article mainly explains "what is the hash in Python data structure and algorithm". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let the editor take you to learn "what is the hash in the Python data structure and algorithm"?

Hash (Hash)

For a set of data items, the time complexity of sequential search is O (n), and that of binary search is O (logn). For hash data structures, the time complexity of search algorithm is reduced to O (1).

Hash table (hash table)

Hash table, also known as "hash table", is a kind of data set, in which the storage of data items is conducive to fast search operations.

In the hash table, each storage location used to store data items is added as "slot", and each slot corresponds to a unique name.

The corresponding data structure in python is the dictionary.

{'averse: 1,' baked: 2, 'catered: 3}

Hash function (hash function)

Hash function: conversion from data item to slot name

A common hash function is "finding the remainder": divide the data item by the size of the hash table, and the remainder is used as the slot name.

Why is it more common to find the remainder? Because the slot number returned by the hash function must be within the range of the hash table, the hash table size is usually offset.

When the data items are saved to the hash table, the search can be queried directly through the slot number, and the time complexity of the algorithm is O (1).

Conflict (collision)

When calculating slots in hash functions, different data items should calculate different slots, but sometimes different data items calculate the same slots (that is, conflicts).

For example: size 11 hash table, hash function "remainder", 77 and 44 calculate the slot is 0! There was a conflict.

For hash tables, the main topic of discussion is conflict resolution

Perfect hash function

Perfect hash function: given a set of data items, the perfect hash function can map each data item to a different slot

For a fixed set of data, we can always find a way to design a nearly perfect hash function.

The characteristics of a good hash function:

Fewer conflicts (different slots for each data item)

The calculation is less difficult (the process of calculating the slot is easier)

Fully disperse data items (save space)

Application of Hash Technology

Hash technology not only arranges the storage location of data items in hash tables, but also has many applications in many fields of information processing.

Because the hash function can generate different hash values for any different data, if the hash value is used as the "flag" of the data, this feature can be widely used in data consistency checking.

Because the hash value is often one-to-one and unique, it can be used as a symbol of a data item

As a "flag" of the consistency check amount data, the hash function needs to have the following characteristics:

Compressibility: for data of any length, the hash value calculated by the hash function is easy to calculate with fixed length: it is easy to calculate the hash value ("flag") from the original data. Note that the anti-modification of the original data can not be derived from the "flag": a small change to the original data. Will cause "flags" (hash values) to greatly change the resistance to conflict: knowing the original data and the corresponding hash values ("flags"), it is difficult to find the same hash values again (that is, uniqueness! )

Approximate perfect function: MD5/SHA

MD5 (Message Digset): converts any length of data into a "flag" of a fixed length of 128bits (16 bytes)

128 bits is already a huge digital space, and it is said that there is so much sand on the earth.

SHA (Secure Hash Algorithm)

SHA-0/SHA-1: output hash value of 160bits (20 bytes)

SHA-256/SHA-224: output 256bit and 224bit respectively

SHA-512/SHA-384: output 512 bits and 384 bits respectively

Python's hash function library: hashlib

Python comes with a hash function of MD5 and SHA series: hashlib

Contains: md5, sha1, sha224, sha256, sha384, sha512

Calculation results:

D26a53750bc40b38b65a520292f69306

Application in data consistency check

1. Whether the data files are consistent

Calculate the hash value for each file, and you can know whether the file content is the same by comparing the hash value.

two。 Used to check the integrity of network file download

The hash value of the file is provided when downloading, and the hash value is constantly compared during the download process to see if there is an error in the download.

3. For file sharing system (e. G. Baidu network disk)

The hash values of files are stored in the server, and the same file does not need to be stored multiple times.

4. Save passwords in encrypted form (commonly used)

When registering an account password, the server often stores the hash value corresponding to the password. when the user logs in and enters the password, it is verified by the hash value comparison.

At this point, I believe you have a deeper understanding of "what is the hash in the Python data structure and algorithm". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.