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:
“He who eats alone chokes alone.”
—Arab proverb, quoted in H.L. Mencken’s Dictionary of Quotations (1942)
“You may read any quantity of books, and you may almost as ignorant as you were at starting, if you don’t have, at the back of your minds, the change for words in definite images which can only be acquired through the operation of your observing faculties on the phenomena of nature.”
—Thomas Henry Huxley (1825–95)
“A tart temper never mellows with age, and a sharp tongue is the only edged tool that grows keener with constant use.”
—Washington Irving (1783–1859)
“What a devil hast thou to do with the time of the day? Unless hours were cups of sack, and minutes capons, and clocks the
tongues of bawds, and dials the signs of leaping-houses, and the blessed sun himself a fair hot wench in flame-colored
taffeta, I see no reason why thou shouldst be so superfluous
to demand the time of the day.”
—William Shakespeare (1564–1616)