Methods and arrangements for inserting values in hash tables

Details Methods and arrangements for inserting values in hash tables Methods and arrangements for inserting values in hash tables

2006-02-16

2009-08-04

Ellis, Kevin L (Department: 2187)

Electrical computers and digital processing systems: memory

Address formation

Hashing

C711S200000, C711S201000, C711S217000, C711S219000, C707S793000

Reexamination Certificate

active

07571299

ABSTRACT:
Methods and arrangements to insert values in hash tables are contemplated. Embodiments include transformations, code, state machines or other logic to insert values in a hash table stored in electronic memory by hashing a value to determine a home address of an entry in the hash table, the hash table having a plurality of entries, each entry comprising an address, a value, and a link. The embodiments may include determining whether there is a collision of the value with a value stored in the entry; inserting the value in the entry if there is no collision; and generating the addresses of further entries until an entry is found in which the value can be inserted if there is a collision. The embodiments may include generating a plurality of addresses of entries based upon the address of a previously generated entry. In some embodiments, a plurality of addresses of entries may be generated from an address of an entry by changing single bits of the address of the entry and taking the resulting address modulus the table size. In further embodiments, the link from one entry to another in the hash table may consist of a representation of the position of the bit that was changed in the address of the entry. In further embodiments, the space required to store a link may be smaller than the space required to store an address of an entry.

REFERENCES:
patent: 6086626 (2000-07-01), Jain et al.
patent: 6115802 (2000-09-01), Tock et al.
patent: 6292795 (2001-09-01), Peters et al.
patent: 6804767 (2004-10-01), Melvin
patent: 6915296 (2005-07-01), Parson
patent: 2004/0034656 (2004-02-01), Beesley
patent: 2004/0083347 (2004-04-01), Parson
patent: 2004145729 (2004-05-01), None
Loudon, Kyle, Mastering Algorithms with C, 1999, O'Reilly, Chapter 8—Hash Tables.
Faloutsos, Christos, Multiattribute Hashing Using Gray Codes, 1986, ACM, pp. 227-238.
Constantine Halatsis and George Philokyprou, Pseudochaining in Hash Tables, Jul. 1978, Communications of the ACM, vol. 21, 554-557.

Affiliated with

Also associated with

Rating

Methods and arrangements for inserting values in 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 Methods and arrangements for inserting values in hash tables, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and arrangements for inserting values in hash tables will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4122905