REAL-TIME HASH MAP

• US 20120054467A1
• Filed: 09/01/2010
• Published: 03/01/2012
• Est. Priority Date: 09/01/2010
• Status: Active Grant

• Current Assignee: AirBNB Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Fulton, Michael S., Stoodley, Mark G.
• Granted Patent: US 8,423,594 B2
• Time in Patent Office: Days
• US Class Current: 711/216
• CPC Class Codes: G06F 16/9014 hash tables

Abstract

A method for implementing a hash map to improve performance consistency is disclosed herein. In one embodiment, such a method includes providing a hash map comprising a set of tables, the set of tables initially containing a first table. When the first table is full, the method augments the hash map by adding a second table to the set of tables. Similarly, when the second table is full, the method augments the hash map by adding a third table to the set of tables. A similar technique may be used to add additional tables to the hash map. When searching for a value in any of the tables in the hash map, the method uses the same hash code. A corresponding computer program product and apparatus are also disclosed herein.

Claims

1. A method for implementing a hash map to improve performance consistency, the method comprising:

providing a hash map comprising a set of tables, the set of tables comprising a first table;

when the first table is full, augmenting the hash map by adding a second table to the set of tables;

when the second table is full, augmenting the hash map by adding a third table to the set of tables; and

using the same hash code to search for a value in any of the tables belonging to the set of tables.

2. The method of claim 1, wherein the third table is larger than the second table and the second table is larger than the first table.

3. The method of claim 2, wherein the first table contains 2ⁿ array elements, the second table contains 2ⁿ⁺¹ array elements, and the third table contains 2ⁿ⁺² array elements.

4. The method of claim 3, wherein searching for the value comprises searching through the set of tables from the most recently added table to the least recently added table until the value is found.

5. The method of claim 1, further comprising migrating an entry to the most recently added table in the event at least one of a “

get” and

“

put”

operation is performed on the entry, and the entry is not already in the most recently added table.

6. The method of claim 1, further comprising maintaining a count value for an entry and incrementing the count value each time one of a “

get” and

“

put”

operation is performed on the entry.

7. The method of claim 6, further comprising migrating the entry to the most recently added table if the count value reaches a designated threshold, and the entry is not already in the most recently added table.

8. The method of claim 1, wherein searching for the value comprises searching through the set of tables from the largest table to the smallest table until the value is found.

9. A computer program product to implement a real-time hash map, the computer program product comprising a computer-usable storage medium having computer-usable program code embodied therein, the computer-usable program code comprising:

computer-usable program code to provide a hash map comprising a set of tables, the set of tables comprising a first table;

computer-usable program code to, upon detecting that the first table is full, augment the hash map by adding a second table to the set of tables;

computer-usable program code to, upon detecting that the second table is full, augment the hash map by adding a third table to the set of tables; and

computer-usable program code to use the same hash code to search for a value in any of the tables belonging to the set of tables.

10. The computer program product of claim 9, wherein the third table is larger than the second table and the second table is larger than the first table.

11. The computer program product of claim 10, wherein the first table contains 2ⁿ array elements, the second table contains 2ⁿ⁺¹ array elements, and the third table contains 2ⁿ⁺² array elements.

12. The computer program product of claim 11, wherein searching for the value comprises searching through the set of tables from the most recently added table to the least recently added table until the value is found.

13. The computer program product of claim 9, further comprising computer-usable program code to migrate an entry to the most recently added table in the event at least one of a “

get” and

“

put”

operation is performed on the entry, and the entry is not already in the most recently added table.

14. The computer program product of claim 9, further comprising computer-usable program code to maintain a count value for an entry and increment the count value each time one of a “

get” and

“

put”

operation is performed on the entry.

15. The computer program product of claim 14, further comprising computer-usable program code to migrate the entry to the most recently added table if the count value reaches a designated threshold, and the entry is not already in the most recently added table.

16. The computer program product of claim 9, wherein the set of tables includes a master table containing pointers to tables within the set of tables.

17. An apparatus to implement a hash map to improve performance consistency, the apparatus comprising:

an establishment module to establish a hash map comprising a set of tables, the set of tables comprising a first table;

an augment module to, upon detecting that the first table is full, augment the hash map by adding a second table to the set of tables;

the augment module further configured to, upon detecting that the second table is full, augment the hash map by adding a third table to the set of tables; and

a search module to use the same hash code to search for a value in any of the tables belonging to the set of tables.

18. The apparatus of claim 17, wherein the third table is larger than the second table and the second table is larger than the first table.

19. The apparatus of claim 18, wherein the first table contains 2ⁿ array elements, the second table contains 2ⁿ⁺¹ array elements, and the third table contains 2ⁿ⁺² array elements.

20. The apparatus of claim 19, wherein the search module is further configured to search through the set of tables from the most recently added table to the least recently added table until the value is found.

21. The apparatus of claim 17, further comprising a migrate module to migrate an entry to the most recently added table in the event at least one of a “

get” and

“

put”

operation is performed on the entry, and the entry is not already in the most recently added table.

22. The apparatus of claim 17, further comprising a count module to maintain a count value for an entry and increment the count value each time one of a “

get” and

“

put”

operation is performed on the entry.

23. The apparatus of claim 22, further comprising a migrate module to migrate the entry to the most recently added table if the count value reaches a designated threshold, and the entry is not already in the most recently added table.

24. The apparatus of claim 17, wherein the search module references a master table containing pointers to tables within the set.

25. A method for implementing a hash map to improve performance consistency, the method comprising:

providing a hash map comprising a set of tables, the set of tables comprising a first table having 2ⁿ array elements;

when the first table is full, augmenting the hash map by adding a second table having 2ⁿ⁺¹ array elements to the set of tables;

when the second table is full, augmenting the hash map by adding a third table having 2ⁿ⁺² array elements to the set of tables; and

using the same hash code to search for a value in any of the tables belonging to the set of tables.