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 is critical vision alone which can mitigate the unimpeded operation of the automatic.”
—Marshall McLuhan (1911–1980)
“Our farmers round, well pleased with constant gain,
Like other farmers, flourish and complain.”
—George Crabbe (1754–1832)
“The purpose of playing, whose end, both at the first and now,
was and is, to hold as ‘twere the mirror up to nature: to show
virtue her feature, scorn her own image, and the very age and
body of the time his form and pressure.”
—William Shakespeare (1564–1616)