Memory storage and retrieval with multiple hashing functions

Details Memory storage and retrieval with multiple hashing functions Memory storage and retrieval with multiple hashing functions

1998-10-15

2001-08-14

Thai, Tuan V. (Department: 2751)

Electrical computers and digital processing systems: memory

Address formation

Hashing

C711S100000, C711S200000

Reexamination Certificate

active

06275919

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to storing information to and retrieving information from a memory. More particularly, the present invention relates to storing and retrieving data from memories using hashing functions.
BACKGROUND OF THE INVENTION
A hashing function is a function that transforms a key value into a table index. The table index is often referred to as a hash value. The key value typically contains more bits than the table index.
As applied to a memory, an incoming datum contains a key value, the memory is the table, and the memory address where the incoming datum is stored is the table index. The table index can be the key value, or a hash value generated by a hashing function. A smaller table can be used when the table index is a hash value, since the hash value has fewer bits than the key value. When the table index is generated by a hashing function, multiple key values will map onto a single table index. This is known as a hash collision. Two prior art solutions to accommodate hash collisions include open chaining and closed chaining.
In an open chaining scheme, each location in the memory may be a data structure, such as a linked list, that is capable of storing multiple entries. When a hash collision occurs, all entries with the same table index are stored in the same data structure (e.g., in the same linked list). Conceptually, open chaining results in a memory that is a set of lists. To retrieve the data, all the entries in the list for a particular hash value have to be searched. If the list is large, the search may be very time consuming.
In a closed chaining scheme, when a hash collision occurs the incoming data causing the collision is stored in an entry in the memory that is subsequent to the location to which the key value hashed. This subsequent entry may be the next sequential memory location or may be the next location available sequentially after all other locations currently storing information that is associated with a hash value to the same location or all other locations already being used. To retrieve the information, the memory must be searched from the location corresponding to the table index to the next empty entry in the memory to determine whether that particular entry exists in the memory. Therefore, in large or frequently changing memories, retrieval of data can become time consuming as it is possible that a large portion of a memory may have to be searched.
Memories are often used with bridges in a communication network to store addresses of local devices. By storing the addresses of local devices, the bridge can determine whether to forward packets of information onto other parts of the network, an event which may waste resources and is undesirable. Such a bridge checks the destination address of the packet with previous source addresses stored in its memory to determine the destination address is local to the bridge. If so, the bridge need not forward the packet to other parts of the network, so that part of the network doesn't have to perform the unnecessary function of transmitting a packet whose recipient is on another portion of the network.
One way to reduce the size of these bridging devices is to reduce the size of their memory. However, reduction in the size of the memory may cause some of the same problems discussed above with respect to hashing as given above. Another way to improve the performance of these bridges is to store and retrieve addresses more quickly.
What is needed is an improved memory management strategy for use in memories that store and retrieve information based on hash values.
SUMMARY OF THE INVENTION
A method and apparatus for use of multiple hashing functions in a memory is described. A first index value is determined for a first set of incoming data during a first preselected time period. The first index value generated is according to a first hashing function. The first set of incoming data is stored in a cache memory based on the first index value. A second index value is determined for a second set of incoming data during a second preselected time period. The second index value is generated according to a second hashing function. The second set of incoming data is stored in the memory based on the second index value. This process may continue for subsequent time periods.


REFERENCES:
patent: 5027350 (1991-06-01), Marshall
patent: 5339398 (1994-08-01), Shah et al.
patent: 5509135 (1996-04-01), Steely, Jr.
patent: 5530958 (1996-06-01), Agarwal et al.
patent: 5608801 (1997-03-01), Aiello et al.
patent: 5692177 (1997-11-01), Miller

Affiliated with

Also associated with

Rating

Memory storage and retrieval with multiple hashing functions does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Memory storage and retrieval with multiple hashing functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory storage and retrieval with multiple hashing functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2501719