Method and apparatus for a four-way hash table
US6775281B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | Sep 30, 1999 |
| Grant date | Aug 10, 2004 |
| Priority date | — |
| Expiry date | Sep 30, 2019 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L45/745
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A number of hash tables are accessed concurrently with a different computed index for each hash table. Each index identifies a location in one of the hash tables at which a forwarding entry may be stored. To search for a forwarding entry, the locations identified by the indices computed by performing a hash function on a search key are searched to a match for the search key. To insert a forwarding entry if single cycle inserting is not required and all the locations identified by the indices computed by performing a hash function on an insert key are used then the data base is reordered so that the forwarding entry can be inserted at one of the locations identified by one of the computed indices for the insert key. If single cycle insertion is required and all the locations identified by the computed indices are used, one of the locations identified by one of the computed indices for the insert key is randomly overwritten by the forwarding entry.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.