US5960434A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System method and computer program product for dynamically sizing hash tables
Assignee: Morgan Stanley and Co LLC
•
Filing: 1997-09-26
•
Granted: 1999-09-28
•
Expires: 2017-09-26
Abstract
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.
Inventors
- 👤 Curt F. Schimmel
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 01:01
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/901; G06F16/9014; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99942; Y10S707/99943
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
104 words
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.
Claim 2
Independent Claim
104 words
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.
Claim 3
Dependent Claim
19 words
The method according to claim 1, wherein step (2) comprises: (a) hashing the records using a modulo hashing function.
Claim 4
Dependent Claim
27 words
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.
Claim 5
Dependent Claim
62 words
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.
Claim 6
Dependent Claim
28 words
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.
Claim 7
Dependent Claim
48 words
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.
Claim 8
Dependent Claim
33 words
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.
Claim 9
Independent Claim
112 words
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.
Claim 10
Independent Claim
112 words
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.
Claim 11
Dependent Claim
15 words
The system according to claim 8, wherein said hashing function comprises a modulo hashing function.
Claim 12
Dependent Claim
29 words
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.
Claim 13
Dependent Claim
74 words
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.
Claim 14
Dependent Claim
28 words
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.
Claim 15
Dependent Claim
44 words
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.
Claim 16
Dependent Claim
29 words
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.
Claim 17
Dependent Claim
144 words
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.
Claim 18
Dependent Claim
144 words
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.
Claim 19
Dependent Claim
37 words
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.
Claim 20
Dependent Claim
43 words
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.
Claim 21
Dependent Claim
107 words
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.
Claim 22
Dependent Claim
34 words
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.
Claim 23
Dependent Claim
54 words
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.
Claim 24
Dependent Claim
36 words
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.
Claim 25
Dependent Claim
45 words
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.
Claim 26
Dependent Claim
45 words
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.
Claim 27
Dependent Claim
61 words
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.
References Cited (Backward Citations)
US4996663A
Cited
US5121495A
Cited
US5287499A
Cited
US5265245A
Cited
US5197002A
Cited
US5511190A
Cited
US5612865A
Cited
US5623545A
Cited
US5706462A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-09-27 | 2003-03-29 | 2003-09-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-09-27 | 2007-03-29 | 2007-09-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-09-27 | 2011-03-29 | 2011-09-28 | $7700.00 | Window Closed / Lapsed |