Method and apparatus for processing hash calculations

Hash calculation processing method and device TECHNICAL FIELD

The present invention relates to the technical field of data processing, and particularly to a method and apparatus for hashing processing. Background technique

Hash table (Hash Table), also known as hash table, it is a very versatile and highly efficient data lookup table. By mapping function key is mapped to a value, the mapping function called a hash function, the value is called the hash value. Hash value is usually used as the location of the table to access records to accelerate speed up the search. However, for different keywords when performing hash calculation, you might get the same hash value, which is key key 1 ≠ Key2, and the hash value Η (key 1) = Η (Key2), a phenomenon known as hash punch

To solve the hash collision, the usual practice is built on the same hash value hash buckets, each hash bucket storage Ν records form the list of conflict, when looking, first by the hash function to find a given value Κ Η hash address Η (Κ), then Η (Κ) read Ν records whose hash bucket for the address of the last keyword to Ν Κ record read out an exact match, if found to have match record, the search is successful, otherwise lookup fails. However, this method there is a problem in the chain length of hash collisions when packets keywords hash calculation produces uncontrollable, if the length of hash collision chain is too long will lead to packet storage efficiency low.

Ternary content addressable memory (Ternary Content Addressable Memory, called TCAM) is a dedicated hardware chip to locate operations, mainly used to quickly find the access control list (Access Control List, ACL), routing table entries, the conflict entry into the TCAM, it is possible that the length of the chain hash collision controlled.

In the implementation of the present invention, the inventors have found that at least the following problems of the prior art: the art of problem solving hash collision packets and preclude the use of hash buckets to establish a method can not control the chain hash collision length, if the length of the hash chain is too long will lead to a conflict of packets stored in Burgundy 4 low efficiency; and by the method of TCAM achieve hashed, although able to control the chain length of hash collisions Degree, but higher implementation costs. SUMMARY

Embodiments of the present invention to provide a hash calculation processing method and apparatus for solving the prior art, there is a higher chain length hash collision control costs.

Technical solution preclude the use of embodiments of the present invention are:

One kind of hash calculation processing method comprising:

Receive messages, it extracts the message needs to be the keyword hash calculation;

Using a hash function to the primary keyword hash calculation to obtain a hash value and the main keyword corresponding;

Analyzing the number of entries in the first of the main conflict with the hash value of the corresponding primary hash memory block is smaller than a preset maximum number of conflicts; wherein said main memory block includes a hash of at least one of said first a conflict entries, each of the first conflict entry corresponds to a keyword, each of the first entry corresponding keyword conflict through the use of the main primary hash function hash calculated after the same value; the maximum number of collisions if the number of entries in the first conflict with the primary hash memory blocks less than the establishment of a keyword corresponding to the first conflict with a hash table in the main memory block item;

If the number of entries in the first conflict with the primary hash memory block is not less than the maximum number of collisions, the hash function for the use of the alternate keywords hash calculation to obtain the corresponding keyword standby Kazakhstan Greek values, establish the key corresponding to the second entry in the conflict and spare the hash hash value corresponding spare memory blocks; wherein the primary hash value and the hash value does not spare same, the hash spare memory block includes at least one of the second conflict entries, each entry corresponding to the second conflict in a keyword, each of the second conflict entries by the corresponding keyword the alternate alternate hashed hash function calculated by the same value.

One kind of hash calculation processing device, comprising:

Receiving module for receiving a packet;

Keyword extraction module for extracting the packets need to be hashed keywords; the main hash calculation module for use with the primary hash function to calculate the hash key, To obtain a hash value and the main keyword corresponding;

First judging module for judging the maximum number of collisions preset number of entries in the first conflict with the primary hash hash value of the corresponding primary storage is less than a block; wherein said primary storage with hash block includes at least one of the first conflict entry, each of the first conflict entry corresponds to a keyword, get after each of the first conflict table entry corresponding to the primary keyword is calculated by using the hash function the main hash values ​​are the same;

The first conflict entry establishing module, when the number of entries in the first active collision hash memory block is less than the maximum number of conflicts for the establishment of the key and the hash in the main memory block word corresponding to the first entry of conflict;

Alternate hash calculation module for, when the number of entries in the first conflict with the primary hash memory block is not less than the maximum number of collisions, the hash function for the use of the alternate keywords hash calculation to obtain and the corresponding spare key hash value;

The second conflict entry establishing module for establishing the keyword corresponding to the second entry in the conflict and spare the hash hash value corresponding spare memory blocks; wherein the main use of the hash value the alternate hash values ​​are not identical, the hash spare memory block includes at least one of the second conflict entries, each entry corresponding to the second conflict in a keyword, each of the second conflict entries the corresponding keywords from the backup after the hash function to calculate a hash value obtained by the same backup.

Hash calculation processing method and apparatus provided by the embodiment of the present invention, by extracting the packets need to be keyword hash calculation using a hash function to the primary keyword hash calculation to obtain the keyword corresponding primary hash value, number of entries in the first conflict with the judgment of the primary hash value corresponding to the primary hash memory block is smaller than a preset maximum number of collisions, if the primary storage with hash number of entries in the first block of the conflict is less than the maximum number of collisions is established and the key corresponding to the first entry in the main conflict with the hash memory block, if the primary hash memory block the number of entries in the first conflict is not less than the maximum number of collisions, the hash function for the use of the alternate keywords hash calculation to obtain spare hash value corresponding to the key in the standby Kazakhstan Greek hash value of the corresponding spare memory block to establish the key corresponding to the second conflict entries. Embodiment of the invention mention Hash calculation processing method and apparatus for in packets of hash calculation processing keywords, you can use low-cost solution to the prior art when packets keywords hashed generated Kazakhstan Greek conflict chain length problem can not control, thereby improving storage efficiency packets. BRIEF DESCRIPTION

In order to more clearly illustrate the embodiments of the present invention, technical implementation of the program, we will implement the following figures for the cases described in the prior art or the need to use a simple introduction. Apparently, the following description of the drawings are merely present invention Some embodiments, those of ordinary skill in speaking, without creative efforts premise, you can also obtain other drawings based on these drawings.

Figure 1 is a hashing processing method according to the invention provides a flow chart of implementation;

Figure 2 is a schematic hash calculation processing method according to a second embodiment of a flow chart;

Figure 3 is a schematic view of the structure of the invention the hash memory block according to a second embodiment;

Figure 4 is a schematic view of the structure of the invention the main memory block number hash table of the first conflict item according to a second less than the maximum number of conflicts implementation;

Figure 5 (a) Schematic diagram of the present invention, the main memory block number of the first hash table conflict according to a second term of not less than the maximum number of conflicts implementation;

Figure 5 (b) the structure of the present invention, a schematic view of an alternate hash memory block according to a second embodiment; FIG. 6 hash calculation processing method of the present invention is provided in the third embodiment of the flow chart of embodiment;

7 of the present invention the hash calculation processing method according to a fourth embodiment of a flow chart;

8 embodiment of the present invention means a hash structure diagram Example V provides calculation processing;

9 of the present invention to provide a hash Five cases of work flow chart illustrating calculation processing means;

FIG. 10 is a circuit diagram of hardware hash invention provides five cases of calculation processing apparatus embodiment; Fig. 11 a schematic view of the structure of the present invention provides apparatus embodiment five hash calculation processing;

FIG. 12 embodiment of the present invention to provide structural diagram means five cases hash calculation processing;

FIG. 13 is a schematic view of the structure of the invention the hash calculation processing device provided five embodiments. detailed description

The present invention will now be combined with the implementation of the accompanying drawings, were clear examples of technical solutions of the present invention, fully described, it is clear that the described embodiments are merely part of the embodiments of the present invention, but not all embodiments. Based on the embodiments of the present invention, all other embodiments of the ordinary skill in the creative work did not make the premise obtained, are within the scope of the present invention is protected.

To make advantage of the present invention as set clearer, the accompanying drawings and the following embodiments of the present invention will be described in detail.

Embodiment 1

The present embodiment provides a hash calculation processing method, as shown in Figure 1, the method comprising:

101, the received message, the message needs to extract a keyword hash calculation;

102, using a hash function to the primary keyword hash calculation to obtain a hash value and the main keyword corresponding;

103, the number of entries in the first conflict with the judgment of the primary hash value corresponding to the primary hash memory block is smaller than a preset maximum number of conflicts; wherein said main memory block includes a hash at least one said first conflict entries, each of the first conflict entry corresponds to a keyword, the main conflict after each of the first entry corresponding to the primary key is calculated by a hash function was used hash values ​​are the same;

104, the maximum number of collisions if the number of entries in the first conflict with the primary hash memory blocks less than the establishment of a keyword corresponding to the first entry in the main conflict with the hash memory block ;

105, if the number of entries in the first conflict with the primary hash memory block is not less than the maximum number of collisions, the hash function for the use of the alternate keywords hash calculation to obtain the corresponding keywords alternate hash value, and the establishment of a keyword corresponding to the second entry in the conflict and spare the hash hash value corresponding spare memory blocks; wherein the primary and the backup with the hash value hash values ​​are not identical, the hash spare memory block includes at least one of the second conflict entries, each entry corresponding to the second conflict in a keyword, each of the second conflict entries by the corresponding keyword the backup of the backup after the hash function calculates a hash obtained the same value. Hash calculation processing method according to an embodiment of the present invention, by extracting the packets need to be keyword hash calculation using a hash function to the primary keyword hash calculation to obtain the corresponding keywords master hash value, number of entries in the first conflict with the judgment of the primary hash value corresponding to the primary hash memory block is smaller than a preset maximum number of collisions, if the primary storage block hash the first conflict table a number less than the maximum number of collisions is established and the key corresponding to the first entry in the main conflict with the hash memory block, if the primary hash memory block the first number of entries in the conflict is not less than the maximum number of collisions, the hash function for the use of the alternate keywords hash calculation to obtain a hash value and the spare key corresponding to the hash value in the standby corresponding spare memory block hash and build a keyword corresponding to the second conflict entries. Hash calculation processing method according to an embodiment of the present invention, in packets of keywords hash calculation processing can be generated when the prior art packet keywords hashed low-cost way to solve problems length hash conflict uncontrollable chain, thereby improving storage efficiency packets.

Second Embodiment

The present embodiment provides a hash calculation processing method, as shown in Figure 2, the method comprising:

201, received message, extracting the packets need to be the IP address of the hash calculation;

202, using a hash function to the primary IP address of the packet is hashed to obtain a hash value of the IP address of the primary and the only Burgundy corresponding text;

203, the number of entries in the first conflict with the judgment of the primary hash value corresponding to the primary hash memory block is smaller than a preset maximum number of conflicts; wherein said main memory block includes a hash at least one said first conflict entry, IP address conflict first entry corresponding to each one of the packets, each of said first conflict table entry corresponding to the IP address of the packet is calculated by using the hash function after the main the main obtained with the same hash value;

204, the maximum number of collisions if the number of entries in the first conflict with the primary hash memory block is less than, is established with an IP address of the packet corresponding to the first hash in the main memory block conflict entries;

Wherein the conflicting entries include: whether to use an alternate hash function hash calculation marks, Table entry valid flag and the IP address of the packet. Shown in Figure 3, Figure conflict table entry whether to use an alternate hash function to calculate the hash marks B for the identification of the message using the IP address of the primary hash function hash calculation, or use alternate hash function hash calculation. For example, when B = 0, it means that the primary use of a hash function on the IP address of the packet is hashed, when B = l, it indicates that a hash function to use an alternate IP address of the packets will be Kazakhstan Greek calculations. FIG conflict table entry valid flag entry D for identifying the conflict entry is valid, when D = l, it indicates that the entry is valid conflict, when D = 0, it indicates that the conflict entry is invalid .

The hash memory block comprising: a flag if there is a conflict entries by alternate hash function and build an alternate hash function type flag. Specifically, shown in Figure 3, you can set a common alternate hash function counter C in the hash memory block, for the second conflict entries by alternate hash function established by counting, when C = 0 , it means that there is no conflict entries by a second alternate hash function established when C = l, it indicates the presence of a second conflict entries by alternate hash function established. FIG hash memory block spare hash function type flag T, indicating whether or not to set up an alternate hash function, when T = 0, it means there is no set up an alternate hash function.

205, when the number of entries in the first conflict with the primary hash memory block is not less than the maximum number of collisions to determine the main memory block hash hash function in the backup type flag is set ;

206, if the primary storage block hash hash function type of the backup flag has been set, according to the alternate hash function symbol type, select the type of backup hash function symbol corresponding hash function as an alternative hash function;

207, if the primary is not provided with the hash stored in the backup block type flag hash function, a hash function to select a hash function as a backup, and disposed in said primary memory block hashed alternate hash function type flag;

Specifically, you can choose to generate a hash function than the main hash collision hash function less as an alternate hash function;

Alternatively, by using at least one hash function to the IP address of the packet hash calculation, the hash function value at least one IP address of the packet corresponding to the at least one select a The number of collisions hash table entries corresponding to the hash function value storage block is less than the maximum number of hash function as a backup conflict hash function.

208, using the hash function to alternate IP address of the packet is hashed to obtain a hash value and standby IP address of the packet corresponds;

209, to establish the IP address of the packet corresponds to the second entry in the conflict and spare the hash hash value corresponding spare memory block.

Specifically, the initial value of the primary hash memory blocks public spare hash function counter is set to a predetermined number (for example, 0), when the main block is a hash of the first memory when the conflict table is not less than the maximum number of collisions, the establishment of the IP address of the packet corresponds to the second conflict in the hash table entry in the spare memory block and said main memory block with hash the count value of the counter of the common hash function plus one spare.

The maximum number of collisions shown in Figure 4, for example, the default produce hash collisions in a hash storage block 6, after receiving the message, the message needs to extract hashed IP address, assuming the packets IP address 10.0.0.1, using a hash function to the primary message hashed IP address 10.0.0.1, obtain the IP address of 10.0.0.1 ^ Gen text corresponding primary Kazakhstan Xi is 1, number of entries in the first conflict with the judgment of the primary hash value 1 corresponds to the master hash memory block is 0, less than the maximum number of collisions 6, in the main memory hash establishment and block the packet IP address 10.0.0.1 corresponding first conflict entries. And if the received message 11.0.0.1, extracting the packets need to be hashed IP address of 11.0.0.1, using the hash function to the main message hashed IP address 11.0.0.1 to obtain a hash value and the main message is the IP address 11.0.0.1 corresponding to 1, number of entries in the first conflict with the judgment of the primary hash value 1 corresponding to the primary storage block is a hash 1, less than the maximum number of collisions 6, the establishment and the packet IP address 11.0.0.1 corresponding to the first entry in the main conflict with the hash memory block, in which case the primary hash memory block the number of entries in the first conflict to 2. Similarly, in turn received only Burgundy message 12.0.0.1, only Gen Wen 13.0.0.1, only Gen Wen 14.0.0.1, only Gen Wen 15.0.0.1, using the master hash function sequentially IP address 12.0.0.1, 13.0.0.1, 14.0.0.1, 15.0.0.1 hashed to obtain the IP address of 12.0.0.1, 13.0.0.1, 14.0.0.1, 15.0.0.1 corresponding primary hash value is 1, Analyzing the main hash value corresponding to the number of entries in a primary storage block hash first conflict were 2, 3, 4, 5, are less than the maximum number of collisions 6, in the main hash memory block to establish IP address 12.0.0.1, 13.0.0.1, 14.0.0.1, 15.0.0.1 corresponding first entry conflict, this time with the number of entries in the main memory block first hash conflict 6.

Shown in Figure 5 (a), if then receives the IP address 16.0.0.1 of the packet, using the hash function to the main message hashed IP address 16.0.0.1, to obtain a hash value and the main message of the corresponding IP address 16.0.0.1 is also 1, number of entries in the first conflict with the judgment of the primary hash value 1 corresponding to the primary storage block is a hash 6, no less than the maximum number of collisions 6, determining whether the main memory block hash hash function in the backup type flag T is set, if the primary hash spare memory block in the Kazakhstan Greek flag function type T = l, indicating that the primary hash has been set in the spare memory block hash function type flag, according to the alternate hash function symbol type, select the type of backup hash function flag corresponding hash function hash function as a backup; if the primary storage block hash hash function type the alternate flag Τ = 0, indicating that the spare memory block in the main hash said Kazakhstan the Greek flag is not set function type, select a hash collisions produce less than the primary hash function hash function hash function as a backup, or at least a hash function on the IP address of the packet through the use of hash calculation, the hash function value at least one IP address of the packet corresponding to the number of entries to select a conflict with the at least one hash function hash value corresponding memory block is less than the maximum conflict the number of hash function hash function as a backup, use the hash function to the backup packets IP address 16.0.0.1 hashed to obtain the IP address of the packets 16.0.0.1 corresponding spare Kazakhstan Greek value of 16, and set the backup type hash function with the hash mark in the main memory block. FIG. 5 (b), in the standby hash value hash 16 corresponding spare memory block to establish the packet IP address 16.0.0.1 corresponding second conflict entry and the the count value of the main memory block spare hash hash function counter is incremented by one.

Hash calculation processing method according to an embodiment of the present invention, the main memory block with the hash set a flag if there is a conflict entries by alternate hash function and build an alternate hash function type flag, when the main hash number of entries in the first memory block conflict is not less than the maximum number of conflicts, Determining whether said main memory block with a hash of the hash function type backup flag is set, if the primary storage block hash hash function type the backup flag has been set, according to the backup hash function symbol type, select the type of backup hash function symbol corresponding hash function hash function as a backup, use the hash function to the alternate keyword hash calculation to obtain the keyword corresponding alternate hash value, establish the key corresponding to the second entry in the conflict and spare the hash hash value corresponding spare memory block. Hash calculation processing method according to an embodiment of the present invention, in packets of keywords hash calculation processing can be generated when the prior art packet keywords hashed low-cost way to solve hash conflict chain length uncontrollable problems, thereby improving the efficiency of message storage.

Third Embodiment

The present embodiment provides a hash calculation processing method shown in Figure 6, the method comprising:

601, with the hash function using the main keywords packets hashed to obtain a hash value and the main keyword corresponding;

602, to find the key corresponding to the first entry in the conflict hashed primary memory block, it is determined whether the found keywords corresponding to the hash stored in the main block said first conflict entries;

603, if found the key corresponding to the first entry in the main conflict with the hash memory block, returns the search results;

604, and if not found the key corresponding to the first entry in the conflict hashed primary storage block, obtaining a hash of the primary memory blocks by the presence or absence of the alternate hash flag conflict entry and the backup function creates hash function type flag;

605, according to the primary storage block with the hash of the presence or absence of a conflict entry flag established by the alternate hash function, and determines whether there is the key corresponding to the first hash function established by alternate two entries conflict;

606, if the key does not exist corresponding to the second conflict entries by alternate hash function established, return to no avail; 607, if the key corresponding to the second entry is a conflict based on a perception alternate hash function, using the master hash of the spare memory block flag corresponding to the type of hash function Hash alternate the hash function key calculation, the alternate hash value corresponding to the key;

608, to find the key to whether the keywords found with the corresponding entry in the second conflict with the alternate hash hash value corresponding spare memory blocks;

609, if found with the keyword corresponding to the second conflict in the hash table entry in the spare memory block, returns the search results, if not found in the spare memory block with the hash key word corresponding to the second conflict entry is returned to no avail.

If not found with the keyword corresponding to the first conflict with the hash table entries in the main memory block, using the main memory block spare hash hash function hash calculation processing method according to an embodiment of the present invention alternate hash function symbol corresponding to the type of keywords hash calculation to obtain spare hash value corresponding to the key, and look at the backup and the hash value corresponding to the spare memory block hash said second key corresponding conflict entries returned search results. Compared to the prior art, the hash calculation processing method provided by the present invention, when the key is not found and the corresponding entry in the first conflict with the primary hash memory block, then the hash stored in the spare Find the key block corresponding to the second entry conflict, seek time can be shortened packets, thereby increasing search efficiency packets.

Fourth Embodiment

The present embodiments provide a hash calculation approach, shown in Figure 7, the method comprising: 701, looking for keywords packets corresponding first conflict with the hash table entries in the main memory block;

702, it is determined whether or not the keywords found with the corresponding entry in the first conflict with the primary hash memory blocks;

703, if found with the keyword corresponding to the first entry in the main conflict with the hash memory block, remove the key corresponding to the first conflict of the entry;

704, if not found in the main block with the hash stored in the first punch and the corresponding keywords Sudden entry, access to the main memory block hash in the presence or absence of signs of conflict entries by alternate hash function and the establishment of alternate hash function type flag;

705, according to the primary storage block with the hash absence flag conflict entries by alternate hash function, determine whether there is the key corresponding to the first hash function established by alternate two entries conflict;

Specifically, if there is a second conflict entries created by the primary backup by using a hash function hash memory blocks public spare hash function counter judgment, if the primary hash memory block the count value of the counter alternate hash function is not 0, then there is a conflict created by the alternate entry hash function, a hash count if the primary storage block alternate hash function counter is 0, conflict entries created by the alternate hash function does not exist.

706, if the key does not exist corresponding to the second conflict entries by alternate hash function established, return to no avail;

707, if the key corresponding to the second entry is a conflict based on a perception alternate hash function, using the master hash of the spare memory block flag corresponding to the type of hash function Hash alternate the hash function key calculation, the alternate hash value corresponding to the key;

708, looking for the key corresponding to the second entry in the conflict spare hash hash value corresponding spare memory blocks; key word corresponding to the second entry of the conflict;

710, if found with the keyword corresponding to the second conflict in the hash table entry in the spare memory block, and remove the key corresponding to the entry of the second conflict, if the said spare hash hash value corresponding spare memory block is not found with the keyword corresponding to a second conflict entry is returned to no avail.

After Specifically, delete the keyword corresponding to the second conflict in the hash table entry in the spare memory block, the count value of the main memory block hash hash function standby counter is decremented. Hash calculation processing method according to an embodiment of the present invention, if found and message keywords corresponding first entry in the main conflict with the hash memory block, remove the main block in the hash memory and the key corresponding to the first entry of conflict, if not found the key corresponding to the first entry in the main conflict with the hash memory block, looking for the hash in the spare memory block said second key corresponding conflict table, if found, remove the key corresponding to the second conflict in the hash table entry in the spare memory block. Compared to the prior art, the hash calculation processing method provided by the present invention may be a low cost solution to the length of the prior art packet keywords hashed generated hash collision chain can not control problems in order to improve storage efficiency packets.

Embodiment 5

The present embodiment provides a hash calculation processing means 8, the apparatus comprising: a receiving module 801 for receiving packets;

Keyword extraction module 802 for extracting the packets need to be hashed keywords; the main hash calculation module 803 for using a hash function to the primary keyword hash calculation to obtain and the corresponding primary key hash value;

The first judgment module 804, number of entries in the first conflict with the main memory block is used to determine the hash and the hash value corresponding to the primary is less than the maximum number of pre-conflict; wherein the main hash memory block includes at least one of the first conflict entry, each of the first conflict entry corresponds to a keyword, each of the first conflict entry corresponding keyword is calculated by using the hash function after the main the main obtained with the same hash value;

The first conflict entry establishing module 805 is used when the number of entries in the first conflict with the primary hash memory block is less than the maximum number of conflicts and the establishment of a hash stored in the main block keyword corresponding to the first entry of conflict;

Alternate hash calculation module 806, for when the main number of entries in the first collision hash memory block is not less than the maximum number of collisions, the hash function for the use of the alternate keywords hash calculation, get spare hash value and the corresponding keywords;

The second conflict entry establishing module 807, and the backup for the hash value corresponding to spare memory hash Establishment and the memory block corresponding to the second key entry conflicts; wherein said primary backup hash with the hash value of the value is not the same, the hash spare storage block comprises at least one of said second conflict entries, the second entry corresponding to each of the conflict a keyword, the same hash value for each of the second alternate conflict entries by keywords corresponding to the hash function standby after calculated.

9, after the adoption of the receiver module to receive messages by the keyword extraction module extracts the message needs to be the keyword hash calculation using the master by the master Ha hash calculation module Greek key function of the hash calculation to obtain a hash value and the master key corresponding to the first judgment by the judge and the main module of the hash value corresponding to the primary hash memory block the first conflict is less than the maximum number of entries in a preset number of collisions, if the number of entries in the first conflict with the primary hash memory block is less than the maximum number of conflicts, through the establishment of the first conflict entry module establishes the key corresponding to the first entry in the main conflict with the hash memory block; if the number of entries in the first conflict with the primary hash memory block is not less than the maximum number of collisions, by using the hash calculation module alternate alternate hash function to the keyword hash calculation to obtain a hash value and the spare key corresponding to the establishment of the module with the spare Kazakhstan by a second conflict entries Greek hash value of the corresponding spare memory block to establish the key corresponding to the second conflict entries.

Specifically, as shown in FIG. 10, the receiving module receives the message later, the keyword extraction module processors (such as CPU) extract the message needs to be the keyword hash calculation of the master hash calculation module by the main processor uses a hash function to the keyword hash calculation to obtain a hash value and the main keyword corresponding to a hash value and the main to the memory for storage. The first judgment by the number of entries in the first module of the conflict with the main processor determines a hash value corresponding to the primary hash memory block is less than the maximum number of conflicts in the preset memory, If the number of entries in the first conflict with the primary hash memory block is less than the maximum number of collisions, the first conflict entry establishing module by the processor, and the establishment of the primary hash memory block the key corresponding to the first entry of conflict, and through the interface unit sends the hash calculation processing result to another device; if the number of entries in the first conflict with the primary hash memory block is not less than the maximum conflict number, the hash calculation module uses alternate alternate hash function by the processor To the keyword hash calculation to obtain a hash value and the spare key corresponding to the second conflict entry establishing module by the processor in the stand with the hash hash value corresponding to spare establishment of the memory block corresponding to the second conflict keyword entries, and through the interface unit sends the hash calculation results to other devices.

Further, the conflict entries include: whether to use an alternate hash function hash calculation marks, and the valid flag entry keyword.

Further, the hash memory block comprising: a flag if there is a conflict entries by alternate hash function and build an alternate hash function type flag.

Further, as shown in Figure 11, the main hash calculation module 803 comprises:

Determination means 8031, for determining whether the primary storage block with the hash hash function type backup flag is set; type flag has been set, according to the primary storage block with the hash of the backup hash function symbol type, select the type of backup hash function symbol corresponding hash function hash function as a backup;

First calculation unit 8033, a hash function for using the spare key to the hash further shown in Figure 11, the main hash calculation module 803 may also include: the type of flag is not set when selecting a hash function hash function as a backup;

The first calculation unit 8033, are also used in the alternate hash function to calculate the hash key;

Setting unit 8035 for setting the backup type hash function with the hash mark in the main memory block.

Further, as shown in FIG. 11, the second selecting unit 8034 further includes:

The first sub-selection unit 80341 for selecting a hash collision than generating the master hash function Less hash function hash function as a backup;

Second selecting sub-unit 80342 for using at least one hash function to the hash key calculation, the hash function value corresponding to at least one of the keyword and choose one of the at least one hash number of collisions entries corresponding to the hash function value storage block is less than the maximum number of hash function as a backup conflict hash function.

Further, as shown in FIG. 12, the apparatus may further comprise:

Lookup module 808, find the key corresponding to the first entry in the main conflict with the hash memory blocks;

Back module 809 for, when found the key corresponding to the first entry in the main conflict with the hash memory block, returns the search results;

Acquisition module 810, when used in the main memory block is not found in the hash and the key corresponding to the first conflict entry is obtained when the main memory block in the hash whether flag conflict entries by alternate hash function to establish the presence and the type of backup hash function symbol;

Second determining module 811, according to said main memory block hash in the presence or absence of a conflict entry flag established by the alternate hash function, and determines whether or not the key to establishing the existence of the hash function by an alternate word corresponding to the second conflict entries;

The return module 809, when used with the keywords corresponding to the second entry does not exist conflict through the establishment of alternate hash function, return to no avail;

The alternate hashing module 806 is also used when there is established with the keyword corresponding to the second entry conflicts by alternate hash function, using the master hash in the memory block alternate alternate hash function hash function symbol corresponding to the type of keywords hash calculation to obtain spare hash value corresponding to the key; to find the key corresponding to the second conflict entries ;

The return module 809 is also used as spare memory blocks found in the hash and the key corresponding to the second entry in the conflict, the return to the search results; The return module 809 is also used when the spare memory block is not found in the hash and the key corresponding to the second conflict entry, return to no avail.

Further, as shown in FIG. 13, the apparatus may further comprise:

The lookup module 808, also used to find the key corresponding to the first entry in the main conflict with the hash memory blocks;

Remove module 812 for, when found with the keyword corresponding to the first entry in the main conflict with the hash memory blocks when the delete key and the corresponding one of said first conflict entries.

Further, as shown in FIG. 13, the apparatus may further comprise:

The acquisition module 810 is also used as the main memory block is not found in the hash and the key corresponding to the first conflict entry, access to the main memory block in the hash said if there are signs of conflict entries by alternate hash function and the establishment of alternate hash function type flag; the second judgment module 811, also according to whether the primary use of the hash memory block flag conflict entries by the presence of alternate hash function established to determine whether there is the keyword corresponding to the second conflict entries by alternate hash function established;

The return module 809 is also used when there is no keyword corresponding to the entry of the second conflict through the establishment of alternate hash function, return to no avail;

The alternate hashing module 806 is also used when there is established with the keyword corresponding to the second entry conflicts by alternate hash function, using the master hash in the memory block alternate hash function symbol corresponding to the type of hash function to spare the keyword hash calculation to obtain a hash value and the spare key corresponding; to find the key corresponding to the second entry of conflict;

Remove the module 812 is also used when found with the keyword corresponding to the second conflict in the hash table entry in the spare memory blocks when deleting the corresponding said first and said keyword two entries conflict; Not found with the keyword corresponding to the second entry of the conflict, the return to no avail. Hash calculation processing apparatus according to an embodiment of the present invention, the keyword extraction module extracts packets need to be keyword hash calculation using the primary hash function with the hash calculation module through the main keywords of the Kazakhstan Greek calculation, the primary hash value and the corresponding keywords, number of entries in the first conflict with the judgment by the first judging module main hash value corresponding to the primary hash memory block is less than the pre the maximum number of conflicts established, the maximum number of collisions if the number of entries in the first conflict with the primary hash memory blocks less than the establishment of modules and the master hash memory block established by the first conflict entry the key corresponding to the first entry of conflict, if the number of entries in the first conflict with the primary hash memory block is not less than the maximum number of collisions, the hash function for the use of the alternate keywords hash calculated to obtain a hash value and the spare key corresponding to establishing module built with the alternate hash hash value corresponding to the spare memory block with the keywords corresponding second entry through a second conflict conflict . Hash calculation processing apparatus according to an embodiment of the present invention, in packets of keywords hash calculation processing can be generated when the prior art packet keywords hashed low-cost way to solve problems length hash conflict uncontrollable chain, thereby improving storage efficiency packets.

The method of computing the hash processing apparatus provided by the embodiment of the present invention may be provided by the above-described embodiment, the specific design, please refer to the method described in the example embodiment, is not described here. Hash calculation processing method and apparatus embodiments of the invention may be applied to provide data communications and wireless communications products switches routers, but is not limited to this.

Those skilled in the art can understand the implementation of the above-described embodiments of the method in all or part of the steps by a computer program instructing relevant hardware, the program may be stored in a computer readable storage medium, the program when executed, the process as the above method embodiments. Wherein the storage medium may be a magnetic disk, optical disk, read-only memory memory (Read-Only Memory, ROM) or random-^ "i have memory body (Random Access Memory, RAM) and the like.

The above is only a specific embodiment of the present invention, but the scope of the present invention is not limited thereto, and any skilled in the art in the art within the technical scope disclosed by the present invention can be easily Change or replace thought, it should fall within the scope of the present invention. Accordingly, the scope of the present invention should be in the scope of the claims shall prevail.