File PointerTable.h

↰ Parent directory (ADS/dictionary)

A hash table of pointers with open addressing, beyond the book: the set of the objects of a search (its closed list), each found from its key, e.g., the state of a node.

Definition (ADS/dictionary/PointerTable.h)

Detailed Description

A place holds the pointer and the whole hash of 64 bits of the key of its object, so that a probe compares two keys only when their hashes are equal and a growth moves the places without touching the objects; the inspection is linear [see File OpenHashTable.h], i.e., along consecutive places and lines of cache, which beats the lists of overflow when the table does not fit in the cache, and the first place of a hash is its top bits after the product by :math:` lfloor 2^{64} / phi rfloor ` [see fibonacciPlace()], so that hashes whose low bits are regular (e.g., the owner of a state in a parallel search, h mod p) still spread over the table. The load factor stays below 7 / 10, the table doubling past it. There is no removal, which a search does not need and which would cost the simplicity of the probes. find_or_insert( key , hash , make ) inserts the object that make() returns only if the key is not there, with one inspection; prefetch( hash ) asks for the first place of a hash, so that the misses of the lookups of all the successors of a node overlap. The places come from the allocator A, which may give, e.g., huge pages.

Two keys are equal by eq( p , key ), with p a pointer of the table; by default p->state == key, the canonical node of a state of a search.

The contracts [see File Contract.h]: make() returns a pointer that is not nil; the invariant is that the load factor stays below 7 / 10 and that each object is reached from the first place of its hash with no empty place in between (checked on the key of the operation). The operations are defined in PointerTable.tpp.

    1. Knuth, The Art of Computer Programming, vol. 3, 2nd ed., Addison-Wesley, 1998, section 6.4 (linear probing, the multiplicative hashing)

  2. Burns, M. Hatem, M. J. Leighton, W. Ruml, Implementing fast heuristic search code, Proceedings of the 5th Symposium on Combinatorial Search (SoCS), 25-32, 2012

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes