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:
““Will I have to use a dictionary to read your book?” asked Mrs. Dodypol. “It depends,” says I, “how much you used the dictionary before you read it.””
—Alexander Theroux (b. 1940)
“It requires a surgical operation to get a joke well into a Scotch understanding. The only idea of wit, or rather that inferior variety of the electric talent which prevails occasionally in the North, and which, under the name of “Wut,” is so infinitely distressing to people of good taste, is laughing immoderately at stated intervals.”
—Sydney Smith (1771–1845)
“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)
“When her husband clutches at her dress,
she lowers her face,
her modesty aroused.
When he wants a wild embrace,
she shyly secrets away
her limbs.
She can’t say a word
and bestows her gaze
on her beaming friends.
A new wife suffers
with shame
the first time she makes love.”
—Amaru (c. seventh century A.D.)