File OpenHashTable.h

↰ Parent directory (ADS/dictionary)

The hash table with open addressing of section 7.2.2, a realization of the DICTIONARY [see File ADT.h].

Definition (ADS/dictionary/OpenHashTable.h)

Detailed Description

The table keeps the pairs in the vector itself (open addressing): the key k goes into the first free place of its sequence of inspection :math:` H( k , 0 ) , H( k , 1 ) , ldots , H( k , m - 1 ) `, which is

  • linear, :math:` H( k , i ) = ( H_0( k ) + delta i ) bmod m , a permutation of the places when :math: gcd( delta , m ) = 1 `;

  • quadratic, :math:` H( k , i ) = ( H_0( k ) + c_1 i + c_2 i^2 ) bmod m ` with m prime, which in general is not a permutation, so an insertion may fail while some place is still free;

  • double hashing, :math:` H( k , i ) = ( H_0( k ) + H_delta( k ) i ) bmod m , with :math: H_delta( k ) = 1 + ( h( k ) bmod ( m - 1 ) ) ` for m prime and :math:` H_delta( k ) = ( lfloor h( k ) / m rfloor bmod m ) | 1 `, odd, for m a power of two, so that the step is coprime with m

or, beyond the book, the triangular inspection :math:` H( k , i ) = ( H_0( k ) + i ( i + 1 ) / 2 ) bmod m , a permutation when m is a power of two, and the double hashing whose step comes from a second function g of the hash, :math: H_delta( k ) = 1 + ( g( h( k ) ) bmod ( m - 1 ) ) ` for m prime and :math:` ( g( h( k ) ) bmod m ) | 1 ` for m a power of two, and the pseudo-random inspection :math:` H( k , i ) = ( H_0( k ) + p_i ) bmod m , where :math: p_0 = 0 , p_1 , ldots , p_{m-1} ` is a fixed random permutation of :math:` 0 , ldots , m - 1 , drawn from a seed for each size m, so that it works with every m and two keys with different :math: H_0 ` do not share the rest of their inspection as in the linear one (no primary clustering)

[see Probing], with :math:` H_0( k ) = h( k ) bmod m ` and h the hash of the keys. A place is nil (never used), full or deleted: the deleted places, left by remove(), do not stop an inspection but are reused by insert(). The scan of the book stops at the key, at a nil place or after m inspections, and remembers the first deleted place met [see scan()].

With the load factor :math:` alpha = n / m `, the expected number of places accessed by an unsuccessful search I( alpha ) and by a successful one S( alpha ) are, under uniform hashing, :math:`[
begin{array}{lll}

mbox{linear} & frac{1}{2} left( 1 + frac{1}{( 1 - alpha )^2} right) & frac{1}{2} left( 1 + frac{1}{1 - alpha} right) \ mbox{double} & frac{1}{1 - alpha} & - frac{1}{alpha} ln( 1 - alpha )

end{array}

` and probes() gives the number of places that the last operation examined, the nil that ends an unsuccessful search included.

The table may restructure itself (section 7.4): it doubles m when the full and deleted places are more than m / 2, so that :math:` alpha leq 1 / 2 ` always and the deleted places go away, and halves it, down to the initial size, when :math:` alpha < 1 / 8 . The two thresholds are 4 times apart, not twice as in the example of the book (0.5 and 0.25): with the latter the table just doubled has :math: alpha approx 1 / 4 , a couple of removals halve it back to :math: alpha approx 1 / 2 , a single insertion doubles it again, and a sequence alternating them costs O( m ) per operation [see :ref:`file_ADS_dictionary_TableSize.h]. A new size that the inspection does not work with, a prime that divides the step of a linear one, is replaced by the next prime that it works with. Since only a removal halves m, a table emptied may stay above its initial size.

The contracts [see File Contract.h]: m > 0 and an inspection that works with m (a linear step coprime with m, a prime m for the quadratic one, a power of two for the triangular one, a prime or a power of two for the double hashing, any m for the pseudo-random one), a full place for keyAt(); after insert() the key is in the table and after remove() it is not; the invariant is that the first place of the inspection of each key that holds it is its own place, with no nil before it, and that size() and the deleted places are counted right. On a table of more than 1024 places the invariant is checked on the inspection of the key of the operation only, up to its first nil, so that a long sequence of operations at the level 3 stays linear; the checks do not change probes(). An insertion whose inspection finds no place, which a quadratic inspection allows while some place is free, is not a fault of the caller and throws std::overflow_error. The operations are defined in OpenHashTable.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, sections 7.2-7.4, https://algoritmicamente.it/materiali/libro/capitoli/cap07.pdf

    1. Knuth, The Art of Computer Programming, vol. 3, 2nd ed., Addison-Wesley, 1998, section 6.4 (the pseudo-random and the quadratic inspections)

    1. Knuth, The Art of Computer Programming, vol. 3, Sorting and Searching, 2nd ed., Addison-Wesley, 1998, section 6.4

    1. Peterson, Addressing for random-access storage, IBM Journal of Research and Development 1(2), 130-146, 1957, doi:10.1147/rd.12.0130

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes