Hash-based translation method and apparatus with multiple level collision resolution

• US 5,920,900 A
• Filed: 12/30/1996
• Issued: 07/06/1999
• Est. Priority Date: 12/30/1996
• Status: Expired due to Term

• Current Assignee: Extreme Networks, Inc.
• Original Assignee: Cabletron Systems Incorporated (Extreme Networks, Inc.)
• Inventors: Poole, Nigel T., Spinney, Barry A.
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): Chow, Christopher S.
• Application Number:
  US08/775,091
• Time in Patent Office: 918 Days
• Field of Search: 711/216, 711/202, 711/206, 370/392, 370/389
• US Class Current: 711/216
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: H04L 12/46 Interconnection of networks
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A translation is performed by using a programmable hashing technique on an input number to generate a hashed number. A subset of the hashed number bits are used to index a first hash table. In first hash table locations where a hash collision does not occur, the first hash table entry contains an index into an output table which contains the desired translated output number. In first hash table locations where a hash collision occurs, the first hash table entry contains a pointer to a first resolution table area in a second hash table. The first resolution table area contains entries which are indexed by additional bits selected from the hashed number in accordance with a mask field in the first hash table location. If collisions occur in the resolution table a new resolution table is created and the process is repeated. The resolution process thus proceeds in stages until all input numbers have been translated.

Claims

1. Apparatus for resolving a hash collision which occurs in a hash table when two input numbers generate a hashed value which is used to access a single location in the hash table, the apparatus comprising:

at least one resolution table containing a plurality of entries;

a mechanism for inserting a collision entry into the single location and into each resolution table entry where a collision occurs, the collision entry containing a bit mask and a pointer to a resolution table; and

an index generator responsive to each collision entry and to portions of the hashed value for accessing the one resolution table pointed to by the each collision entry.

2. Apparatus according to claim 1 wherein the bit mask in each collision entry comprises a mechanism for selecting the portions of the hashed value used by the index generator.

3. Apparatus according to claim 1 wherein the index generator combines the collision entry pointer with the portions of the hashed value to access the one resolution table.

4. Apparatus according to claim 1 wherein part of the hashed value is used to access the single location in the hash table and the portions of the hashed value used by the index generator are different from the part of the hashed value used to access the single location in the hash table.

5. A method for resolving a hash collision which occurs in a hash table when two input numbers generate a hashed value which is used to access a single location in the hash table, the method comprising the steps of:

A. creating at least one resolution table containing a plurality of entries;

B. inserting a collision entry into the single location and into each resolution table entry where a collision occurs, the collision entry containing a bit mask and a pointer to a resolution table; and

C. accessing the one resolution table pointed to by the each collision entry using each collision entry and portions of the hashed value.

6. A method according to claim 5 wherein step C comprises the step of:

C1. using the bit mask in each collision entry to select the portions of the hashed value for accessing the one resolution table.

7. A method according to claim 5 wherein step C further comprises the step of:

C2. combining the collision entry pointer with the portions of the hashed value to access the one resolution table.

8. A method according to claim 5 wherein step C comprises the step of:

C3. using a part of the hashed value to access the single location in the hash table which is different from the portions of the hashed value used to access the resolution table.

9. Translation apparatus for translating a plurality of input numbers into a plurality of output numbers, the apparatus comprising:

a hasher responsive to each of the plurality of input numbers for generating a hashed argument corresponding to the each input number, the hashed number having a plurality of bits;

a first hash table containing a plurality of entries, each of the plurality of entries where a hash collision does not occur containing an index into an output table which contains the output number and each of the plurality of entries where a hash collision occurs containing a bit mask and a pointer to a next resolution table;

at least one resolution table containing a plurality of entries, each of the plurality of entries where a hash collision does not occur containing an index into the output table which contains the output number and each of the plurality of entries where a hash collision occurs containing a bit mask and a pointer to a next resolution table;

a first index generator entries responsive to a subset of the hashed argument bits for accessing the first hash table; and

a second index generator responsive to a collision entry and to hashed argument bits not in the hashed argument bit subset for accessing the at least one resolution table.

10. A computer program product for resolving a hash collision which occurs in a hash table stored in a memory when two input numbers generate a hashed value which is used to access a single location in the hash table, the computer program product comprising a computer usable medium having computer readable program code thereon, the program code including:

program code for creating at least one resolution table containing a plurality of entries in the memory;

program code for inserting a collision entry into the single location and into each resolution table entry where a collision occurs, the collision entry containing a bit mask and a pointer to a resolution table; and

program code responsive to each collision entry and to portions of the hashed value for accessing the one resolution table pointed to by the each collision entry.

11. A computer program product according to claim 10 further comprising program code for using the bit mask in each collision entry to select the portions of the hashed value used by the index generator.

12. A computer program product according to claim 10 wherein the program code for accessing the one resolution table comprises program code for combining the collision entry pointer with the portions of the hashed value to access the one resolution table.

13. A computer program product according to claim 10 wherein part of the hashed value is used to access the single location in the hash table and the portions of the hashed value used by the program code for accessing the one resolution table are different from the part of the hashed value used to access the single location in the hash table.