File KnuthHashing.h

↰ Parent directory (ADS/dictionary)

Two hash tables of Knuth, beyond the book [see File ChainedHashTable.h and File OpenHashTable.h for those of chapter 7], both without removal:

Definition (ADS/dictionary/KnuthHashing.h)

Detailed Description

  • CoalescedHashTable (Algorithm 6.4C, with the cellar of Vitter): the lists of overflow live in the table itself, a key that collides being put in the empty place of largest index (the first ones taken being those of a cellar beyond the m places addressed by the hash) and linked at the end of the list of its place, so that the lists may merge (coalesce); with a cellar of about 14 % of the table the searches are nearly as fast as with separate lists, with no memory out of the table;

  • BrentHashTable, the double hashing [see Probing] with the improvement of Brent to the insertions: the key K is placed at the j-th place of its inspection, and the key found there moved forward by s - j places of its own inspection, for the least s, and then the least j, that find an empty place; this lowers the expected number of probes of a successful search below 2.5 even in a full table, against :math:` - ln( 1 - alpha ) / alpha ` of the plain double hashing, at no cost for the searches.

The contracts [see File Contract.h]: the table is not full on insert(); insert() ensures that the key is there; the invariant of CoalescedHashTable is that each key is on the list of its place, an audit. The operations are defined in KnuthHashing.tpp.

    1. Knuth, The Art of Computer Programming, vol. 3, 2nd ed., Addison-Wesley, 1998, section 6.4 (Algorithm C and exercise 6.4-49 on Brent’s variation)

    1. Vitter, Implementations for coalesced hashing, Communications of the ACM 25(12), 911-926, 1982, doi:10.1145/358728.358745

    1. Brent, Reducing the retrieval time of scatter storage techniques, Communications of the ACM 16(2), 105-109, 1973, doi:10.1145/361952.361964

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes