Hash tables

Details Hash tables Hash tables

2006-03-29

2010-02-16

Bragdon, Reginald G (Department: 2189)

Electrical computers and digital processing systems: memory

Address formation

Hashing

C711S165000

Reexamination Certificate

active

07664927

ABSTRACT:
Hash tables comprising load factors of up to and above 97% are disclosed. The hash tables may be associated with three or more hash functions, each hash function being applied to a key to identify a location in a hash table. The load factor of a hash table may be increased, obviating any need to increase the size of the hash table to accommodate more insertions. Such increase in load factor may be accomplished by a combination of increasing the number of cells per bucket in a hash table and increasing the number of hash functions associated with the hash table.

REFERENCES:
patent: 4290105 (1981-09-01), Cichelli et al.
patent: 4996663 (1991-02-01), Nemes
patent: 5530958 (1996-06-01), Agarwal et al.
patent: 6553420 (2003-04-01), Karger et al.
patent: 6717946 (2004-04-01), Hariguchi et al.
patent: 6804767 (2004-10-01), Melvin
Rushton, Andy. hash—A Chained Hash Table Container. STLplus Library [online], Sep. 2, 2004 [retrieved on Feb. 28, 2008]. Retrieved from the Internet:< URL:http//stlplus.sourceforge.net/stlplus/docs/hash.html>.
Zaiane, Osmar. Dynamic Hashing. [online], Jul. 13, 1998 [retrieved on Mar. 11, 2008]. Retrieved from the Internet:< URL:http://www.cs.sfu.ca/CC/354/zaiane/material
otes/Chapter11
ode20.html>.
Tindale, Ben. Hash Tables in Java. Linux Gazette [online], Sep. 2000 [retrieved on Apr. 24, 2008]. Retrieved from the Internet:< URL:http//linuxgazette.net/issue57/tindale.html>.
Bandyopadhyay et al., Raj. Tradeoff between coverage of a Markov prefetcher and memory bandwidth usage. [online], Spring 2005 [retrieved on Apr. 24, 2008]. Retrieved from the Internet:<URL:http//www.owlnet.rice.edu/˜elec525/projects/markov—report.pdf>.
Fotakis, D. et al., “Space Efficient Hash Tables with Worst Case Constant Access Time”,Proceedings of the 20thAnnual Symposium on Theoretical Aspects of Computer Science(STACS 2003),Lecture Notes in Computer Science, 19 pages.
Panigrahy, R., “Efficient Hashing with Lookups in Two Memory Accesses”, Sep. 23, 2005, 1-12.

Affiliated with

Also associated with

Rating

Hash tables does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Hash tables, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hash tables will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4205297