Method and system for processing Hash collision

Abstract

The invention provides a method and a system for processing Hash collision. The method includes separating list items which include a first list item corresponding a first Hash function and a second list item corresponding to a second Hash function and store Hash data; receiving Hash key words and judging whether the Hash collision exists or not, if collision exists in the first list item, storing the Hash key words to the corresponding position of the second list item according to the second Hash function; if no collision exists, storing the Hash key words into the corresponding position of the first list item according to the first Hash function; searching clauses corresponding to the Hash key words sequentially in the first list item and the second list item according to the first Hash function and the second Hash function. On the basis of keeping hardware cost constant, incidence rate of the Hash collision is decrease effectively.

Description

technical field [0001] The invention relates to the technology in the field of network communication, in particular to a method and system for processing hash conflicts. Background technique [0002] Hash (Hash) table is a data structure that is directly accessed according to the key value (key). It stores the key code value by mapping it to a position (index) in the table entry to speed up data lookup. Among them, this mapping function is called a hash function (f), and the array storing records is a hash table. The mathematical expression of the hash table is: index=f(key). In the field of network communication, taking route lookup as an example, the valid range of the hash function input value (key) is the entire address space, and the valid range of the hash function output value (Index) is the maximum specification supported by the system. Obviously, the valid range of the output value is far smaller than the valid range of the input value. Under this premise, no matte...

AI Technical Summary

Problems solved by technology

[0003] In the prior art, in addition to expanding the entry space and constructing a more suitable hash function, the commonly used method to resolve hash conflicts is to "establish a common overflow area". This method stores the data that has hash conflicts in TCAM (three state addressable register), however, although the above method can avoid the occurrence of hash collisions to a certain extent, due to the limited TCAM space and high cost, if the hash collision rate is high and the TCAM space is insufficient, it will lead to conflicts There is nowhere to store the table items, and additional TCAM will inevitably increase the cost of the entire equipment

Images