System with a plurality of hash tables each using different adap

Details System with a plurality of hash tables each using different adap System with a plurality of hash tables each using different adap

1990-05-11

1991-07-16

Lee, Thomas C.

Boots, shoes, and leggings

3642604, 3642612, 364262, G06F 1202, G06F 738

Patent

active

050329871

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.

REFERENCES:
patent: 4063220 (1977-12-01), Metcalf et al.
patent: 4564944 (1986-01-01), Arnold et al.
patent: 4706081 (1987-11-01), Hart et al.
patent: 4731739 (1988-03-01), Woffinden et al.
patent: 4897785 (1990-01-01), Ziiger
Du et al., "The Study of a New Perfect Hash Scheme", IEEE Tran. Software Engineering, 5/1983, pp. 305-313.
Hawe, R. et al., "The Extended Local Area Network Architecture and LANBridge Loo", Digital Technical Journal, No. 3, Sep. 1986, pp. 54-72.
The Ethernet, A Local Area Network, Data Link Layer and Physical Layer Specifications, Version 1.0, Sep. 30, 1980.
M. Fredman, J. Komlos, E. Szemeredi, "Storing a Sparse Table with 0(1) Worst Case Access Time", Journal of the ACM, vol. 31, No. 3, Jul. 1984, pp. 538-544.
A. V. Aho and D. Lee, "Storing a Dynamic Sparse Table", 27th IEEE Symposium on Foundations of Computer Science, 1986, pp. 55-60.
L. Carter, M. Wegman, "Universal Classes of Hash Functions", JCSS, 18, No. 2, 1979, pp. 143-154.

Affiliated with

Also associated with

Rating

System with a plurality of hash tables each using different adap does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System with a plurality of hash tables each using different adap, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System with a plurality of hash tables each using different adap will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-136773