System method and computer program product for dynamically sizing hash tables

• US 5,960,434 A
• Filed: 09/26/1997
• Issued: 09/28/1999
• Est. Priority Date: 09/26/1997
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Schimmel, Curt F.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Coby, Frantz
• Application Number:
  US08/938,672
• Time in Patent Office: 732 Days
• Field of Search: 707/100, 707/101, 707/102, 707/103
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

The present invention is a system, method, and computer program product for dynamically sizing a hash table when the average number of records per bucket in the hash table exceeds a maximum average number of records per bucket. In one embodiment, the hash table employs a modulo hashing function. In a second embodiment, the number of buckets is grown by a multiple of the previous number of buckets and records are re-hashed using a lazy re-hashing modulo algorithm that re-hashes records in a hash bucket only when those records are searched. In the second embodiment, when a hash table is re-sized, each new bucket is provided with a logical back pointer, or index, to a pre-existing bucket that potentially contains records that belong in the new bucket. When a search is directed at a new bucket, the logical back pointer, or index, directs the search to a pre-existing bucket. When a search of a pre-existing bucket finds a data record that belongs in a new bucket, the record is moved to the new bucket. When there are no more records in a pre-existing bucket that belong in a new bucket, the logical back pointer from the new bucket to the pre-existing bucket is removed. Preferably, the logical back pointer is stored in the bucket where a regular pointer would normally be stored so that no extra space is needed.

Claims

1. A method for dynamically sizing a hash table in a processor, comprising the steps of:

(1) allocating a hash table having a number n of hash buckets;

(2) hashing records into the hash table;

(3) re-sizing the hash table when an actual number of records in the hash table exceeds a limit; and

(4) re-hashing the records in the hash table after the hash table is re-sized using a lazy re-hashinz algorithm wherein a logical pointer is associated with a new hash bucket and the logical pointer points to a pre-existing hash bucket that potentially contains records that belong in the new hash bucket.

2. The method according to claim 1, wherein step (2) comprises:

(a) hashing the records using a modulo hashing function.

3. The method according to claim 1, wherein step (3) comprises:

(a) increasing the number of hash buckets by a multiple of a preexisting number of hash buckets.

4. The method according to claim 1, wherein step (4) comprises:

(i) searching the new hash bucket for a record;

(ii) using the logical pointer associated with the new hash bucket to identify the pre-existing hash bucket;

(iii) searching the pre-existing bucket for the record; and

(iv) re-hashing records that are searched in the pre-existing bucket and that belong in the new bucket.

5. The method according to claim 4 wherein step (4) comprises storing the logical pointer within the new hash bucket in place of a regular pointer to a record.

6. The method according to claim 5, wherein step (4) further comprises the step of:

(v) moving the logical pointer to a record that has been re-hashed to the new hash bucket and placing a regular pointer to the record that has been re-hashed in the new hash bucket.

7. The method of claim 4, wherein step (4) further comprises the step of:

removing the logical pointer when there are no more records in the existing bucket that belong in the new bucket.

22. The method according to claim 1, wherein step (4) comprises:

(a) re-sizing the hash table when the actual number of records in the hash table, divided by the number of buckets n, exceeds a limit of a maximum average number of records per hash bucket.

8. A system for dynamically sizing a hash table of records in a processor, comprising:

a hashing function that generates a hash table having a number of buckets n and that hashes records into the buckets based on a key value associated with each record;

a re-sizing module that dynamically re-sizes the hash table when an actual number of records in the hash table exceeds a limit; and

a lazy re-hashing function that re-hashes the records using a lazy re-hashing algorithm, wherein a logical pointer is associated with a new hash bucket and the logical pointer points to a pre-existing hash bucket that potentially contains records that belong in the new hash bucket.

9. The system according to claim 8, wherein said hashing function comprises a modulo hashing function.

10. The system according to claim 9, wherein said re-sizing module comprises:

means for increasing the number of hash buckets by a multiple of a preexisting number of hash buckets.

11. The system according to claim 10, further comprising:

means for using the logical pointer in the new hash bucket to identify and search the pre-existing hash bucket when the new hash bucket is searched for a record; and

means for using the logical pointer in the new hash bucket to flag said lazy re-hashing function to re-hash a record in the pre-existing hash bucket that is searched and that belongs in the new bucket.

12. The system according to claim 11, further comprising:

means for storing the logical pointer in the new hash bucket in place of a regular pointer to a record.

13. The system according to claim 12, further comprising:

means for moving the logical pointer to a record that has been re-hashed to the new hash bucket and for placing a regular pointer to the record that has been re-hashed in the new hash bucket.

14. The method of claim 13, further comprising:

means for removing the logical pointer when there are no more records in the pre-existing bucket that belong in the new bucket.

23. The system according to claim 8, wherein said re-sizing module dynamically re-sizes the hash table when the actual number of records in the hash table, divided by the number of buckets n, exceeds a limit of a maximum average number of records per hash bucket.

15. A computer program product comprising a computer useable medium having computer program logic stored therein, said computer program logic for enabling a computer to dynamically re-size a hash table, wherein said computer program logic comprises:

means for enabling the computer to allocate a hash table having a number n of hash buckets;

means for enabling the computer to hash records into the hash table;

means for enabling the computer to re-size the hash table when an actual number of records in the hash table exceeds a limit; and

means for enabling the computer to re-hash the records in the hash table after the hash table is re-sized using a lazv re-hashing algorithm, wherein a logical pointer is associated with a new hash bucket and the logical pointer points to a pre-existing hash bucket that potentially contains records that belong in the new hash bucket.

16. The computer program product according to claim 15, wherein said means for enabling the computer to hash records into the hash table comprises:

means for enabling the computer to hash the records using a modulo hashing function.

17. The computer program product according to claim 16, wherein said means for enabling the computer to re-size the hash table comprises:

means for enabling the computer to increase the number of hash buckets by a multiple of a pre-existing number of hash buckets.

18. The computer program product according to claim 17, wherein said means for enabling the computer to re-hash the records in the hash table after the hash table is re-sized using a lazv re-hashing algorithm comprises:

means for enabling the computer to search the new hash bucket for a record;

means for enabling the computer to use the logical pointer associated with the new hash bucket to identify the pre-existing hash bucket,

means for enabling the computer to search the pre-existing bucket for the record; and

means for enabling the computer to re-hash records that are searched in the pre-existing bucket and that belong in the new bucket.

19. The computer program product according to claim 18, further comprising:

means for enabling the computer to store the logical pointer within the new hash bucket in place of a regular pointer to a record.

20. The computer program product according to claim 19, ftirther comprising:

means for enabling the computer to move the logical pointer to a record that has been re-hashed to the new hash bucket and for enabling the computer to place a regular pointer to the record that has been re-hashed in the new hash bucket.

21. The computer program product according to claim 20, further comprising:

means for enabling the computer to remove the logical pointer when there are no more records in the existing bucket that belong in the new bucket.

24. The computer program product according to claim 15, wherein said means for enabling the computer to re-size the hash table comprises:

means for enabling the computer to re-size the hash table when the actual number of records in the hash table, divided by the number of buckets n, exceeds a limit of a maximum average number of records per hash bucket.