Data structure for hash operation and hash table storage and query method based on data structure

Abstract

The invention belongs to the field of computer hash data structures, in particular to a data structure for hash operation and a hash table storage and query method based on the structure. In order toensure the query efficiency, a dual-port memory bank is adopted for hardware implementation, the content of two addresses of the memory bank can be read at the same time, key value comparison can be completed within the determined time, and the method is suitable for achieving efficient query in an assembly line mode. More candidate positions are provided through more hash operations, the probability of hash conflicts is reduced, the insertion, storage and updating efficiency of hash table entries is improved, dynamic change of hash table entry capacity is supported, space waste or performancereduction caused by table entry insertion operation is avoided, and the method is suitable for applications with unknown and constantly changing hash table entries. A CRC algorithm is adopted as a hash function, a hash calculation result has good uniqueness, the hash calculation result can be obtained on the basis of XOR exclusive-OR operation and a parallel pipeline implementation structure during specific implementation, and hardware design implementation is facilitated.

Description

technical field [0001] The invention belongs to the field of computer hash data structures, in particular to a data structure for hash operations and a hash table storage and query method based on the structure, so as to be suitable for optimal design and hardware realization of high-performance hash tables. Background technique [0002] Hash table (Hash table) is the key data structure for network message flow management. The hash table is based on message keywords. Through hash function operation, you can access the index information corresponding to the stored key value, which greatly improves the search efficiency. The hash function is essentially a transformation that maps elements from a larger input space to a smaller index space. Therefore, two or more keywords may be mapped to the same position. In the hash table, this The situation is called an address collision. When a conflict occurs, it will affect the insertion efficiency of the hash table. Therefore, an eff...

AI Technical Summary

Problems solved by technology

The cuckoo hash algorithm can always complete the query operation within a certain time by detecting more candidate positions, but for inserting or updating key values, it may cause low performance due to conflict handling

Images