Method and system for dynamically managing hash pool data structures

• US 6,748,401 B2
• Filed: 10/11/2001
• Issued: 06/08/2004
• Est. Priority Date: 10/11/2001
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Blackburn, Robert A., Dryfoos, Robert O., Sears, Glenn W. Jr., Fisher, Gary A. Sr.
• Primary Examiner(s): Metjahic, Safet
• Assistant Examiner(s): AL HASHEMI, SANA A
• Application Number:
  US09/974,977
• Publication Number:
  US 20030074341A1
• Time in Patent Office: 971 Days
• Field of Search: 707/104.1, 707/102, 707/100, 707/103.Y, 707/3
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

An exemplary embodiment of the present invention is a method for dynamically managing a hash pool data structure. A request to insert a new key value into a hash pool data structure that includes at least one index level is received. An insertion location is calculated for the new key value in response to the new key value and to existing key values in the hash pool data structure. The insertion location includes an index level. A new index level is added at the insertion location if the index level is not the maximum number of index levels in the hash pool data structure; if the insertion location contains a chain of existing key values with a length equal to the maximum chain length; and if the new index record locations of the new key value and the existing key values are dispersed. The insertion location is updated in response to adding a new index record and the new key value is inserted into the insertion location. An additional embodiment includes a system and storage medium for dynamically managing a hash pool data structure.

Claims

1. A method for dynamically managing a hash pool data structure, said method comprising:

receiving a request to insert a new key value into a hash pool data structure, said hash pool data structure including at least one index level;

calculating an insertion location for said new key value in said hash pool data structure in response to said new key value and existing key values, wherein said insertion location includes an index level;

adding a new index record at said insertion location if;

said index level is not equal to a preselected maximum number of index levels;

said insertion location contains a chain of said existing key values with a length equal to a maximum chain length; and

new index record locations of said new key value and said existing key values are dispersed;

updating said insertion location in response to said adding a new index record; and

inserting said new key value into said insertion location.

2. The method of claim 1 wherein said new index record locations of said new key value and said existing key values are dispersed if less than a selected number of duplicate insertion locations would result if said new key value and said existing key values were inserted into said new index record.

3. The method of claim 1 wherein said preselected maximum number of index levels is equal to two.

4. The method of claim 1 further comprising:

adding a new contention record at said insertion location in response to not performing said adding a new index record and if said insertion location contains a chain of said existing key values with a length equal to said maximum chain length; and

updating said insertion location in response to said adding a new contention record.

5. The method of claim 1 wherein said maximum chain length is equal to three.

6. The method of claim 1 wherein said calculating an insertion location for said new key value comprises:

executing a hash function in response to said new key value, wherein said output of said hash function includes an ordinal value;

executing an index location function in response to said ordinal value, wherein said output of said index location function includes an index record address and index off-set data; and

retrieving and analyzing said existing key values in response to said index record address, said index off-set data, and said new key value wherein said output of said analyzing is said insertion location for said new key value.

7. The method of claim 1 wherein said hash pool data structure includes index records, contention records, user data records, chained contention records, and chained user data records.

8. The method of claim 1 wherein said adding a new index record comprises:

allocating a new index record;

updating said insertion location with said address of new index record; and

updating said new index record with said existing key values in said chain.

9. The method of claim 4 wherein said adding a new contention record comprises:

allocating a new contention record;

updating said insertion location with said address of new contention record; and

updating said new contention record with said existing key values in said chain.

10. The method of claim 1 further comprising:

receiving a request to insert new user data, wherein said new user data corresponds to said new key value; and

allocating a new user data record in response to said request; and

storing said new user data record address at said insertion location.

11. A storage medium encoded with machine-readable computer code for dynamically managing a hash pool data structure, the storage medium storing instructions for causing a computer to implement the method comprising:

receiving a request to insert a new key value into a hash pool data structure, said hash pool data structure including at least one index level;

calculating an insertion location for said new key value in said hash pool data structure in response to said new key value and existing key values, wherein said insertion location includes an index level;

adding a new index record at said insertion location if;

said index level is not equal to a preselected maximum number of index levels;

said insertion location contains a chain of said existing key values with a length equal to a maximum chain length; and

new index record locations of said new key value and said existing key values are dispersed;

updating said insertion location in response to said adding a new index record; and

inserting said new key value into said insertion location.

12. The storage medium of claim 11 wherein said new index record locations of said new key value and said existing key values are dispersed if less than a selected number of duplicate insertion locations would result if said new key value and said existing key values were inserted into said new index record.

13. The storage medium of claim 11 wherein said preselected maximum number of index levels is equal to two.

14. The storage medium of claim 11 further comprising instructions for causing the computer to implement:

adding a new contention record at said insertion location in response to not performing said adding a new index record and if said insertion location contains a chain of said existing key values with a length equal to said maximum chain length; and

updating said insertion location in response to said adding a new contention record.

15. The storage medium of claim 11 wherein said maximum chain length is equal to three.

16. The storage medium of claim 11 wherein said calculating an insertion location for said new key value comprises:

executing a hash function in response to said new key value, wherein said output of said hash function includes an ordinal value;

executing an index location function in response to said ordinal value, wherein said output of said index location function includes an index record address and index off-set data; and

retrieving and analyzing said existing key values in response to said index record address, said index off-set data, and said new key value wherein said output of said analyzing is said insertion location for said new key value.

17. The storage medium of claim 11 wherein said hash pool data structure includes index records, contention records, user data records, chained contention records, and chained user data records.

18. The storage medium of claim 11 wherein said adding a new index record comprises:

allocating a new index record;

updating said insertion location with said address of new index record; and

updating said new index record with said existing key values in said chain.

19. The storage medium of claim 14 wherein said adding a new contention record comprises:

allocating a new contention record;

updating said insertion location with said address of new contention record; and

updating said new contention record with said existing key values in said chain.

20. The storage medium of claim 11 further comprising instructions for causing the computer to implement:

receiving a request to insert new user data, wherein said new user data corresponds to said new key value; and

allocating a new user data record in response to said request; and

storing said new user data record address at said insertion location.