File ChainedHashTable.h
↰ Parent directory (ADS/dictionary)
The hash table with lists of overflow of section 7.2.1, a realization of the DICTIONARY [see File ADT.h]: the place i of a vector of size m holds a LIST with the pairs whose keys have H( k ) = i, insert() puts a new key at the head of its list, lookup() and remove() go along it.
Definition (ADS/dictionary/ChainedHashTable.h)
Detailed Description
A list may also bring to its head the key just found, so that the keys looked up often stay close to it (exercise 7.5), or be kept sorted, so that an unsuccessful search stops at the first larger key (exercise 7.10) [see Chain].
With the load factor :math:` alpha = n / m , an unsuccessful search accesses :math: 1 + alpha ` cells on average and a successful one :math:` 1 + alpha / 2 ; probes() gives the cells that the last operation examined, the nil that ends an unsuccessful search included. The table may restructure itself (section 7.4), doubling m when :math: alpha > 2 ` and halving it, down to the initial size, when :math:` alpha < 1 / 2 : the two thresholds are 4 times apart, so that between two restructurings there are at least m / 4 operations and the cost stays O( 1 ) amortized [see :ref:`file_ADS_dictionary_TableSize.h].
The contracts [see File Contract.h]: m > 0 and a list that exists for chain(); after insert() the key is in the table and after remove() it is not; the invariant is that each key is in the list of its own place, that the lists are sorted when they must be, that size() counts the keys, and that the key of the operation is in its list at most once. On a table of more than 1024 lists the invariant is checked on the list of that key only, so that a long sequence of operations at the level 3 stays linear; the checks do not change probes(). The operations are defined in ChainedHashTable.tpp.
Montresor, Algoritmi e Strutture Dati, 2025, sections 7.2-7.4, https://algoritmicamente.it/materiali/libro/capitoli/cap07.pdf
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
ADS/Contract.h(File Contract.h)ADS/dictionary/TableSize.h(File TableSize.h)ADS/dictionary/impl/ChainedHashTable.tppADS/sequence/List.h(File List.h)conceptscstddeffunctionaliteratoroptionalutilityvector