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 reputation of a man is like his shadow; it sometimes follows and sometimes precedes him, sometimes longer and sometimes shorter than his natural size.”
—French Proverb. Quoted in Dictionary of Similes, ed. Frank J. Wilstach (1916)
“Waiting for the race to become official, he began to feel as if he had as much effect on the final outcome of the operation as a single piece of a jumbo jigsaw puzzle has to its predetermined final design. Only the addition of the missing fragments of the puzzle would reveal if the picture was as he guessed it would be.”
—Stanley Kubrick (b. 1928)
“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)
“Dear, why should you command me to my rest,
When now the night doth summon all to sleep?
Methinks this time becometh lovers best;
Night was ordained together friends to keep.
How happy are all other living things,
Which though the day disjoin by several flight,
The quiet evening yet together brings,
And each returns unto his love at night.”
—Michael Drayton (1563–1631)