Memory storage and retrieval with multiple hashing functions
AssigneeCreative Technology Ltd
InventorPeter Johnson
Life of this patent
Estimating the term…
Abstract
A method and apparatus for using a hashing function to store data in a cache memory. Briefly, a method and apparatus is provided for using a hashing function to store data in a cache memory where the hashing function used is changed periodically. In one embodiment, the cache memory stores the data, an indicator of the hashing function used and the index value generated by the hashing function used. To retrieve data from the cache memory, the current hashing function is used to generate an index for the incoming data. The data at the index is checked to determine whether the stored data matches the incoming data. If the data at the index generated by the current hashing function does not match the incoming data, previous hashing functions are used to repeat the search.
Claims18
A method comprising:
- determining a first index value for a first set of incoming data during a first preselected time period, the first index value generated according to a first hashing function using a hash generator configurable to providing a plurality of hashing functions;
- storing the first set of incoming data in a memory based on the first index value, and storing an indication that the first hashing function generated the first index value;
- changing the hash generator, in response to an input, from providing the first hashing function to providing a second hashing function;
- determining a second index value for a second set of incoming data during a second preselected time period, the second index value generated according to the second hashing function;
- and
- storing the second set of incoming data in the memory based on the second index value, and storing an indication that the second hashing function generated the second index value.
An apparatus comprising:
- means for determining a first index value for a first set of incoming data during a first preselected time period, the first index value generated according to a first hashing function using a hash generator configurable to providing a plurality of hashing functions;
- means for storing the first set of incoming data in a memory based on the first index value further comprising means for storing an indication that the first hashing function generated the first index value;
- means for changing the hash generator, in response to an input, from providing the first hashing function to providing a second hashing function;
- means for determining a second index value for a second set of incoming data during a second preselected time period, the second index value generated according to the second hashing function;
- and
- means for storing the second set of incoming data in the memory based on the second index value further comprising means for storing an indication that the second hashing function generated the second index value.
Dependencies are inferred from the claim text.