Dictionary Operation in Constant Time
Using linear probing, dictionary operation can be implemented in constant time. In other words, insert, remove and find operations can be implemented in O(1), as long as the load factor of the hash table is a constant strictly less than one. This analysis makes the (unrealistic) assumption that the hash function is completely random, but can be extended also to 5-independent hash functions. Weaker properties, such as universal hashing, are not strong enough to ensure the constant-time operation of linear probing, but one practical method of hash function generation, tabulation hashing, again leads to a guaranteed constant expected time performance despite not being 5-independent.
Read more about this topic: Linear Probing
Famous quotes containing the words dictionary, operation, constant and/or time:
“The much vaunted male logic isn’t logical, because they display prejudices—against half the human race—that are considered prejudices according to any dictionary definition.”
—Eva Figes (b. 1932)
“An absolute can only be given in an intuition, while all the rest has to do with analysis. We call intuition here the sympathy by which one is transported into the interior of an object in order to coincide with what there is unique and consequently inexpressible in it. Analysis, on the contrary, is the operation which reduces the object to elements already known.”
—Henri Bergson (1859–1941)
“Praise to Christ who feeds the hungry, frees the captive, finds the lost,
Heals the sick, upsets religion, fearless both of fate and cost.
Celebrate Christ’s constant presence—Friend and Stranger, Guest and Host.”
—The Iona Community (founded 1938)
“... but by that time a lot of sea had rolled by and Lucette was too tired to wait. Then the night was filled with the rattle of an old but still strong helicopter. Its diligent beam could spot only the dark head of Van, who, having been propelled out of the boat when it shied from its own sudden shadow, kept bobbing and bawling the drowned girl’s name in the black, foam-veined, complicated waters.”
—Vladimir Nabokov (1899–1977)