Methods and arrangements for inserting values in hash tables

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.