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

Hash conflicts occur and what are the methods to solve hash conflicts. For this problem, this article introduces the corresponding analysis and solutions in detail, hoping to help more small partners who want to solve this problem find simpler and easier methods.

By constructing a good hash function, conflicts can be reduced, but it is generally impossible to avoid conflicts completely, so conflict resolution is another key problem of hash methods.

Creating a hash table and looking up a hash table will encounter conflicts, and the methods for resolving conflicts in both cases should be the same.

The following is an example of how to resolve conflicts by creating a hash table. There are four common conflict resolution methods:

open addressing

This method is also called hashing method, its basic idea is: when the hash address p=H (key) of the keyword key conflicts, based on p, generate another hash address p1, if p1 still conflicts, and then based on p, generate another hash address p2,..., until a hash address pi that does not conflict is found.

This method has a general rehashing function form:

Hi=（H（key）+di）% m i=1，2，…，n

where H (key) is the hash function, m is the table length, and di is called the incremental sequence. The value of increment sequence is different, and the corresponding hashing method is also different. There are three main types:

linear detection rehashing

dii=1，2，3，…，m-1

The characteristic of this method is that when conflict occurs, the next cell in the table is looked at in order until an empty cell is found or the whole table is searched.

double probe rehashing

di=12，-12，22，-22，…，k2，-k2 ( 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.