WO2012159480A1

WO2012159480A1 - Table entry adding, deleting and searching method of hash table and hash table storage device

Info

Publication number: WO2012159480A1
Application number: PCT/CN2012/072473
Authority: WO
Inventors: 李彧; 张炜; 孙远航; 崔玉姣; 郑永梅
Original assignee: 中兴通讯股份有限公司
Priority date: 2011-05-25
Filing date: 2012-03-16
Publication date: 2012-11-29
Also published as: CN102194002A

Abstract

Disclosed is a table entry adding method of a hash table, which comprises: splitting a hash table into multiple hash sub-tables, each hash sub-table being corresponding to a bitmap and a hash function; using the hash function to calculate a hash value of a key of a table entry to be stored; and determining an unoccupied position for storing the table entry to be stored according to the hash value. Also disclosed are a table entry deleting and searching method of a hash table and a hash table storage device. According to the present invention, with a rather small search time and high table space utilization rate, all table entries are stored and no table entry is left; the required table entry can be found accurately by accessing the memory once; and meanwhile, an interface between the hardware and the memory can be easily realized, so that the table space size, search efficiency and hardware implementation can be well balanced.

Description

Hash table entry addition, deletion, search method, and hash table storage device

The present invention relates to the field of communications technologies, and in particular, to a method for adding, deleting, searching, and hashing a table of a hash table. Background technique

In the field of communication, there are various matching algorithms. For example, for an exact matching search, a hash algorithm can be employed. The process of hash lookup is to use the hash function to find the key value of the input.

(Key) performs the abbreviated operation, and then uses the calculated hash value to be addressed in the hash index table. After finding the matching item, the hash index (Hash Index) stored in the corresponding item is read, and finally the hash index is used. The direct address mapping table is addressed to get the desired lookup results.

The hash algorithm is a common fast search algorithm. Its basic idea is to use the keyword k of each element in the linear table as an independent variable. Through a certain functional relationship H(k), the corresponding function value is calculated, and this value is interpreted as a unit of continuous storage space, and the element is stored in this unit. The hash algorithm establishes a certain correspondence between the storage location of the element and its keyword. When searching, there is no need to compare, and a hash map can find the required element.

In the hash function, the same hash address may be obtained for different keywords, namely keyl≠key2, and H(keyl)=H(key2), which is called collision (Collision). In general, it is normal to encounter conflicts. The key is how to deal with them after a conflict to achieve the desired search purpose. There are two main methods to deal with conflicts: one is to select and improve the better hash function; the other is to choose the appropriate table item storage structure.

Currently, for applications such as route lookup, a hash function using the CRC (Cyclic Redundancy Checking) class is suitable. Different hash functions under the same bit width can be achieved by selecting different CRC polynomials. Multidimensional hash tables, conflict chains, Double Hashing, etc. can be used to select the appropriate table storage structure to resolve conflicts. The simulation results show that using these methods, under the premise of ensuring that no entries remain, that is, all the entries can be stored, the number of times the hash value is calculated is opposite to the required storage table space, that is, if you want To drop all the entries with a small enough storage space, you need to do a sufficient number of hashes. This will result in multiple accesses to the same table. Since there is only one table, the search can only be performed sequentially, which will seriously affect the speed of the table lookup. On the other hand, if you want to find the storage with a small enough number of calculations Vacancies, then ensure that the storage space is large enough, the space utilization will be greatly reduced. If multiple hash tables are used for parallel search, multiple memory interfaces are required, which is not conducive to hardware implementation. Summary of the invention

The invention provides a method for adding, deleting, searching and hashing a table entry of a hash table, which can realize storage of all entries without a table entry with a minimum search time cost and a high table space utilization rate. At the same time, it only needs to be accessed once to accurately find the required items. At the same time, it is also convenient to implement the interface between hardware and memory, which can achieve better balance in table space size, search efficiency and hardware implementation.

To solve the above technical problem, the technical solution adopted by the embodiment of the present invention is as follows:

A method for adding a table entry of a hash table, including:

Splitting the hash table into multiple hash sub-tables, each hash sub-table corresponds to a bitmap, and each bitmap corresponds to a hash function;

Determining a current target hash sub-table, calculating a hash value of the key value of the table to be stored by using a hash function corresponding to the bitmap corresponding to the current target hash sub-table, and determining, according to the hash value, a current target hash sub-table Whether the storage location is a vacancy, if yes, the information of the to-be-stored entry is stored in the vacancy, otherwise, the current target hash sub-table is updated until a vacancy is found to store the information of the to-be-stored entry.

Further, the bitmap includes a conflict bit and a valid bit, and is determined according to the hash value. Whether the storage location corresponding to the previous target hash sub-table is a vacancy, if yes, the information of the to-be-stored entry is stored in the vacancy, otherwise, the current target hash sub-table is updated until a vacancy is found to store the to-be-stored entry. The steps of the information, including:

Using the hash value as an index, searching for a bitmap corresponding to the current target hash sub-table; determining whether the valid bit of the bitmap is valid, and whether the conflict bit of the bitmap is invalid; if the valid bit If it is valid, and the conflict bit is invalid, it is determined that the storage location corresponding to the current target hash sub-table is a vacancy, and the information of the to-be-stored entry is stored in the vacancy; otherwise, the current target hash is updated. And the step of searching for the bitmap corresponding to the current target hash sub-table by using the hash value as an index, and the method includes:

Determining whether the capacity of the current target hash sub-table is less than the calculated number of bits of the hash value;

If the capacity of the current target hash sub-table is less than the calculated number of bits of the hash value, intercept the hash value, and use the intercepted hash value as an index to find the current target hash sub-table The corresponding bitmap.

Further, after the information of the to-be-stored entry is stored in the vacancy, the method further includes: invalidating the valid position of the bitmap, and storing the key value of the to-be-stored entry into the bitmap.

Further, the step of updating the current target hash sub-table until finding a space to store the information of the to-be-stored item includes:

When the conflict bit of the bitmap is invalid and the valid bit is invalid, the existing entry in the hash sub-table corresponding to the bitmap is taken out, the conflict position is valid, and the key value of the entry is taken out. The key value of the current table to be stored is stored in the bitmap;

Determine whether the current target hash subtable is the last hash subtable, if not the last one The hash sub-table updates the current target hash sub-table to the next hash sub-table until the vacancy is found to store the information of the to-be-stored entry.

When the conflict bit of the bitmap is valid, the key value of the current to-be-stored entry is directly stored in the bitmap;

Determining whether the current target hash sub-table is the last hash sub-table, if not the last hash sub-table, updating the current target hash sub-table to the next hash sub-table until the empty space is found to store the to-be-stored entry Information.

Further, the method further includes:

After the storage of the to-be-stored entry is completed, the conflict bit information of the bitmap and the information of the hash sub-table are synchronously updated.

Further, the hash function corresponding to the hash sub-table is a cyclic redundancy code check function. Further, different cyclic redundancy code check polynomials are used between the hash functions corresponding to the plurality of hash sub-tables.

A hash table entry deletion method, the hash table includes a plurality of hash sub-tables, each hash sub-table corresponds to a bitmap, each bitmap corresponds to a hash function, and each of the bits The figure includes a plurality of entries, and the method includes:

The hash function corresponding to each bitmap calculates the hash value of the item to be deleted in parallel; according to the calculated hash value, it searches in parallel in its corresponding bitmap;

The search results of each bitmap are sequentially compared. When the first occurrence of the conflict bit is invalid, the entry in the hash sub-table corresponding to the address of the bitmap is taken out;

The key value of the fetched entry is compared with the key value to be searched. If they are the same, the entry is deleted from the hash subtable.

Further, after deleting the entry, the method further includes; The conflict position of the corresponding bitmap is invalid, and the valid position is valid.

Further, the method further includes:

Compare all stored key values in all bitmaps before the bitmap in which the deleted entry is located;

If the key value stored in a bitmap is greater than two, delete the key value that needs to be deleted directly; or,

If the key value stored in a bitmap is equal to two, delete the key value that needs to be deleted, and find the location where another key value is stored, take it out, and store it in the corresponding bitmap. In the table.

A hash table search method, the hash table includes a plurality of hash sub-tables, each hash sub-table corresponds to a bitmap, and each bitmap corresponds to a hash function, and the hash table search method Includes:

Using the hash function corresponding to each hash sub-table to calculate the hash value of the key value of the item to be searched in parallel;

The hash value obtained according to the calculation is searched in parallel in the corresponding bitmap;

The key value of the extracted entry is compared with the key value of the entry to be searched. If the key value of the retrieved entry matches the key of the to-be-find entry, the information of the entry is used as a final check. Table results.

Further, the method further includes: if the key value of the extracted entry does not match the key value of the to-be-find entry, returning a message that the search fails.

Further, the step of searching in parallel according to the calculated hash value in the corresponding bitmap includes:

Calculating the capacity of the hash sub-table corresponding to the hash value, and calculating the hash value Line interception

The intercepted hash value is used as an index and is searched in parallel in its corresponding bitmap.

Further, the hash function corresponding to the bitmap is the same as the hash function corresponding to the hash sub-table when the table entry is stored.

A hash table storage device includes a main control logic module, and a control line and a data line connected to the main control logic module, wherein the main control logic module controls the addition and/or deletion of the control line completion entry And the control data line completion entry search, where the control line includes: an entry split module, a target hash sub-determination module, and an entry storage module, where

The table splitting module is configured to split the hash table into multiple hash subtables and multiple bitmaps, and each hash subtable corresponds to a bitmap and a hash function;

The target hash sub-table determining module is connected to the table splitting module, and is configured to determine a hash sub-table from the plurality of hash sub-tables obtained by splitting the table splitting module as a current target. Hash subtable; and after receiving the update instruction issued by the entry storage module, set to update the current target hash subtable to its next hash subtable;

The entry storage module is configured to be connected to the target hash sub-table determining module, and configured to calculate a hash value of the key value of the to-be-stored entry by using a hash function corresponding to the current target hash sub-table. And determining, according to the hash value, whether the storage location corresponding to the current target hash sub-table is a vacancy, and if yes, storing information of the entry to be stored in the vacancy, otherwise sending an update instruction to the target hash sub-determination module, The storage of the to-be-stored entry is not found until the slot is found.

Further, the bitmap includes a conflicting bit and a valid bit, and the entry storage module includes a calculation submodule, a lookup submodule, and an entry add submodule, where

The calculation sub-module is connected to the target hash sub-table determination module, and is configured to calculate a hash value of the key value of the to-be-stored entry by using a hash function corresponding to the current target hash sub-table;

The search submodule is connected to the calculation submodule and configured to determine the target hash The sub-table determines whether the number of bits of the hash value calculated by the module is greater than or equal to the capacity of the current target hash sub-table, and if so, intercepts the hash value, and uses the intercepted hash value as an index to find the corresponding bit. And determining whether the valid bit of the bitmap is valid, and whether the conflict bit of the bitmap is invalid, and if yes, determining that the storage location in the target hash sub-table is a vacancy; otherwise, proceeding to the target The hash sub-table determines that the module sends an update instruction until a space is found;

Adding a sub-module of the entry to the lookup sub-module, and setting, when the search sub-module finds a vacancy in the current target hash sub-table, storing the information of the to-be-stored entry into the Said in the vacancy.

Further, after the sub-module is added to the entry, the information about the to-be-stored entry is stored in the slot, and the entry-add sub-module is further configured to invalidate the valid position of the bitmap. And storing the key value of the item to be stored in the bitmap.

Further, when the searching sub-module determines that the valid bit of the bitmap is invalid, it is further configured to determine whether the conflict bit of the bitmap is invalid, and if yes, the entry adding submodule is set to be The bitmap corresponding to the stored table entry in the hash sub-table, and the key value of the extracted entry and the key value of the current to-be-stored entry are stored in the bitmap; When the module determines that the conflict bit of the bitmap is valid, the entry adding submodule of the entry storage module is configured to store the current key value of the to-be-stored entry into the bitmap.

Further, the hash table includes a plurality of hash sub-tables, each of the hash sub-tables corresponds to a bitmap and a hash function, and the data line includes a parallel computing module, a parallel search module, and a comparison module, where

The parallel computing module is configured to calculate a hash value of the key value of the to-be-find table item in parallel by using a hash function corresponding to each hash sub-table;

a parallel search module, connected to the parallel computing module, configured to search in parallel according to the calculated hash values in their respective bitmaps;

The comparison module is set to compare and compare the lookup results of the respective bitmaps to determine a match. The address of the hash table in which the entry is located, the information of the entry stored in the address is taken out, and compared with the key value to be searched, to determine whether the extracted entry matches the entry to be searched, such as matching. Then the information of the entry is used as the final lookup result.

The method for adding an entry of a hash table according to the embodiment of the present invention, by splitting the hash table into multiple hash sub-tables, and each hash sub-table corresponds to a bitmap and a hash function, and then utilizing The hash function calculates a hash value of the key value of the table to be stored, and the hash value is used to determine the space for storing the entry to be stored, that is, since each hash sub-table is obtained by splitting the hash table. The storage address of the matching entry has been determined in the bitmap, so that all the entries are stored with a minimum update time cost and a high table space utilization, and no entry remains.

The hash table searching method according to the embodiment of the present invention calculates the hash value of the key of the table to be searched in parallel, and searches according to the hash value to the corresponding bitmap, and compares the search results. When the conflicting bit is invalid for the first time, the entry in the hash sub-table corresponding to the address of the bitmap is taken out; compared with the lookup table entry, if it matches, the entry is the table to be searched. Item, because each hash sub-table is obtained by splitting the hash table, and the storage address of the matching table item has been determined in the bitmap, so that only one visit to the hash sub-table can accurately find the need The table entry also facilitates the implementation of the interface between hardware and memory, and achieves a better balance in table space size, search efficiency, and hardware implementation. DRAWINGS

1 is a schematic structural diagram of an embodiment of a hash table storage device of the present invention;

2 is a schematic structural diagram of an embodiment of an entry storage module according to the present invention;

3 is a schematic structural diagram of a specific embodiment of a hash table storage device of the present invention; FIG. 4 is a flowchart of an embodiment of a method for adding a hash table of the present invention; FIG. 5 is a hash of the present invention; A flowchart of an embodiment of step S407 of the table entry adding method of the table;

6 is a flow of an embodiment of step S409b of the method for adding a table entry of the hash table of the present invention; Cheng Tu

7 is a flowchart of an embodiment of a method for deleting an entry of a hash table according to the present invention; FIG. 8 is a flowchart of an embodiment of a method for searching a hash table according to the present invention;

9 is a logical structural diagram of an embodiment of a hash table of the present invention;

FIG. 10 is a flowchart of a specific embodiment of an entry of a hash table of the present invention; FIG. 11 is a schematic diagram of a logical structure of an embodiment of a lookup hash table according to the present invention. detailed description

The present invention will be further described in detail below with reference to the accompanying drawings.

Please refer to FIG. 1 , which is a structural block diagram of an embodiment of a hash table storage device according to an embodiment of the present invention. The hash table storage device of this embodiment includes a main control logic module 100, and a control line and a data line connected to the main control logic module 100, wherein the main control logic module 100 controls the addition and/or deletion of the control line completion entry. The control data line completes the entry search, wherein the control line includes: an entry split module 101, a target hash sub-determination module 102, and an entry storage module 103, wherein the entry split module 101 and the target hash sub-determination module 102 and the entry storage module 103, wherein the table entry splitting module 101 is configured to split the hash table into multiple hash sub-tables and multiple bitmaps, and each hash sub-table corresponds to one bitmap and one The hash function table 102 is connected to the table splitting module 101, and is used as the current target in the first hash sub-table of the plurality of hash sub-tables obtained by splitting the table splitting module 101. Hash subtable, and after receiving the update instruction issued by the entry storage module 103, is used to update the current target hash subtable to its next hash subtable; the entry storage module 103, And the target hash sub-table determination module 102 is configured to calculate a hash value of the key value of the table to be stored by using a hash function corresponding to the current target hash sub-table, and determine a current target hash sub-table according to the hash value. If the corresponding storage location is a vacancy, if yes, the information of the entry to be stored is stored in the vacancy, otherwise the update instruction is sent to the target hash sub-determination module 102 until the vacant storage of the entry to be stored is found.

Please refer to FIG. 2 , which is a schematic structural diagram of an embodiment of an entry storage module according to an embodiment of the present invention. The bitmap in this embodiment includes a collision bit and a valid bit. In the embodiment, the entry storage module includes a calculation submodule 200, a lookup submodule 201, and an entry addition submodule 203, wherein the calculation submodule 200 is connected to the target hash subform determination module for utilizing the current target hash subtable. The corresponding hash function calculates a hash value of the key value of the entry to be stored; the search submodule 201 is connected to the calculation submodule 200, and is used for determining the number of bits of the hash value calculated by the target hash subtable determination module. Whether it is greater than or equal to the capacity of the current target hash subtable, if yes, intercept the hash value, and use the intercepted hash value as an index to find the corresponding bitmap, and determine whether the valid bit of the found bitmap is valid. And if the conflict bit is invalid, if yes, it is determined that the storage location in the target hash sub-table is a vacancy; otherwise, the update instruction is sent to the target hash sub-table determination module until the vacancy is found; the entry adds the sub-module 202, The search sub-module 201 is connected to be used to store the information of the entry to be stored when the search sub-module 201 finds a vacancy in the current target hash sub-table. Bit, and invalidate the valid position of the bitmap, store the key value of the table item to be stored in the bitmap, and when the search sub-module 201 determines that the valid bit of the bitmap is invalid, Determining whether the conflict bit of the bitmap is invalid. If yes, the entry adding submodule is used to take out the stored table entry in the hash sub-table, and extract the key value of the entry and the current table to be stored. The key value of the item is stored in the bitmap; when the search sub-module 201 determines that the conflict bit of the bitmap is valid, the entry adding sub-module 202 is configured to store the key value of the current to-be-stored entry to the bitmap. in.

Each bitmap in this embodiment includes a bit conflict bit and a valid bit, and a plurality of conflict key value storage slots. In this embodiment, the effective position of the bitmap is 0, that is, it is valid, and when it is set to 1, it means invalid; if the conflict position of the bitmap is 0, it means invalid, and setting it to 1 means valid.

Referring to FIG. 1, the data line of the hash table storage device in this embodiment includes a parallel computing module 301, a parallel searching module 302, and a comparison module 303, wherein the parallel computing module 301 is configured to utilize each hash sub-table corresponding to a hash function, the hash value of the key value of the table to be searched is calculated in parallel; the parallel search module 302 is connected to the parallel computing module 301, and is configured to search for the hash values in parallel according to the calculated hash values in their respective corresponding bitmaps. Comparison module 303 for using each bitmap The result of the look-up table is compared and judged, the address of the hash sub-table in which the matching entry is located is determined, the information of the entry stored in the address is taken out, and compared with the key value to be searched to determine whether the entry matches, such as If the match is made, the information of the entry is used as the final lookup result.

In the present embodiment, when the bitmap corresponding to the hash sub-table in the lookup table is stored and the table entry is stored, the bitmap depth corresponding to the hash sub-table is the same; and the hash function corresponding to the hash sub-table and the storage table entry, the hash sub- The hash function corresponding to the table is the same. In the present embodiment, when the entry is looked up, the corresponding bitmap contains only one bit of the conflict bit.

The hash table storage device of the present embodiment splits the hash table into a plurality of hash sub-tables by using the table splitting module, and then the target hash sub-table determining module determines a target hash sub-table from which the entry is The storage module calculates a hash value corresponding to the key value of the table to be stored by using a hash function corresponding to the target hash sub-table, and searches for a space in the target hash table according to the hash value, thereby storing the to-be-stored entry into the In the vacancy, when no vacancy is found, the key value of the entry to be stored is stored in the corresponding bitmap, and the target hash sub-table is updated until a vacancy is found to store the to-be-stored entry, thereby updating with a minimum The time cost and the higher table space utilization realize that all the table entries are stored, and no table entries are left behind; on the other hand, the device uses the parallel computing module to calculate the hash value corresponding to the key value of the table to be searched in parallel, and then by parallel The search module searches for the corresponding bitmap according to the hash value, and finally compares the search result by the comparison module, and extracts the corresponding corresponding address in the hash sub-table address where the entry is located. If the entry matches the entry to be searched, the entry is the entry to be searched, and then it is returned as the final search result, so that each hash subtable passes through the hash. The table is split, and the storage address of the matching entry is determined in the bitmap, so that only one hash subtable can be accessed to accurately find the required entry, and the interface between the hardware and the memory is also facilitated. Implementation, can achieve a better balance in table space size, search efficiency and hardware implementation.

Embodiment 1:

Please refer to FIG. 3 , which is a schematic structural diagram of an embodiment of a hash table storage device according to an embodiment of the present invention. Figure. The hash table storage search system of the present embodiment includes a main control logic module 505, a plurality of calculation modules 502a to 502n, a plurality of search modules 503a to 503n, an entry addition module 504, a statistics module 505, and an entry split module 506. A plurality of bitmap modules 507a to 507n, a plurality of entry storage modules 508a to 508n, a data decision module 509, and an exception processing module 550. The internal connection of the hash table storage device of this embodiment is divided into a data line and a control line. On the data line, the main control logic module 501 is coupled to the plurality of calculation modules 502a-502n, the data decision module 509; and the plurality of calculation modules 502a~ 502n are coupled to the plurality of lookup modules 503a-503n, respectively; the plurality of lookup modules 503a-503n are respectively coupled to the plurality of bitmap modules 507a-507n, and the plurality of bitmap modules 507a-507n are coupled to the plurality of entry storage modules 508a-508n; The main control logic module 501 is coupled to the entry adding module 504, the statistics module 505, the table splitting module 506, and the exception handling module 510, and the entry adding module 504, the statistics module 505, the table splitting module 506, and the exception handling. Modules 510 are each coupled to a plurality of lookup modules 503a-503n, respectively.

The main control logic module 501 is a control component of the hash table storage device, and is mainly used for controlling algorithm startup, termination, task scheduling, data distribution on the data path, and result collection and the like on the control line and the data line.

The master logic module 501 in this embodiment may be implemented by hardware logic, such as an ASIC (Application Specific Integrated Circuit) or an FPGA (Field Programmable Logic Gate Array) or other chip that can implement a logic function. Of course, the main control logic module 501 in this embodiment may also be implemented by software running on a CPU (Central Processing). In this implementation manner, the modules on the control line include an entry adding module 504, and a statistics module 505. The entry splitting module 506 and the exception handling module 550 can all be implemented by software.

The plurality of calculation modules 502a to 502n are coupled to the main control logic module 501 and the plurality of search modules 503a to 503n. In the table item search process, the main control logic module 501 simultaneously sends the key values to be searched to the plurality of calculation modules. 502a ~ 502η, the plurality of calculation modules 502 are configured to perform a hash operation on the assigned key values at the same time to obtain an index different from other calculation modules. Each computing module 502 in this embodiment includes a hash function different from other computing modules 502, and the hash function in this embodiment can be implemented by various known methods, such as an exclusive OR array or a CRC-like CRC. Functions, or through complex mathematical operations, and so on. The selection criterion of the hash function is to reduce the index number conflicts obtained by hash function operations of different key values as much as possible.

A plurality of lookup modules 503a through 503n are coupled to the plurality of compute modules 502a through 502n and the plurality of bitmap modules 507a through 507n, respectively, and a statistics module 505, an entry split module 506, and an exception handling module 510. Each of the search modules 503 in the present embodiment is independently coupled to a bitmap module 507, and accesses and modifies the data in the bitmap module 507 and the storage module 508 corresponding to the bitmap through the address bus and data bus of the bitmap module 507. On the data line, each lookup module 503 receives the different index generated by the compute module 502 and converts it to the address of the bitmap module 507, thereby reading the address corresponding to the data in the memory module 508. After obtaining the data corresponding to the address, the searching module 503 transmits the received index value calculated by the plurality of calculating modules 502a to 502n and the data values obtained by the plurality of bitmap modules 507a to 507n to the data decision module 509 and Finding a key value comparison to determine whether a match is made; on the control line, the plurality of search modules 503a to 503n receive the read/write instructions issued by the statistics module 505, the table item splitting module 506, and the exception handling module 509, and convert the plurality of bitmap modules 507a into The address of ~507n operates on the stored data in the plurality of bitmap modules 507a to 507n, and further operates the data stored in the plurality of storage modules 508a to 508n.

The search module 503 in this embodiment simultaneously implements the functions of the control line and the data line. Of course, the corresponding search module can also be set for the control line and the data line respectively. In this embodiment, there may be an expansion of the index value, an addition or subtraction of an offset or an interception operation.

The plurality of bitmap modules 507a to 507n are respectively coupled to the plurality of search modules 503a to 503n, and each of the bitmap modules 507 has an independent address access bus and an independent data bus. For each module, the address bus and the data bus can be complexed. Use, but multiple storage modules 508 Without multiplexing, the plurality of bitmap modules 507a to 507n are respectively coupled to the plurality of search modules 503a to 503n through the independent address access bus and the independent data bus, and the plurality of search modules 503a to 503n access the plurality of addresses by transmitting addresses. The bitmap modules 507a to 507n correspond to data (conflict bits, valid bits and key values) stored at the transmitted address, and the plurality of bitmap modules 507a to 507n further correspond to one of the storage modules 508a to 508n, and each of the storage modules 508 A hash sub-table is stored, and each sub-table is obtained by splitting the hash table by the table item splitting module 506, and the storage address of the matching entry is determined in the bitmap module 507, and only the storage module 508a is accessed once. ~ 508n, so the memory modules 508a ~ 508n share a set of address access bus and data bus.

A plurality of bitmap modules 507a through 507n are coupled to the plurality of lookup modules 503a through 503n, respectively. Each of the bitmap modules has a separate address access bus and a separate data bus. For each module, the address bus and the data bus can be multiplexed, but multiple entries are not multiplexed between the storage modules. The plurality of bitmap modules 507a to 507n are respectively coupled to the plurality of search modules 503a to 503n through the independent address access bus and the independent data bus, and the plurality of search modules 503a to 503n can access the plurality of bitmap modules 507a by sending addresses. 507η corresponds to the data (conflict bit, valid bit and key value) stored at the transmitted address. The plurality of bitmap modules 507a to 507n respectively correspond to one entry storage module 508a to 508n, and each entry storage module stores a hash sub-table, wherein each sub-table is obtained by splitting the hash table, because The storage address of the matching entry has been determined in the bitmap, and only the entry storage modules 508a-508n are accessed once, so the entry storage modules 508a-508n share a set of address access bus and data bus.

The plurality of bitmap modules 507 and storage modules 508 in this embodiment may be implemented by various data storage technologies currently in existence. Since the bitmap module 507 requires parallel access and takes up less storage space, it can be implemented with on-chip SRAM. For the storage module 508, for example, in an application scenario requiring less delay, n independent high-speed SRAM chips can be used as the storage. Modules 508a to 508n, the high-speed SRAM chip may be various commonly used SRAM chips such as ZBT SRAM, QDR SRAM, QDRII SRAM, QDRII+ SRAM; in the case where a large-capacity entry space is required, n independent high-speed lines may be used. The DRAM chip is used as the storage modules 508a-508n. The high-speed DRAM chip may be various commonly used SDRAM chips such as SDRAM, DDR SDRAM, DDRII SDRAM, DDRIII SDRAM, etc. In the case where data needs to be saved by power-down, n can be used. The independent FLASH chip is used as the storage modules 508a to 508n, and the FLASH chip may be NAND FLASH, NOR FLASH, NV RAM or other commonly used memory chips; in the case of massive data, the storage modules 508a to 508n may also be It can be realized by a plurality of independent hard disks, a plurality of independent disk storage arrays, or a mass data storage technology such as an optical disk drive, and a plurality of bitmap modules 507a to 507n and a storage module can be arbitrarily selected without departing from the scope of the present embodiment. Implementation medium of 508a ~ 508η.

The data decision module 509 is coupled to the plurality of search modules 503a-503n and the plurality of storage modules 508a-508n to complete the decision operation of the search result. The plurality of lookups 503a to 503n, after obtaining the search results of the plurality of bitmap modules 507a to 507n, transfer the result to the data decision module 509, and the data decision module compares the search results of the bitmap modules 507a to 507n in the order of a~n to find out The bitmap module 507 with the first conflict bit is 0, and the found bitmap address is transmitted to the plurality of storage modules 508a to 508n, and the data acquired from the storage module 508 is transmitted to the data decision module 509, and transmitted according to the main control logic module 501. The original key value from the comparison, whether the data is a matching entry, because the plurality of search results obtained by the plurality of search modules 503a to 503n are from conflict bits stored in the plurality of bitmap modules 507a to 507n, and the conflict bits are only It will be set to 0 when it does not conflict with other entries. If there is a conflict, it will be set to 1. Therefore, the data stored in the storage module corresponding to the address with the first occurrence of the conflicting bit is 0. Therefore, There is no duplicate entry in this, only one result of finding the storage module 508 is a possible correct result, or the returned result is inconsistent with the key value, and the hash search is lost. defeat. When the lookup is correct, the data decision module 509 returns the index value in the correct set of data to the master logic module 501, representing The result of this hash search; in the case of a search failure, the data decision module 509 will return to the master logic module 501 an invalid index value or an interrupt signal, informing the master logic module 501 that the current search failed.

The table item splitting module 506 and the table item adding module 504 work together to split the hash table into N (N>=l) hash subtables and store them in a plurality of storage modules 508. Each hash subtable corresponds to a bitmap and a hash function, and the storage size of N hash subtables and N bitmaps can be selected as needed. For example, the 32-th power of 2, in the hash sub-table generation process, the table item splitting module 506 sequentially selects one of the M items, and sets the target hash sub-table and the bitmap as the first hash sub-table and the bitmap. The entry is passed to the entry addition module 504. The entry adding module 104 calculates the index value K of the entry according to the hash function corresponding to the first hash sub-table, and attempts to store the entry in the hash sub-table corresponding to the hash function. The position of the index value K, at the same time, the conflicting position 0 in the corresponding index value K position in the bitmap corresponding to the hash sub-table, the valid position 1, and the original 43⁄4 value is stored in the position.

In this embodiment, when the table splitting module 506 splits multiple hash sub-tables, it is possible to encounter a hash conflict, that is, two different key values are calculated to obtain the same hash sub-table. The same index value. In this case, if the bitmap conflict bit of the location is 0, the valid bit is 1, indicating that the location has been placed in an entry, and the data of the entry storage module corresponding to the index value needs to be taken out, and The conflicting bit value 1 in the bitmap corresponding to the index value, the current key value and the key value corresponding to the fetched entry are placed in the bitma; if the bitmap conflict bit of the location is 1, indicating that the location has collided more than once, The current key value is placed in the bitmap. When the above two conflict situations occur, the failure message is returned to the table item splitting module 106, and the table item splitting module 506 determines whether the current target hash sub-table is the last hash sub-table, and if not, the item is The target sub-table is set to the next sub-table, and is passed to the entry adding module 504 to repeat the above process; If it is already the last hash sub-table, a failure message is returned to the main control logic module 501, and the exception processing module 509 is called by the main control logic module 501 to complete the update of the hash table.

Although the entry adding module 504 in this embodiment is on the control line, the contents of the bitmap module 507 and the storage module 508 can be read or modified by the plurality of lookup modules 503a to 503n.

The exception handling module 510 and the statistics module 505 are coupled to the plurality of lookup modules 503 and the master control logic module 501, respectively, to perform tasks such as system monitoring and error recovery. If each query fails, the statistics module 505 will count it into the lookup failure record. The exception processing module 510 is configured to respond to the hash table refresh request sent by the master logic module 501, and clear the plurality of Bitmap modules 507a to 507n and the plurality of storage modules 508a to 508n through the plurality of search modules 503a to 503n. Reassign operation.

The hash table storage device of this embodiment will be divided into two parts, a data line and a control line, for detailed description.

The data line is composed of a main control logic module 501, a plurality of calculation modules 502a to 502n, a plurality of search modules 503a to 503n, a plurality of Bitmap modules 507a to 507n, a plurality of storage modules 508a to 508n, and a data decision module 509. The data line is used to complete the search operation, and the control line is composed of the main control logic module 501, the item addition module 504, the statistics module 505, the table item splitting module 506, and the exception handling module 510. The entry adding module 504 is coupled to the plurality of searching modules 503 for adding the conflicting state information and the entry data to the plurality of bitmap modules 507a to 507n and the plurality of storage modules 508a to 508n, wherein the control line is used to complete the entry addition and Delete operation.

In the hash table storage device of this embodiment, the hash function corresponding to the hash sub-table obtained after the splitting may be a CRC function or other functions, and the CRC function is used as the hash sub-table corresponding to the embodiment. When the hash function is used, different CRC polynomials can be used between the hash functions corresponding to several hash subtables. Based on the hash table storage device described above, the embodiment further provides a method for adding a strong entry of a hash table.

Referring to FIG. 4, it is a schematic flowchart of an embodiment of a method for adding an entry of a hash table according to the embodiment. The method for adding an entry of the hash table in this embodiment includes:

S401, the hash table is split into multiple hash sub-tables, and each hash sub-table corresponds to a bitmap, and each bitmap corresponds to a hash function.

The key influencing factor of the split in this embodiment is the size of the storage space of each sub-table. The storage space of the multiple hash sub-tables in this embodiment may be selected according to requirements. For example, the size of each small table space may be set to be the same, or the size of the storage space may be decreased. However, the split mode is not limited to the above two modes. .

S403: The first hash sub-table is used as the current target hash sub-table.

S405: The key value of the storage entry is taken, and the hash value corresponding to the current target hash sub-table is used to calculate the hash value.

S407. Determine, according to the calculated hash value, whether the storage location corresponding to the current target hash sub-table is a vacancy. If yes, go to step S409a. Otherwise, go to step S409b.

S409a: The information of the entry to be stored is stored in the slot, and step S4011 is performed. The information of the entry in this embodiment includes information such as a table key value and a table lookup result.

S409b, updating the current target hash sub-table and performing step S405.

S4011, invalidating the valid position in the bitmap, and storing the key value of the item to be stored into the bitmap.

S4013: After the storage of the to-be-stored entry is completed, the conflict bit information of the bitmap and the information of the hash sub-table are synchronously updated.

Please refer to FIG. 5, which is a flowchart of an embodiment of step S407 of the present embodiment. Step S407 in this embodiment includes:

S501, determining whether the capacity of the current target hash sub-table is less than the calculated hash value, and if so, Then, step S503a is performed, otherwise step S503b is performed.

S503a, according to the bit number corresponding to the capacity of the hash sub-table, intercepting the same bit number of the calculated hash value from the high bit, obtaining the intercepted hash value, and using the intercepted hash value as The index is executed in step S505.

S503b, directly using the calculated hash value as an index, and executing step S505.

S505. Find a null bit in the target hash sub-table according to the index, that is, determine whether the valid bit of the bitmap is 0, and the conflict bit of the bitmap is 0. If yes, the storage location corresponding to the target hash sub-table is a vacancy. Then, step S409a is performed; otherwise, step S409b is performed.

Referring to FIG. 6, step S409b in this embodiment includes:

S601. Determine whether the conflict bit of the bitmap is 0, and whether the valid bit is 1. If yes, step S603a is performed. If the conflict bit of the bitmap is 1, step S603b is performed.

S603a, the bitmap corresponding to the stored table in the hash sub-table is taken out, and the conflict position of the bitmap is set to 1, and step S605 is performed.

S603b: The key value of the current to-be-stored entry is stored in the bitmap, and step S607 is performed. S605: The key value of the fetched entry and the key value of the current to-be-stored entry are stored in the bitmap. S607. Determine whether the current target hash sub-table is the last hash sub-table. If yes, go to step S609a, otherwise go to step S609b.

S609a, returns a storage failure message, and ends the operation.

S609b, updating the target hash sub-table to the next hash sub-table, and executing step S405. In the method for adding a hash table of the present embodiment, the hash function corresponding to the hash sub-table is a cyclic redundancy code check function, and the hash functions corresponding to the multiple hash sub-tables adopt different cyclic redundancy. Code check polynomial.

The method for adding an entry of the hash table in this embodiment, by splitting the hash table into multiple hash sub-tables, and each hash sub-table corresponds to a bitmap and a hash function, and then using the hash The function calculates a hash value of the key value of the table to be stored, and the hash value determines the storage of the entry to be stored. Vacancies. Since each hash sub-table is obtained by splitting the hash table, and the storage address of the matching entry is determined in the bitmap, the implementation is achieved with a small update time cost and a high table space utilization rate. All entries are stored, and no entries are left behind.

The embodiment further provides a method for deleting an entry of a hash table. The hash table in this embodiment includes a plurality of hash sub-tables, each of which corresponds to a bitmap, each bitmap corresponding to a hash function, and each of the bitmaps includes a plurality of entries. Referring to FIG. 7, the entry deletion method of the hash table storage device in this embodiment includes:

S701. The hash function corresponding to each bitmap calculates the hash value of the item to be deleted in parallel. S703. Search according to the calculated hash values in parallel in their respective bitmaps. S705: sequentially compare the search results of each bitmap, and when the first occurrence of the conflict bit is invalid, extract the entry in the hash sub-table corresponding to the address of the bitmap.

S707. Compare the key value of the extracted item with the key value to be searched. If they are the same, perform step S709.

S709, the entry is deleted from the hash subtable.

S7011, the conflict position of the corresponding bitmap is 0, and the valid position is 0.

S7013: Compare all the stored key values in all the bitmaps before the bitmap in which the deleted entry is located. If the key value stored in a bitmap is greater than two, step S7015a is performed, if some If the key value stored in the bitmap is equal to two, step S7015b is performed.

S7015a, directly delete the key value to be deleted, and end.

S7015b, deletes the key value that needs to be deleted, and finds the location where another key value is stored. S7017: The entry corresponding to another key value is taken out and stored in the hash sub-table corresponding to the bitmap.

The embodiment further provides a hash table search method. The hash table searched in the method is composed of a plurality of hash sub-tables, and the storage space size of the plurality of hash sub-tables can be selected according to requirements. Each bitmap has a separate address control line that can be accessed at the same time, all the hashes The table shares a set of address control lines, and each table entry looks up only once for the hash subtable. Each hash subtable corresponds to a hash function, and the hash function corresponding to each hash subtable is the same as the hash function corresponding to the hash subtable when the table entry is stored.

Please refer to FIG. 8 , which is a flowchart of an implementation principle of the hash table searching method according to the embodiment. The hash table search method in this embodiment mainly includes the following steps:

S801. The hash values corresponding to the key values of the table to be searched are calculated in parallel by using multiple hash functions corresponding to the plurality of hash sub-tables.

S803, searching according to the calculated hash value in parallel in the corresponding bitmap.

S805, comparing the search results of each bitmap, and when the conflict bit is 0 for the first time, extracting the entry in the hash sub-table corresponding to the address of the bitmap corresponding to the conflict bit.

S807, the key value of the extracted entry is compared with the key value of the entry to be searched. If the key value of the retrieved entry matches the key of the to-be-find entry, step S809a is performed, otherwise, execution is performed. Step S809b.

S809a, the information of the entry is used as the final lookup result.

S809b, returns a message that failed to find.

Step S805 in this embodiment includes: intercepting the hash value according to the calculated hash sub-table corresponding to the hash value; using the intercepted hash value as an index, in the corresponding bitmap and the hash sub- Look in parallel in the table.

The hash table searching method in this embodiment, by performing a hash value of the key value of the table to be searched in parallel, and searching according to the hash value to the corresponding bitmap, and comparing the search results, when the first time When the conflicting bit is invalid, the entry in the hash sub-table corresponding to the address of the bitmap is taken out; compared with the lookup table entry, if the match is matched, the entry is the entry to be searched, because Each hash subtable is obtained by splitting the hash table, and the storage address of the matching entry is determined in the bitmap, so that only one hash subtable can be accessed to accurately find the required entry. , also facilitates the implementation of the interface between the hardware and the memory, can be in the table space A good balance between size, search efficiency, and hardware implementation.

Embodiment 2:

Referring to FIG. 9, which is a logical structure diagram of an embodiment of a hash table according to an embodiment, each hash sub-table corresponds to a bitmap and a hash function, wherein input key values are input to the local through the input interface. In the hash sub-table of the embodiment, the hash value of the input key value is calculated by the hash table storage device, and the hash value is used as an index to search for a space in the bitmap and the hash sub-table, and is filled in; wherein bitmap0~9 is 10 For the same size, the state table with the depth of m is stored. The hash sub-tables 0~9 are 10 memories of the same size and storing the depth m.

The hash table storage device in this embodiment is used to complete all operations on input key values according to user requests, including addition, lookup, monitoring, exception handling, and the like. Referring to FIG. 3, when the hash key is input to the main control logic module 501, the main control logic module 501 selects a hash function, and uses the hash function to calculate a corresponding hash value through the hash calculation logic, and adds an entry. The logic module 504 completes the work of adding an entry, and the lookup logic module 503 completes the lookup of the specified hash key. The hash table storage device of this embodiment further includes a delete entry logic module, and a monitor logic module, which are not shown in the drawings. The delete entry logic module completes the work of deleting the entry; the monitoring logic module monitors the space occupation in the hash sub-table during the process of adding and deleting the entry, and feeds this information back to the main control logic module 501.

In this embodiment, if all the hash subtables cannot be added to the exception processing of the hash table, the exception processing logic 510 is required to perform processing to maximize the addition of all the entries. In the table.

Referring to FIG. 10, which is a flowchart of a specific embodiment of a method for adding an entry of a hash table according to the embodiment, the method includes the following steps:

S1001: Calculate a 16-bit hash value of a key value of the to-be-stored entry by using a hash function corresponding to the i-th hash sub-table, that is, a CRC16 function.

In this embodiment, the initial value of i is 0, and the value ranges from 0 to 9. S1003: Determine whether the table capacity of the i-th hash sub-table is less than the calculated hash value, and if yes, execute step S1005a, otherwise perform step S1005b.

S1005a, the calculated 16-bit hash value is intercepted from the high-order bit, and the intercepted hash value is used as an index, and step S1007 is performed.

S1005b, using the calculated hash value as an index.

S1007: Find, according to the index value, whether there is a space in the i-th hash sub-table, that is, determine that the conflict bit in the corresponding bitmap is 0, and the valid bit is 0. If yes, execute step S1009; otherwise, execute step S1011.

S1009: Put all the information corresponding to the table to be stored into the found space, and set a conflict position 0 and a valid position 1 in the corresponding bitmap.

At this point, the calculation of this entry and the end of the stored procedure begin to store the next entry.

S1011, if the conflict bit of the bitmap is 0, and the valid bit is 1, that is, the address has stored one entry, step S1012 is performed; if the conflict bit of the bitmap is 1, step S1013 is performed.

S1013: The stored entry is taken out, and the current key value and the extracted entry key value are stored in the bitmap, and the conflict position is 1, and step S1017 is performed.

S1013: Store the current key value in the corresponding bitmap.

S1015, i = i + l , returns to step S1001, and starts to find the gap in the next table until the slot is found to store the entry.

Please refer to FIG. 11 , which is a logical structural diagram of an embodiment of a lookup table entry in the embodiment. For a hash key value to be searched, the hash function 0 to 9 is first calculated in parallel. The hash value, each hash function here must be the same as the hash function used to store the table entry; then the calculated hash value is used as the index value to search in parallel in the corresponding bitmap table to determine the matching table. The address of the item, the address is transferred to the hash sub-table memory fetch entry, and each hash sub-table memory still has a port for CPU access; finally, the fetched entry is compared with the key value to be searched to determine the match. , all the information of the item as the final The result of the lookup table is returned to the user, and the process of checking the table ends.

Since all 10 bitmap tables are searched in parallel during the search, only one search cycle and one cycle read the hash sub-table memory can achieve all hits, thus realizing the premise of guaranteeing the absence of the entry. Faster hash lookup with a smaller on-chip table space capacity and a memory interface.

Embodiment 3:

Referring to FIG. 9, the figure is a logical structure diagram of an embodiment of a hash table in the embodiment. The input key value is input to the hash sub-table of the embodiment through an input interface, and the input is input through a hash table controller. The key value calculates its hash value, and the hash value is used as an index to find the empty space in the hash sub-table and fill in; wherein the hash sub-table 0-9 is 10 memories, representing 10 hash sub-tables, and bitmap0~9 is 10 A state table, but the first four of the ten memories in this embodiment have a memory depth of m, and the last six have a memory depth of m/2.

The logical structure of the hash table controller in this embodiment, the storage of the hash table, the search process, and the logical structure of the lookup table are exactly the same as those in the second embodiment.

Compared with the second embodiment, the space utilization rate of the third embodiment is higher. It is to be understood that the specific embodiments of the invention are limited only by the description. It is to be understood by those skilled in the art that the present invention may be practiced without departing from the spirit and scope of the invention.

Claims

Claim

A method for adding an entry of a hash table, where the method includes:

The method of claim 1, wherein the bitmap includes a conflict bit and a valid bit, and determining, according to the hash value, whether a storage location corresponding to the current target hash sub-table is a vacancy, and if so, The information about the storage entry is stored in the slot. Otherwise, the current target hash sub-table is updated until the slot is found to store the information of the to-be-stored entry, including:

Using the hash value as an index, searching for a bitmap corresponding to the current target hash sub-table; determining whether the valid bit of the bitmap is valid, and whether the conflict bit of the bitmap is invalid; the valid bit is If the conflicting bit is invalid, and determining that the storage location corresponding to the current target hash sub-table is a vacancy, the information of the to-be-stored entry is stored in the vacancy; otherwise, the current target hash sub-table is updated. The information of the item to be stored is stored until the vacancy is found.

3. The method according to claim 2, wherein the using the hash value as an index, searching for a bitmap corresponding to the current target hash sub-table is:

The method of claim 2, wherein after the information of the item to be stored is stored in a space, the method further includes:

The valid position of the bitmap is invalid, and the key value of the table to be stored is stored in the bitmap.

5. The method according to claim 2, wherein the updating the current target hash sub-table until the location of the vacant space to store the to-be-stored entry is:

Determining whether the current target hash sub-table is the last hash sub-table, if not the last hash sub-table, updating the current target hash sub-table to the next hash sub-table until the vacancy is found to store the to-be-stored The information of the entry.

The method of claim 2, wherein the updating the current target hash sub-table until the location of the vacant space to store the to-be-stored entry is:

The method according to any one of claims 1 to 6, wherein the method further comprises: synchronously updating the conflict bit information of the bitmap and the information of the hash sub-table after the storage of the to-be-stored entry is completed.

The method according to any one of claims 1 to 6, wherein the hash function corresponding to the hash sub-table is a cyclic redundancy code check function.

The method according to any one of claims 1 to 6, wherein the plurality of hash sub-tables Different cyclic redundancy code check polynomials are used between the corresponding hash functions.

10, a hash table entry deletion method, wherein the hash table includes multiple hash sub-tables, each hash sub-table corresponds to a bitmap, each bitmap corresponds to a hash function, and each The bitmap includes a plurality of entries, and the method includes:

The method according to claim 10, wherein after the deleting the entry, the method further includes:

The conflict position of the corresponding bitmap is invalid, and the valid position is valid.

12. The method of claim 10, wherein the method further comprises:

Compare all key values stored in all bitmaps before the bitmap in which the deleted entry is located;

A hash table search method, wherein the hash table includes a plurality of hash sub-tables, each hash sub-table corresponds to a bitmap, and each bitmap corresponds to a hash function, and the method includes: Using the hash function corresponding to each hash sub-table to calculate the hash value of the key value of the table to be searched in parallel; The hash value obtained according to the calculation is searched in parallel in the corresponding bitmap;

The method of claim 13, wherein the method further comprises: if the key value of the retrieved entry does not match the key of the to-be-find entry, returning a message that the search fails.

The method according to claim 13 or 14, wherein the calculated hash value is found in parallel in the corresponding bitmap as:

Obtaining the hash value according to the calculated capacity of the hash sub-table corresponding to the hash value;

The method according to claim 15, wherein the hash function corresponding to the bitmap is the same as the hash function corresponding to the hash sub-table when the table entry is stored.

17. A hash table storage device, comprising a main control logic module, and a control line and a data line connected to the main control logic module, wherein the main control logic module controls the addition of the control line completion entry and/or Or deleting, and controlling the data line completion entry search, where the control line includes: an entry split module, a target hash sub-determination module, and an entry storage module, where

The target hash sub-table determining module is connected to the table splitting module, and is configured to determine a hash sub-table from the plurality of hash sub-tables obtained by splitting the table splitting module as a current target. Hash subtable; and after receiving the update instruction issued by the entry storage module, setting To update the current target hash subtable to its next hash subtable;

The device of claim 17, wherein the bitmap includes a conflicting bit and a valid bit, the entry storage module includes a computing submodule, a searching submodule, and an entry adding submodule, wherein the calculating a sub-module, connected to the target hash sub-table determining module, configured to calculate a hash value of the key value of the to-be-stored entry by using a hash function corresponding to the current target hash sub-table;

The search sub-module is connected to the calculation sub-module, and is configured to determine whether the number of bits of the hash value calculated by the target hash sub-table determination module is greater than or equal to the capacity of the current target hash sub-table, and if so, intercept The hash value, and taking the intercepted hash value as an index, searching for a corresponding bitmap, and determining whether the valid bit of the bitmap is valid, and whether the conflict bit of the bitmap is invalid, if yes, Determining that the storage location in the target hash sub-table is a vacancy; otherwise, sending an update instruction to the target hash sub-table determination module until a vacancy is found;

The device according to claim 18, wherein, after the entry adding sub-module stores the information of the to-be-stored entry into the slot, the entry adding sub-module is further configured to be The valid position of the bitmap is invalid, and the key value of the table to be stored is stored in the bitmap.

The device according to claim 18, wherein, when the finding sub-module determines that the valid bit of the bitmap is invalid, it is further configured to determine whether the conflict bit of the bitmap is invalid, such as If yes, the entry adding submodule is configured to take out the stored table entry in the hash sub-table, and store the key value of the extracted entry and the key value of the current to-be-stored entry. Entering into the bitmap; when the lookup sub-module determines that the conflict bit of the bitmap is valid, the entry add sub-module of the entry storage module is set to be the current to-be-stored table The key value of the item is stored in the bitmap.

The apparatus of claim 17, wherein the hash table comprises a plurality of hash sub-tables, each hash sub-table corresponds to a bitmap and a hash function, and the data line comprises a parallel computing module. a parallel search module and a comparison module, wherein

The comparison module is configured to compare and compare the lookup results of the respective bitmaps, determine the address of the hash sub-table in which the matching entry is located, take out the information of the entry stored in the address, and perform the key value that needs to be searched. The comparison determines whether the extracted entry matches the entry to be searched. If the entry is matched, the information of the entry is used as the final lookup result.