Method and device for managing hash table, and computer program product

1. A method of managing a hash table, comprising:

in response to receiving a write request, determining whether a first hash value associated with the write request is stored in a set of hash tables, the set of hash tables including at least a first hash table and a second hash table, the first hash table being a currently valid hash table for a first storage device, the second hash table being stored in a second storage device, an access speed of the first storage device being faster than that of the second storage device;

in response to determining that the first hash value is not stored in the set of hash tables and the first hash table is full, setting a pre-allocated third hash table in the first storage device as the currently valid hash table for the first storage device;

writing a first entry into the third hash table, the first entry including the first hash value; and

merging entries in the first hash table with entries in the second hash table for storage into the second storage device.

2. The method according to claim 1 , wherein the merging entries in the first hash table with entries in the second hash table comprises:

determining whether a sum of a number of entries in the first hash table and a number of entries in the second hash table reaches a predetermined threshold; and

in response to the sum being smaller than the predetermined threshold, writing the entries in the first hash table and the entries in the second hash table into the second hash table in a descending order of the hash values.

3. The method according to claim 2 , further comprising:

in response to the sum reaching the predetermined threshold, writing the entries in the first hash table and the entries in the second hash table into a pre-allocated fourth hash table in a descending order of the hash values.

4. The method according to claim 3 , further comprising:

removing the first hash table from the first storage device.

5. The method according to claim 1 , further comprising:

in response to receiving a delete request, determining whether the third hash table is full; and

in response to determining that the third hash table is not full, writing a second entry into the third hash table, the second entry including a second hash value associated with the delete request; and

marking the second entry in the third hash table to indicate that the second hash value is to be deleted.

6. The method according to claim 5 , wherein the merging entries in the first hash table with entries in the second hash table comprises:

determining whether an unmarked third entry exists in the first hash table and the second hash table, the third entry including the second hash value; and

in response to the third entry existing in the third hash table or the second hash table, deleting the second entry and the third entry from the first hash table or the second hash table.

7. The method according to claim 1 , wherein the determining whether a first hash value is stored in a set of hash tables comprises:

determining whether the first hash value is stored in the first hash table;

in response to the first hash value being not stored in the first hash table, mapping the first hash value to a plurality of bits with a bloom filter, the bloom filter being associated with the second hash table; and

in response to determining that a zero bit exists in the plurality of bits, determining that the first hash value is not stored in the second hash table.

8. The method according to claim 7 , further comprising:

in response to determining that there is no zero bit in the plurality of bits, determining a page in the second hash table associated with the first hash value based on a page index, the page index being stored in the first storage device; and

querying for the first hash value from the page.

9. The method according to claim 7 , wherein the bloom filter is stored in the first storage device.

10. The method according to claim 1 , wherein before determining whether the first hash value is stored in the set of hash tables, the method further comprises:

determining, based on the first hash value, the set of hash tables associated with the first hash table from a plurality of sets of hash tables.

11. An apparatus for managing a hash table, comprising:

at least one processing unit;

at least one memory, the at least one memory is coupled to the at least one processing unit and stores instructions to be executed by the at least one processing unit, the instructions, when executed by the at least one processing unit, causing the apparatus to perform acts, the acts including:

in response to receiving a write request, determining whether a first hash value associated with the write request is stored in a set of hash tables, the set of hash tables including at least a first hash table and a second hash table, the first hash table being a currently valid hash table for a first storage device, the second hash table being stored in a second storage device, an access speed of the first storage device being faster than that of the second storage device,

in response to determining that the first hash value is not stored in the set of hash tables and the first hash table is full, setting a pre-allocated third hash table in the first storage device as the currently valid hash table for the first storage device,

writing a first entry into the third hash table, the first entry including the first hash value, and

merging entries in the first hash table with entries in the second hash table for storage into the second storage device.

12. The apparatus according to claim 11 , wherein the merging entries in the first hash table with entries in the second hash table comprises:

determining whether a sum of a number of entries in the first hash table and a number of entries in the second hash table reaches a predetermined threshold; and

in response to the sum being smaller than the predetermined threshold, writing the entries in the first hash table and the entries in the second hash table into the second hash table in a descending order of the hash values.

13. The apparatus according to claim 12 , the acts further comprising:

in response to the sum reaching the predetermined threshold, writing the entries in the first hash table and the entries in the second hash table into a pre-allocated fourth hash table in a descending order of the hash values.

14. The apparatus according to claim 13 , the acts further comprising:

removing the first hash table from the first storage device.

15. The apparatus according to claim 11 , the acts further comprising:

in response to receiving a delete request, determining whether the third hash table is full; and

in response to determining that the third hash table is not full, writing a second entry into the third hash table, the second entry including a second hash value associated with the delete request; and

marking the second entry in the third hash table to indicate that the second hash value is to be deleted.

16. The apparatus according to claim 15 , wherein the merging entries in the first hash table with entries in the second hash table comprises:

determining whether an unmarked third entry exists in the first hash table and the second hash table, the third entry including the second hash value; and

in response to the third entry existing in the third hash table or the second hash table, deleting the second entry and the third entry from the first hash table or the second hash table.

17. The apparatus according to claim 11 , wherein the determining whether a first hash value is stored in a set of hash tables comprises:

determining whether the first hash value is stored in the first hash table;

in response to the first hash value being not stored in the first hash table, mapping the first hash value to a plurality of bits with a bloom filter, the bloom filter being associated with the second hash table; and

in response to determining that a zero bit exists in the plurality of bits, determining that the first hash value is not stored in the second hash table.

18. The apparatus according to claim 17 , the acts further comprising:

in response to determining that there is no zero bit in the plurality of bits, determining a page in the second hash table associated with the first hash value based on a page index, the page index being stored in the first storage device; and

querying for the first hash value from the page.

19. The apparatus according to claim 17 , wherein the bloom filter is stored in the first storage device.

20. The apparatus according to claim 11 , wherein before determining whether the first hash value is stored in the set of hash tables, the acts further comprise:

determining, based on the first hash value, the set of hash tables associated with the first hash table from a plurality of set of hash tables.

21. A computer program product having a non-transitory computer readable medium which stores a set of instructions for managing a hash table; the set of instructions, when carried out by computerized circuitry, causing the computerized circuitry to perform a method of:

in response to receiving a write request, determining whether a first hash value associated with the write request is stored in a set of hash tables, the set of hash tables including at least a first hash table and a second hash table, the first hash table being a currently valid hash table for a first storage device, the second hash table being stored in a second storage device, an access speed of the first storage device being faster than that of the second storage device;

in response to determining that the first hash value is not stored in the set of hash tables and the first hash table is full, setting a pre-allocated third hash table in the first storage device as the currently valid hash table for the first storage device;

writing a first entry into the third hash table, the first entry including the first hash value; and

merging entries in the first hash table with entries in the second hash table for storage into the second storage device.