Equipment and method for hash table resizing
A method for optimizing hash table lookup speed during hash table resize on a computing device, the method including performing the following on the computing device: providing a first hash table having N slots for entries, designating the first hash table as an active hash table, allocating a second hash table, and performing the following after allocating the second hash table: when a hash table insertion of an entry is requested, performing insertion by inserting the entry to the first hash table and inserting the entry to the second hash table, and when a hash table lookup is requested, looking up the requested entry in the active hash table, one of the performing insertion and the performing deletion including also copying K entries, K being greater than or equal to 1, from the first hash table to the second hash table. Related apparatus and methods are also described.
1. A method for optimizing hash table lookup speed during hash table resize on a computing device, the method comprising performing the following on the computing device:
providing a first hash table having N slots for entries;
designating the first hash table as an active hash table;
allocating a second hash table; and
performing the following after allocating the second hash table:
when a hash table insertion of an entry is requested, performing insertion by: inserting the entry to the first hash table and inserting the entry to the second hash table; and
when a hash table lookup is requested, looking up the requested entry in the active hash table,
wherein the performing insertion comprises: also copying K entries, K being greater than or equal to 1, from the first hash table to the second hash table,
the method also comprising providing an enlargement ratio e and a threshold occupancy level of slots for the first hash table, the threshold occupancy level being equal to N multiplied by the enlargement ratio e,
wherein the second hash table is allocated in response to a present occupancy level of the first hash table exceeding the threshold occupancy level, and the second hash table has more than N slots for entries.
2. The method according to claim 1 and wherein the performing the following after allocating the second hash table also comprises:
when a hash table deletion of an entry is requested, performing deletion by: deleting the entry from the first hash table and deleting the entry from the second hash table, and also copying K entries, K being greater than or equal to 1, from the first hash table to the second hash table.
3. The method according to claim 1 and wherein the second hash table has at least 2N+1 slots for entries.
4. The method according to claim 1 and wherein the second hash table has
1
+
1
e
*
N
entries.
5. The method according to claim 1 and wherein said performing the following after allocating the second hash table further comprises:
when a number of entries in the first hash table and a number of entries in the second hash table are equal, designating the second hash table as the active hash table and ceasing to designate the first hash table as the active hash table.
6. The method according to claim 5 and further comprising:
after said designating the second hash table as the active hash table, deallocating the first hash table.
7. A computing device comprising:
a processing unit; and
memory for storing a first hash table having N slots for entries,
the processing unit being configured for:
designating the first hash table as an active hash table;
allocating a second hash table; and
performing the following after allocating the second hash table:
when a hash table insertion of an entry is requested, performing insertion by: inserting the entry to the first hash table and inserting the entry to the second hash table; and
when a hash table lookup is requested, looking up the requested entry in the active hash table,
wherein the performing insertion comprises: also copying K entries, K being greater than or equal to 1, from the first hash table to the second hash table,
wherein the processing unit is also configured for:
providing a threshold occupancy level of slots for the first hash table and an enlargement ratio e, the threshold occupancy level being equal to N multiplied by the enlargement ratio e, and
the second hash table is allocated in response to a present occupancy level of the first hash table exceeding the threshold occupancy level, and the second hash table has more than N slots for entries.
8. The computing device according to claim 7 and wherein the performing the following after allocating the second hash table also comprises:
when a hash table deletion of an entry is requested, performing deletion by: deleting the entry from the first hash table and deleting the entry from the second hash table, and copying K entries, K being greater than or equal to 1, from the first hash table to the second hash table.
9. The computing device according to claim 7 and wherein the second hash table has at least 2N+1 slots for entries.
10. The computing device according to claim 7 and wherein the second hash table has
1
+
1
e
*
N
entries.
11. The computing device according to claim 7 and wherein said performing the following after allocating the second hash table further comprises:
when a number of entries in the first hash table and a number of entries in the second hash table are equal, designating the second hash table as the active hash table and ceasing to designate the first hash table as the active hash table.
12. The computing device according to claim 11 and wherein said performing the following after allocating the second hash table further comprises:
after said designating the second hash table as the active hash table, deallocating the first hash table.
13. A computing device comprising:
a processing unit; and
memory for storing a first hash table having N slots for entries,
the processing unit being configured for:
designating the first hash table as an active hash table;
providing a threshold occupancy level of slots for the first hash table and a diminution ratio d, the threshold occupancy level being equal to N multiplied by the diminution ratio d;
allocating a second hash table in response to a present occupancy level of the first hash table reaching a level less than the threshold occupancy level, the second hash table having fewer than N slots for entries; and
performing the following after allocating the second hash table:
when a hash table insertion of an entry is requested, performing insertion by: inserting the entry to the first hash table and inserting the entry to the second hash table; and
when a hash table lookup is requested, looking up the requested entry in the active hash table,
wherein the performing insertion comprises: also copying K entries, K being greater than or equal to 1, from the first hash table to the second hash table.
14. The computing device according to claim 13 and wherein the second hash table has
entries.
15. The computing device according to claim 13 and wherein the performing the following after allocating the second hash table also comprises:
when a hash table deletion of an entry is requested, performing deletion by: deleting the entry from the first hash table and deleting the entry from the second hash table, and copying K entries, K being greater than or equal to 1, from the first hash table to the second hash table.
16. The computing device according to claim 13 and wherein said performing the following after allocating the second hash table further comprises:
when a number of entries in the first hash table and a number of entries in the second hash table are equal, designating the second hash table as the active hash table and ceasing to designate the first hash table as the active hash table.
17. The computing device according to claim 16 and wherein said performing the following after allocating the second hash table further comprises:
after said designating the second hash table as the active hash table, deallocating the first hash table.