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)
“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)
“The water never formed to mind or voice,
Like a body wholly body, fluttering
Its empty sleeves; and yet its mimic motion
Made constant cry,”
—Wallace Stevens (1879–1955)
“Every man who has lived for fifty years has buried a whole world or even two; he has grown used to its disappearance and accustomed to the new scenery of another act: but suddenly the names and faces of a time long dead appear more and more often on his way, calling up series of shades and pictures kept somewhere, “just in case” in the endless catacombs of the memory, making him smile or sigh, and sometimes almost weep.”
—Alexander Herzen (1812–1870)