System with a plurality of hash tables each using different adaptive hashing functions
US5032987A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | May 11, 1990 |
| Grant date | Jul 16, 1991 |
| Priority date | — |
| Expiry date | May 11, 2010 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L69/00
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A data processing system and method particularly useful for network address lookup in interconnected local area networks uses a family of hashing algorithms that allow implementation of a dictionary that is particularly advantageous when the underlying hardware allows parallel memory reads in different memory banks. The system and method requires exactly one memory cycle for deletes and lookup and constant expected amortized cost for insertions. The system and method uses easy-to-compute hash functions and makes no unproven assumptions about their randomness properties, or about any property of keys drawn from a universe U. The system and method makes it possible to build a dictionary that is able to answer 20 parallel searches among 64,000 entries in less than 5 .mu.s using relatively inexpensive hardware.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.