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)
“An absolute can only be given in an intuition, while all the rest has to do with analysis. We call intuition here the sympathy by which one is transported into the interior of an object in order to coincide with what there is unique and consequently inexpressible in it. Analysis, on the contrary, is the operation which reduces the object to elements already known.”
—Henri Bergson (1859–1941)
“I should say that the most prominent scientific men of our country, and perhaps of this age, are either serving the arts and not pure science, or are performing faithful but quite subordinate labors in particular departments. They make no steady and systematic approaches to the central fact.... There is wanting constant and accurate observation with enough of theory to direct and discipline it. But, above all, there is wanting genius.”
—Henry David Thoreau (1817–1862)
“I lay my eternal curse on whomsoever shall now or at any time hereafter make schoolbooks of my works and make me hated as Shakespeare is hated. My plays were not designed as instruments of torture. All the schools that lust after them get this answer, and will never get any other.”
—George Bernard Shaw (1856–1950)