Methods and arrangements for inserting values in hash tables
US7571299B2 · kind B2 · utility
Assignee
Inventor
Key dates
| Filing date | Feb 16, 2006 |
| Grant date | Aug 4, 2009 |
| Priority date | — |
| Expiry date | Feb 6, 2027 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99931
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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 add…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.