Hash conflict processing method and system

Abstract

The invention discloses a hash conflict processing method and system. The method comprises the steps of S1, judging whether a hash conflict occurs in a keyword corresponding to data needing to be added or not; s2, if yes, respectively calculating hash values corresponding to the keywords in a plurality of hash buckets, and obtaining a plurality of conflicting data in the plurality of hash buckets;and S3, selecting a hash bucket, and moving one piece of conflicting data in the hash bucket to another hash bucket. According to the invention, the hash conflict can be effectively solved by using data migration of depth-first search, so that the utilization rate of the storage space is improved, the use of a hash conflict solution table is reduced, and the cost and the power consumption are greatly reduced.

Description

technical field [0001] The invention belongs to the technical field of data processing, and in particular relates to a hash conflict processing method and system. Background technique [0002] In fields such as the lookup of the second-layer and third-layer forwarding tables in the switching chip, the use of the hash algorithm is usually involved. First, a brief introduction to the hash algorithm. Hash is also called hash. An index value is obtained by calculating the keyword Key through the hash function F. This index value is called the hash value. Use the hash value as the index of the storage space, and record the data into the storage space. When performing a hash search, the hash function is used to perform hash calculation on the searched keyword Key, and the calculated index is used to retrieve data from the storage space. Hash algorithm lookup is very fast, but has a fatal shortcoming that is hash collision. [0003] When two different keywords key1 and key2 have...

AI Technical Summary

Problems solved by technology

However, the number of hash buckets in this solution cannot be infinite, so there will still be hash collisions

Images