US5339398A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Memory architecture and method of data organization optimized for hashing
Assignee: Philips North America LLC
•
Filing: 1992-07-14
•
Granted: 1994-08-16
•
Expires: 2012-07-14
Abstract
Abstract A hashing data storage and retrieval arrangement whose storage capacity is unaffected by collisions. A first memory serves as a hash index table, for storing pointers at each address location corresponding to a hash value generated by hashing a key data word. Each pointer is the address of a location in a second memory, which has a separate storage location for each key data word, its associated data, and a further pointer which is the address of the next key data word resulting from a collision during hashing. Preferably a pipeline register between the two memories permits hashing of a subsequent key data word while accessing of the second memory is still in progress.
Inventors
- 👤 Imran A. Shah
- 👤 Brian C. Johnson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 00:03
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/901; G06F16/9014
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
256 words
A method of pipe-lined memory accessing for a multiplicity of sequentially received data values forming a string, comprising: receiving said sequentially received data values, storing pointer values in a first memory, storing data values and respective further pointer values in a second memory at locations corresponding to pointer values in said first memory, hashing respective prefix-data combinations formed from a respective prefix and a respective one of said data values to provide a respective hash value, said respective hash value including an address in said first memory, responsive to hashing of a given prefix-data combination including a given received data value, and the resulting hash value corresponding to one location in said first memory at which a pointer value is already stored, hashing the next received data value with an assumed prefix having a value corresponding to that already stored pointer value; comparing the data value stored at the location corresponding to said pointer value stored at said one location in said second memory with a value related to said given received data value, while hashing said assumed prefix with said next received data value; and selecting the prefix for the next hashing responsive to the result of the comparison, and responsive to hashing of said given prefix-data combination including said given received data value, and the resulting hash value corresponding to a location in said first memory at which a pointer value is not already stored, hashing the next received data value with a prefix having a value corresponding to said given received data value.
Claim 2
Independent Claim
256 words
A method of pipe-lined memory accessing for a multiplicity of sequentially received data values forming a string, comprising: receiving said sequentially received data values, storing pointer values in a first memory, storing data values and respective further pointer values in a second memory at locations corresponding to pointer values in said first memory, hashing respective prefix-data combinations formed from a respective prefix and a respective one of said data values to provide a respective hash value, said respective hash value including an address in said first memory, responsive to hashing of a given prefix-data combination including a given received data value, and the resulting hash value corresponding to one location in said first memory at which a pointer value is already stored, hashing the next received data value with an assumed prefix having a value corresponding to that already stored pointer value; comparing the data value stored at the location corresponding to said pointer value stored at said one location in said second memory with a value related to said given received data value, while hashing said assumed prefix with said next received data value; and selecting the prefix for the next hashing responsive to the result of the comparison, and responsive to hashing of said given prefix-data combination including said given received data value, and the resulting hash value corresponding to a location in said first memory at which a pointer value is not already stored, hashing the next received data value with a prefix having a value corresponding to said given received data value.
Claim 3
Dependent Claim
37 words
A method as claimed in claim 1, characterized by storing, at each location in said first memory, a respective tag bit whose value indicates whether or not a respective said pointer value is stored at that location.
Claim 4
Dependent Claim
37 words
A method as claimed in claim 1, characterized by storing, at each location in said second memory, a respective tag bit whose value indicates whether or not a respective said data value is stored at that location.
Claim 5
Dependent Claim
74 words
A method as claimed in claim 1, characterized in that said hashing produces hash values which respectively comprise an address portion and an abbreviated key, said address portion and abbreviated key together being invertible, said data values stored in said second memory comprise said abbreviated keys, and comparing includes comparing the respective abbreviated key stored in the second memory with the abbreviated key portion of the hashed value of the corresponding received data value.
Claim 6
Independent Claim
349 words
An apparatus for pipe-lined memory accessing for a multiplicity of sequentially received data values forming a string, comprising: means for receiving said sequentially received data values, a first memory for storing pointer values, a second memory for storing data values and respective further pointer values at locations corresponding to pointer values in said first memory, comparing means for comparing the data value stored in a given location in said second memory with a value related to one of said received data values, means for selecting a prefix, and hashing means, coupled to the means for receiving and said means for selecting, for hashing respective prefix-data combinations formed from a respective prefix and a respective one of said data values to provide a respective hash value, said respective hash value including an address in said first memory, said means for selecting, responsive to hashing of a given prefix-data combination including a given received data value, and the resulting hash value corresponding to one location in said first memory at which a pointer value is already stored, providing a value corresponding to that already stored pointer value to said hashing means, to be an assumed prefix for hashing with the next received data value after said given received data value; said comparing means, while said hashing means is then hashing said assumed prefix with said next received data value, comparing the data value stored at the location corresponding to said pointer value stored at said one location in said second memory with a value related to said given received data value; and said means for selecting being responsive to the result of the comparison in selecting the prefix for the next hashing, and said means for selecting, responsive to hashing of said given prefix-data combination including said given received data value, and the resulting hash value corresponding to a location in said first memory at which a pointer value is not already stored, providing said given received data value to said hashing means to be the prefix for hashing with the next received data value after said given received data value.
Claim 7
Independent Claim
349 words
An apparatus for pipe-lined memory accessing for a multiplicity of sequentially received data values forming a string, comprising: means for receiving said sequentially received data values, a first memory for storing pointer values, a second memory for storing data values and respective further pointer values at locations corresponding to pointer values in said first memory, comparing means for comparing the data value stored in a given location in said second memory with a value related to one of said received data values, means for selecting a prefix, and hashing means, coupled to the means for receiving and said means for selecting, for hashing respective prefix-data combinations formed from a respective prefix and a respective one of said data values to provide a respective hash value, said respective hash value including an address in said first memory, said means for selecting, responsive to hashing of a given prefix-data combination including a given received data value, and the resulting hash value corresponding to one location in said first memory at which a pointer value is already stored, providing a value corresponding to that already stored pointer value to said hashing means, to be an assumed prefix for hashing with the next received data value after said given received data value; said comparing means, while said hashing means is then hashing said assumed prefix with said next received data value, comparing the data value stored at the location corresponding to said pointer value stored at said one location in said second memory with a value related to said given received data value; and said means for selecting being responsive to the result of the comparison in selecting the prefix for the next hashing, and said means for selecting, responsive to hashing of said given prefix-data combination including said given received data value, and the resulting hash value corresponding to a location in said first memory at which a pointer value is not already stored, providing said given received data value to said hashing means to be the prefix for hashing with the next received data value after said given received data value.
Claim 8
Dependent Claim
37 words
An apparatus as claimed in claim 5, characterized in that said first memory comprises, at each location, a respective tag bit whose value indicates whether or not a respective said pointer value is stored at that location.
Claim 9
Dependent Claim
37 words
An apparatus as claimed in claim 5, characterized in that said second memory comprises, at each location, a respective tag bit whose value indicates whether or not a respective said data value is stored at that location.
Claim 10
Dependent Claim
79 words
An apparatus as claimed in claim 5, characterized in that said hashing means produces hash values which respectively comprise an address portion and an abbreviated key, said address portion and abbreviated key together being invertible, said data values stored in said second memory comprise said abbreviated keys, and said means for comparing compares the respective abbreviated key stored in said given location with the abbreviated key portion of the hashed value of said one of said received data values.
References Cited (Backward Citations)
US4215402A
Cited
US4290105A
Cited
US4611272A
Cited
US4736287A
Cited
US4897785A
Cited
US4807122A
Cited
US4730249A
Cited
US4916658A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-08-15 | 1998-02-14 | 1998-08-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-08-15 | 2002-02-14 | 2002-08-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-08-15 | 2006-02-14 | 2006-08-16 | $7700.00 | Window Closed / Lapsed |