Method and device for adding, searching for and deleting key in hash table

Abstract

The present invention discloses a method and device for adding, searching for and deleting a key in a hash table, wherein, the method for adding a key in a hash table includes: calculating both the bucket address corresponding to the key to be added and the address extension of the key to be added in each hash sub-table according to a hash function; generating the fingerprints of the key to be added corresponding to each hash sub-table, wherein the fingerprint of the key to be added corresponding to one hash sub-table includes: the address extension of the key to be added in the hash sub-table, and the bucket address corresponding to the key to be added and the address extension of the key to be added in other hash sub-tables; and when determining that there is no conflict, storing the fingerprint of the key to be added corresponding to the selected hash sub-table into the selected hash sub-table. The solution of the present invention enables that the fingerprint of each key can only match one fingerprint in one hash sub-table, thus when searching for a key, at most once is required to visit an original key table, thereby improving the search performance, and simplifying the search process.

Description

technical field [0001] The invention relates to the field of communication technology, in particular to a method and device for adding, searching or deleting key values ​​in a hash table. Background technique [0002] Due to its high lookup performance, hash tables are widely used in the field of communication technology. A hash table generally consists of one or more hash sub-tables. An address space in a hash sub-table is called a bucket. Each bucket is composed of multiple slices (slots). Each slice can store A key value (key). Each hash subtable corresponds to a hash function (hash function), the key value is input to the hash function, and the output result is the address of the bucket that stores the key value in the corresponding hash subtable. The utilization of a hash table is defined as the number of keys to be stored divided by the number of shards in all hash subtables. If the number of key values ​​to be stored is 8M (8388608), the hash table includes two has...

AI Technical Summary

Problems solved by technology

Suppose y1 and x1 correspond to the same address in subtable 1, but now subtable 1 is full, only y1 can be put into subtable 2

In this way, it is guaranteed that there is no conflict between x1, x2, x3 and y1, but it cannot guarantee that other key values ​​​​do not conflict with y1, for example, it is difficult to guarantee that z2 and y1 do not conflict

Images