Real-time hash map

• US 8,423,594 B2
• Filed: 09/01/2010
• Issued: 04/16/2013
• Est. Priority Date: 09/01/2010
• Status: Expired due to Fees

• Current Assignee: AirBNB Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Stoodley, Mark Graham, Fulton, Michael Stephen
• Primary Examiner(s): Chbouki, Tarek
• Application Number:
  US12/874,136
• Publication Number:
  US 20120054467A1
• Time in Patent Office: 958 Days
• Field of Search: None
• US Class Current: 707/902
• 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, by a processor, 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, wherein the second table is larger than the first table;

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

using the same hash code to search for a value in any of the tables belonging to the set of tables, 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.

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

3. 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.

4. 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.

5. The method of claim 4, 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.

6. 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.

7. A computer program product to implement a real-time hash map, the computer program product comprising:

a computer-readable 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, wherein the second table is larger than the first table;

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, wherein the third table is larger than the second table; 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, 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.

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

9. The computer program product of claim 7, 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.

10. The computer program product of claim 7, 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.

11. The computer program product of claim 10, 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.

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

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

a plurality of modules, each module implemented in at least one of hardware and software operating hardware, the plurality of modules 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, wherein the second table is larger than the first table;

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, wherein the third table is larger than the second table; 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, 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.

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

15. The apparatus of claim 13, 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.

16. The apparatus of claim 13, 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.

17. The apparatus of claim 16, 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.

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

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

providing, by a processor, 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, 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.