CN108287840B - A Data Storage and Query Method Based on Matrix Hash - Google Patents

Abstract

The invention relates to a data storage and query method based on matrix hash. The method includes: 1) establishing a hash table data structure, which includes z sub-tables, z is an even number, and the sizes of the sub-tables decrease equally;

Combining the i-th sub-table with the z-i+1-th sub-table, we get

2) establish an auxiliary data structure, which includes z bloom filters corresponding to the z sub-tables, and the sizes of each bloom filter are equidistantly decreasing; for

Combining the i-th Bloom filter with the z‑i+1-th Bloom filter, we get

Bloom filters of equal size; then the

Corresponding bits of each Bloom filter are added together to form a multi-bit Bloom filter; 3) Key-value pairs are inserted by using the hash table data structure and the auxiliary data structure to realize data storage. The present invention can realize fast update and fast query.

Description

A Data Storage and Query Method Based on Matrix Hash

technical field

The invention belongs to the technical field of in-memory databases, and in particular relates to a data organization, index and storage method based on a matrix hash algorithm.

Background technique

Compared with disk database, in-memory database has higher flexibility and ease of use. In-memory database can be divided into relational in-memory database and key-value in-memory database from the paradigm. The key-value-based in-memory database (Key ValueStore) has the advantages of flexibility and simplicity, saving memory, and fast query. Compared with the relational in-memory database, it has unique advantages, so it is widely used in major Internet companies, such as Amazon, Facebook , Youtube, Baidu, Sina, Sohu, etc. The data of the key-value storage system exists in the form of key-value pairs and is stored in a hash table. Therefore, the hash algorithm, as the core technology of the key-value storage system, is a key factor that directly affects the system performance and website efficiency.

The actual problem at present is that with the rapid development of the Internet, many Internet companies have accumulated a large amount of data. Due to the huge number of key-value pairs, the available memory space is limited, so when a new key is inserted When the value is paired, the conflict of the key-value pair will be more. Such conflicts will lead to the failure of inserting new key-value pairs, the failure of updating and searching of existing key-value pairs, etc., which greatly affects the performance of the key-value storage system, thus causing great economic losses to Internet companies using the key-value storage system. loss.

At the same time, customers have higher and higher demands and requirements for data operations, and they need to quickly obtain data query results. Therefore, higher requirements are placed on the responsiveness of Internet companies. If Internet companies cannot respond immediately, it will greatly affect the user experience. .

The above two problems widely exist in major Internet companies applying key-value storage systems, and the existing hash table designs are constantly trying new ideas to better solve these two key problems. First of all, for the conflict problem, the existing hash table designs widely use auxiliary data structures (such as Bloom filters) to reduce the conflict probability. A typical algorithm design is fast hash table (H. Song, S. Dharmapurikar, J. Turner, and J. Lockwood. Fasthash table lookup using extended bloom filter: an aid to network processing. ACM SIGCOMM Computer Communication Review , 35(4):181–192, 2005.), segment hash (S.Kumar and P.Crowley.Segmented hash: an efficient hashtable implementation for high performance networking subsystems.In Proc.ACMANCS,pages 91–103, 2005.), peacock hash (S. Kumar, J. Turner, and P. Crowley. Peacock hashing: Deterministic and updatable hashing for highperformance networking. In Proc. IEEE INFOCOM, 2008.). For a new key-value pair that needs to be inserted, these hash designs use Bloom filters to determine the hash table to insert. For conflicting key-value pairs, either use a pointer to hang on the linked list, or discard it. Although these hash designs use multiple subtables to reduce collisions, there are still drawbacks, such as lower load rates. There is also a large room for reduction in the conflict rate.

The second is the query time problem. The typical hash design is perfect hash (Z.J.Czech,G.Havas,andB.S.Majewski.An optimal algorithm for generating minimal perfect hashfunctions.Information Processing Letters,43(5):257– 264, 1992.), Cuckoo Hash (B.Fan,D.G.Andersen,and M.Kaminsky.Memc3:Compact and concurrent memcache withdumber caching and smarter hashing.In NSDI,volume 13,pages 385–398,2013.), etc. However, the disadvantage of these hashes is that they are very inefficient to update, requiring a large number of hash calculations and memory accesses. For example, cuckoo hashing requires nearly 500 hash calculations and memory accesses when updating the hash table, and even then, there is a high chance that the update will fail. So with these hash table designs, if multiple updates fail, the entire hash table will have to be rebuilt. The reconstruction process will take a lot of time, which is unacceptable for real application systems.

SUMMARY OF THE INVENTION

In order to solve the problem of hash table conflict and query time, and overcome the defects of high conflict rate, low memory usage efficiency, low loading rate, etc. existing in the existing hash table, the present invention provides a multi-subtable hash and bloom filter. , a new hash table design scheme combined with bitmap - "Matrix Hash".

The technical scheme adopted in the present invention is as follows:

A data storage method based on matrix hash, is characterized in that, comprises the following steps:

将第i个子表和第z-i+1个子表结合，得到

个大小相等的子表；1) Establish a hash table data structure, which includes z sub-tables, z is an even number, and the size of each sub-table decreases equally; for

Combining the i-th sub-table with the z-i+1-th sub-table, we get

subtables of equal size;

将第i个布隆过滤器和第z-i+1个布隆过滤器结合，得到

个大小相等的布隆过滤器；然后将该

个布隆过滤器的对应比特追加在一起，形成1个多比特布隆过滤器；2) establish an auxiliary data structure, which comprises z bloom filters corresponding to the z sub-tables, and the size of each bloom filter is equidistantly decreasing; for

Combining the i-th bloom filter and the z-i+1-th bloom filter, we get

Bloom filters of equal size; then the

The corresponding bits of each Bloom filter are appended together to form a multi-bit Bloom filter;

3) Using the hash table data structure and the auxiliary data structure to insert key-value pairs to realize data storage.

Further, whenever a new key-value pair is inserted, it is inserted into the child table with the smallest load rate.

Further, a linked list is attached to the last sub-table, that is, the z-th sub-table. If the key-value pair to be inserted cannot find an empty bucket, a pointer is used to attach it to the linked list.

Further, each subtable corresponds to a bitmap, and each bit in the bitmap corresponds to a bucket in its corresponding subtable; the bit in the bitmap corresponding to an empty bucket is 0, and the bitmap corresponding to a non-empty bucket is 0. bit is 1.

以减少查询的子表数。Further, add an additional bloom filter F _half , which is responsible for recording the second part of the subtable, namely

to reduce the number of subtables queried.

Further, key-value pairs are inserted as follows:

则更新布隆过滤器F_i来表示键x在子表T_i中，并更新对应位图；如果

则更新布隆过滤器F_z-i+1来表示x在子表T_i中，并更新F_half和对应位图；a) For a given key-value pair, first check whether the z candidate buckets are empty through the bitmap, and then insert the key-value pair into the child table with the lowest loading rate to balance the loading rate of all child tables; The subtable index of i is i, if

Then update the Bloom filter F _i to indicate that the key x is in the sub-table T _i , and update the corresponding bitmap; if

Then update the Bloom filter F _z-i+1 to represent that x is in the sub-table T _i , and update F _half and the corresponding bitmap;

b) If the bitmap shows that the z buckets into which the key x should be inserted are all full, then use the kick mechanism to implement key-value pair insertion.

返回true，且F_half返回false，则检查子表T_i；否则，先检查子表T_z-i+1，如果没有匹配，再检查子表T_i；如果在z个子表中都无法查找到x，则查找最后一个子表的链表；如果仍然无法找到，则说明x不在哈希表中。Further, the query method of key-value pairs is: when querying x, first query x in the multi-bit Bloom filters F _m and F _half , if

Returns true, and F _half returns false, then check the sub-table T _i ; otherwise, check the sub-table T _{z-i+1 first} , if there is no match, then check the sub-table T _i ; if none of the z sub-tables can be found x, then look up the linked list of the last sublist; if it still cannot be found, it means that x is not in the hash table.

Further, the deletion method of the key-value pair is as follows: when deleting x, first find the bucket where x is located according to the query operation, then remove the key-value pair from the bucket, and reset the corresponding bit of the bucket where x is located in the bitmap.

The beneficial effects of the present invention are: 1) high loading rate + less pointers: a small memory space is used to store a large number of key-value pairs, and the number of pointers used is small. 2) Low conflict rate. 3) Fast update: Hash table can be updated with few memory accesses. 4) Zero update failed. 5) Fast query: can quickly find key-value pairs with little memory access, or can quickly return non-existent results for key-value pairs that do not exist. 6) Practicality: It is easy to implement in hardware system.

Description of drawings

Figure 1 is a schematic diagram of the algorithm of matrix hashing.

Figure 2 is a structural diagram of a multi-bit Bloom filter.

Detailed ways

The present invention will be further described below through specific embodiments and accompanying drawings.

1. Data structure

The data structure of the "matrix hash" of the present invention comprehensively uses multi-level sub-tables, bloom filters and bitmaps. The data structure consists of two parts, the hash table data structure and the auxiliary data structure.

1. Hash table data structure

The size of each subtable, that is, the maximum number of elements that can be stored, is arithmetically decreasing, so the Bloom filter corresponding to the subtable is also arithmetically decreasing. A relatively simple balancing strategy is used when inserting elements: whenever a new key-value pair is inserted, it is inserted into the sub-table with the smallest load rate, so that the number of elements in each sub-table is guaranteed to be similar to arithmetic It exists in the form of decreasing series.

矩阵哈希将第i个子表和第z-i+1个子表结合，最终得到了

个大小相等的子表。因为结合后的子表形状与矩阵类似，因此我们将这个算法命名为矩阵哈希。为了避免插入失败，允许最后一个子表挂链表。如果待插入键值对最终找不到一个空桶，则可以在第z个子表上挂链表。因为第z个子表是最小的子表，因此指针将会占用最小的内存。Suppose there are z sublists in total, and z is an even number. for

The matrix hash combines the i-th subtable with the z-i+1-th subtable, and finally gets

subtables of equal size. Because the shape of the combined subtable is similar to that of a matrix, we name this algorithm matrix hashing. To avoid insert failures, allow the last child list to be linked. If the key-value pair to be inserted cannot find an empty bucket, a linked list can be attached to the z-th sub-table. Because the z-th subtable is the smallest subtable, the pointer will occupy the smallest memory.

Figure 1 is a schematic diagram of the algorithm of matrix hashing, in which, the left side is 6 sub-tables and 6 bloom filters with equally decreasing size, and the middle is the combined 3 sub-tables and 3 bloom filters of equal size. The upper right is a multi-bit Bloom filter composed of three standard Bloom filters BF1, BF2, BF3.

2. Auxiliary data structure

矩阵哈希将第i个布隆过滤器和第z-i+1个布隆过滤器结合，最终得到了

个大小相等的标准布隆过滤器。接着，通过将这

个布隆过滤器对应比特追加在一起，形成了1个布隆过滤器。在这个布隆过滤器中，每个箱由

个比特组成。我称将这一个布隆过滤器为多比特布隆过滤器，并用F_m表示。到此，我们已经把原z个等差的布隆过滤器组合成1个多比特布隆过滤器。Similar to the hash table combination, for

The matrix hash combines the i-th bloom filter with the z-i+1-th bloom filter, and finally gets

A standard bloom filter of equal size. Then, by putting this

The corresponding bits of each bloom filter are appended together to form a bloom filter. In this bloom filter, each bin consists of

composed of bits. I call this a bloom filter a multi-bit bloom filter and denote it by F _m . So far, we have combined the original z arithmetic bloom filters into a multi-bit bloom filter.

Figure 2 is a structural diagram of a multi-bit Bloom filter. As shown in the figure, the three bits in a bin come from three equal-sized standard bloom filters namely F1, F2, F3. It is worth noting that the combination of bloom filters is done in on-chip memory and is physical, while the combination of sub-tables is only conceptual. The algorithm implementation of the multi-bit bloom filter is as follows:

)。Assume that F1, F2, and F3 all have m bits. For F1, first take the most significant bit (the m bits of F1 are logically ANDed with 2 ^m-1 ), then shift the result to the left by 2*m bits (the resulting m bits are multiplied by 2 ^2m ), and then take the second most significant bit bits (the m bits of F1 are logically ANDed with 2 ^m-2 ), the result is shifted to the left by 2*(m-1) bits (the resulting m bits are multiplied by 2 ^2(m-1) ), the The obtained result is accumulated with the value after the operation of the highest bit, and so on. Similar operations are performed for each bit and accumulated until the last bit, assuming that the accumulated value obtained is f1. Do the same operation on F2 and F3 respectively, and get the accumulated value of f2 and f3. The result of shifting f1 and f2 to the right by one bit and the result of shifting f3 to the right by two bits, these three are logically ORed to obtain a multi-bit Bloom filter (that is,

).

Due to the design of the above bloom filter, there will be a problem: when a bloom filter returns true, we need to query the corresponding two sub-tables. For example, if x is in the i-th Bloom filter, you need to query in the sub-table T _i or T _z-i+1 . In order to reduce the number of sub-tables queried, an additional bloom filter called F _half is added, which is responsible for recording the second part of the sub-table, namely

In addition, matrix hashing also uses bitmaps within the slice. Each subtable has a corresponding bitmap, and each bit in the bitmap corresponds to a bucket in its corresponding subtable. The bit in the bitmap corresponding to an empty bucket is 0, and a non-empty bucket is 1.

2. Derivation of matrix hash false positive rate

个子表。假设F_m有m个箱，每个箱里有

个比特，这

个比特分别对应

个子表。假设F_m有k个子表，

F_m的假阳率和组成它的独立的

个布隆过滤器相等。因此F_m的假阳率如用f(F_m)表示，公式如下：Matrix hashing has two bloom filters: F _m and F _half . Assuming n is the number of key-value pairs, z sub-tables are reorganized into

subtable. Suppose F _m has m bins, each with

bits, this

bits corresponding to

subtable. Suppose F _m has k subtables,

The false positive rate of F _m and the independent

Bloom filters are equal. Therefore, the false positive rate of F _m is expressed as f(F _m ), and the formula is as follows:

If the number of Bloom filters that return true is u+1, then the formula for the false positive rate is:

f(F _m ,u)=0.5 ^k*u *(1-0.5 ^k(zu-1) )

F _half also has k hash functions, and the false positive rate of F _half is: f(F _half )=0.5 ^k . If only F _m returns true, and the key-value pair exists in only one subtable, there are no false positives, and the probability of this event occurring is (1-f(F _m ))*(1-f(F _half )). If only F _m returns true, and the reported key-value pair exists in u+1 sub-tables, there will be u false positives, and the probability of this event is f(F _m ,u)*(1-f(F _half ) ). If only F _half reports a false positive, the probability of this event occurring is (1-f(F _m ))*f(F _half ). If F _m has u false positives and F _half has one false positive, the probability of this event occurring is f(F _m ,u)*f(F _half ).

For example: when z=8 and k=16, the false positive rate of matrix hashing is 1-(1-f(F _m ))*(1-f(F _half ))≈6.1*10 ^-5 , this number is very small.

3. Insert, query and delete key-value pairs

In the key-value storage system, the specific operations of the matrix hash algorithm to insert, query, and delete key-value pairs are as follows:

1. How to insert key-value pairs

则更新F_i来表示x在子表T_i中，更新对应位图；如果子表索引

需将F_z-i+1更新来表示x在子表T_i中，并更新F_half和对应位图。插入过程中，为了将一个箱中与F_i对应的比特置为1，将这个箱中的

个比特与2^i-1做逻辑或操作即可。For a given key-value pair, key x is to be inserted. First check if z candidate buckets are empty by bitmap. The key-value pair is then inserted into the child table with the lowest load ratio to balance all child table load ratios. Suppose the index of the subtable to be inserted is i. if

Then update F _i to indicate that x is in the sub-table T _i , and update the corresponding bitmap; if the sub-table index

It is necessary to update F _{z-i+1 to} indicate that x is in the sub-table Ti, and update F _half and the corresponding bitmap. During insertion, in order to set the bit corresponding to Fi in a _bin to 1, set the

A bit and 2 ^i-1 can be logically ORed.

If the bitmap shows that the z buckets that x should be inserted into are all full, use the kicking mechanism in cuckoo hashing (cuckoo hashing) and use the bitmap to decide which key-value pair to kick. Use the bitmap to check the z candidate buckets corresponding to x in order to determine whether the original element in the candidate bucket, such as y, has an empty bucket to insert y into the remaining z-1 subtables. If there is, kick y out, insert x, and insert y in the new position. If such a y cannot be found, a blind kick is performed, and the above insertion process is repeated. The number of blind kicks is limited to θ. If the number of blind kicks exceeds θ, the key-value pair will be linked to the linked list of the last sub-list. By changing the value of θ, RHT4 can trade off loading rate and insertion speed. Because bitmaps have a global record of empty and non-empty buckets in subtables, the use of on-chip bitmaps significantly reduces the number of kick operations.

2. How to query key-value pairs

返回true，且F_half返回false，则检查子表T_i。否则，先检查子表T_z-i+1，如果没有匹配，再检查子表T_i。如果在z个子表中都无法查找到x，则查找最后一个子表的链表。如果仍然无法找到，则说明x不在该哈希表中。If query x, first query x in F _m and F _half , if

Returns true, and F _half returns false, check the sub-table T _i . Otherwise, the sub-table T _z-i+1 is checked first, and if there is no match, then the sub-table T _i is checked. If x cannot be found in z sublists, look up the linked list of the last sublist. If it still can't be found, then x is not in that hash table.

个布隆过滤器的参数是相同的。如果要读取一个箱中与F_i对应的比特，将这

个比特与2^i-1做逻辑与操作。如果结果为0，则箱中与Fi对应的比特为0，反之为1。It is worth noting that in the query process, only k hash functions need to be calculated, and z × k hash functions do not need to be calculated. This is because: the original composition of a Bloom filter

The parameters of each bloom filter are the same. If you want to read the _bits corresponding to Fi in a bin, put this

The bits are logically ANDed with 2 ^i-1 . If the result is 0, the bit corresponding to Fi in the bin is 0, otherwise it is 1.

3. How to delete key-value pairs

If x is deleted, RHT1 first finds the bucket where x is located according to the above query operation, then removes the key-value pair from the bucket, and resets the corresponding bit of the bucket where x is located in the bitmap.

4. Experimental data

In order to better evaluate the matrix hashing of the present invention as well as existing hashing designs, we use actual application data. We obtained 12 forwarding information bases (FIB, Forward Information Base) of the website www.ripe.net at 8:00 am on 2014.07.08, and for each FIB, a traffic trace ( traffic trace). We use the part of the FIB that is relevant to us, namely the prefix and the associated next hop. The prefix is the key and the next hop is the value. We use β to denote the ratio of the total number of buckets to the total number of elements in the hash table. where 1.05≤β≤10. We denote the threshold for blind kick operations by θ. The number of key-value pairs in the FIB is 500,000. The size difference of the 8 sub-tables established is 5000, and the total size of the sub-tables is β*n. Let θ=0, which means that no blind kicks are allowed, only bitmap kicks are allowed. Each time a key-value pair is inserted, the maximum number of imitations is 8+1. If the element does not find an empty candidate position in the 8 sub-lists, it needs to be inserted into the linked list of the last sub-list. The collision rate is the ratio of the number on the last child list to the total number of elements. Bloom filters have 16 hash functions. The experimental results are as follows:

1. Matrix hash experiment performance:

1) Loading rate and conflict rate

The experimental settings are β=1.05 and θ=0. The experimental results show that the matrix hash can achieve a very high loading rate with only 1.05*n memory. The loading rate of the 8 sub-tables is very balanced, and the total loading rate is 95.19%. . The conflict rate is around 0.05%, with only a few FIBs exceeding 0.06%.

2) Insert and query time

The experiment sets β=1.05 and θ=0, and the experiment inserts all elements of each FIB into the matrix hash. The experimental results show that the more elements inserted, the more memory accesses are required. For most elements, the number of memory accesses required per insert was less than 6, and the number of memory accesses for queries ranged from 1 to 1.0019, with a mean of 1.00059.

3) Bitmap Kicks and Blind Kicks

The experimental setting is β=1.05. The experimental results show that when θ=5, the maximum number of times of inserting a key-value pair into memory is 8*(5+1)+1=49 times, and the number of memory accesses for querying a key-value pair is lower than 8 times, when there is no element in the linked list of the last sublist. When θ=0, even though blind kicks are not allowed, there are only a few elements (0.56%) on the linked list of the last sublist. Worst case memory access at insert time is 8+1 times.

4) Conflict rate vs β

The experimental set θ=0, the experimental results show that the larger the β, the smaller the conflict rate, and when β≥1.18, the conflict rate is close to 0.

2. Comparison of matrix hashes with other hashes:

The experiment compares matrix hashing with six well-known hashing designs: chained hashing, linear probing, double hashing, cuckoo hashing, d-left hashing, and peacock bird hashing. First define the insertion failure. For linear detection, double hash and cuckoo hash, when a collision occurs, another bucket is detected, and this detection is repeated all the time. We limit the number of repeated detections to less than 500, which means that for these three hash designs, the maximum number of memory accesses per insertion is 500. If there are still collisions after more than 500 times, the three hash designs It will give up and continue to insert, and discard the elements that have not been inserted in the 500th cycle, which will cause the insertion to fail. For peacock bird hashing and matrix hashing, the Bloom filter has 16 hash functions.

Experiment 1: (β=1.05, different FIBs)

1) Loading rate

The experimental results show that the loading rate of matrix hashing has always been the highest.

2) Insert time

The experimental results show that matrix hashing requires the least number of replicas to insert among all hashes except chain hashing. This is because chained hashing requires only one or two fetches when inserting, so the fetching time is shorter, but chained hashing has very prominent shortcomings in other aspects. The matrix hash, due to the existence of Bloom filters and bitmaps, can achieve fast insertion.

3) Find time

The experimental results show that matrix hashing has the shortest search time, because matrix hashing has a high loading rate and a small false positive rate.

Experiment 2 (different beta, FIB rrc00)

1) Loading rate

The experimental results show that the loading rate of matrix hashing is always the highest, the loading rate of chain hashing and double hashing is similar, and the loading rate of peacock bird hashing can only reach a higher loading rate when β is relatively high.

2) Insert time

The experimental results show that matrix hashing requires the least number of replicas to insert among all hashes except chain hashing.

3) Find time

The experimental results show that the matrix hash has the shortest search time.

The above embodiments are only used to illustrate the technical solutions of the present invention and not to limit them. Those skilled in the art can modify or equivalently replace the technical solutions of the present invention without departing from the spirit and scope of the present invention. The scope of protection shall be subject to what is stated in the claims.

Claims (3)

1. A data storage method based on matrix hash is characterized by comprising the following steps:

1) establishing a hash table data structure which comprises z sub-tables, wherein z is an even number, and the size equal difference of each sub-table is decreased progressively; for the

Combining the ith sub-table with the z-i +1 th sub-table to obtain

Sub-tables with equal size; each sub-table in the z sub-tables corresponds to a bitmap, and each bit in the bitmap corresponds to a bucket in the corresponding sub-table; the bit in the bitmap corresponding to the empty bucket is 0, and the bit in the bitmap corresponding to the non-empty bucket is 1;

2) establishing an auxiliary data structure which comprises z bloom filters corresponding to the z sub-tables, wherein the size arithmetic of each bloom filter is decreased; for the

Combining the ith bloom filter with the z-i +1 th bloom filter to obtain

A bloom filter of equal size; then the product is mixed with

Corresponding bits of the plural bloom filters are added together to form 1 plural-bit bloom filter F_m(ii) a Adding an additional bloom filter F_halfResponsible for recording the second in the z sub-tables

Individual watch

To the z th sub-table T_zI.e. by

To reduce the number of sub-tables queried;

the multi-bit bloom filter F_mThe implementation mode of (2) is as follows:

assume that the standard bloom filters F1, F2, F3 all have m bits; for F1, firstly taking the most significant bit, then moving the obtained result to the left by 2 x m bits, then taking the next most significant bit, moving the obtained result to the left by 2 x (m-1) bits, accumulating the obtained result and the value after the operation of the most significant bit, and so on, performing similar operation on each bit, and accumulating until the last bit, and assuming that the obtained accumulated value is F1; respectively carrying out the same operation on F2 and F3 to obtain accumulated values F2 and F3; performing logic or operation on the result obtained after the f1 and the f2 are shifted to the right by one bit and the result obtained after the f3 is shifted to the right by two bits to obtain a multi-bit bloom filter;

3) inserting key value pairs by using the hash table data structure and the auxiliary data structure to realize data storage;

wherein, step 3) includes:

inserting a new key value pair into the sub-table with the minimum loading rate in the z sub-tables every time the key value pair is inserted;

hanging a linked list on the last sub-table, namely the z-th sub-table, in the z sub-tables;

the key-value pairs are inserted as follows:

a) for a given key-value pair, checking whether z candidate buckets are empty through a bitmap, and then inserting the key-value pair into a sub-table with the lowest loading rate to balance the loading rates of all the sub-tables; suppose the sub-table index to be inserted is i, if

Updating the ith bloom filter F of the z bloom filters_iTo indicate the i-th sub-table T of the z sub-tables of the key-value pair_iUpdating the corresponding bitmap; if it is not

Then the z-i +1 th of the z bloom filters F is updated_z-i+1To indicate the i-th sub-table T of the z sub-tables of the key-value pair_iAnd update F_halfAnd a corresponding bitmap;

b) if the bitmap shows that z buckets into which the key x should be inserted are full, the insertion of the key-value pair is realized by using a kick mechanism;

wherein, the implementation mode of the step b) is as follows: using the bitmap to sequentially check z candidate buckets corresponding to x to determine whether an original element y in the candidate buckets has an empty bucket in the remaining z-1 subtables into which y can be inserted; if yes, kicking out y, inserting x, and inserting y into a new position; and if y cannot be found, executing blind kicking, repeating the above insertion process, limiting the number of times of blind kicking to theta, and if the number of times of blind kicking exceeds theta, hanging the key value pair on the linked list of the last sub-table.

2. The method of claim 1, in which key-value pairsThe query mode is as follows: when looking up the key x, first in the multi-bit bloom filter F_mAnd F_halfMiddle query key x, for

If Fi returns true, and F_halfReturning false, the ith sub-table T in the z sub-tables is checked_i(ii) a Otherwise, checking the z-i +1 th sub-table T in the z sub-tables_z-i+1If there is no match, then check the ith sub-table T of the z sub-tables_i(ii) a If the key x cannot be found in the z sub-tables, searching a linked list of the last sub-table; if it is still not found, it indicates that key x is not in the hash table.

3. The method of claim 1, wherein key-value pairs are deleted by: when deleting the key x, firstly finding the bucket where the key x is located according to the query operation, then removing the key value pair from the bucket, and resetting the corresponding bit of the bucket where the key x is located in the bitmap.

Images