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)
“Human knowledge and human power meet in one; for where the cause is not known the effect cannot be produced. Nature to be commanded must be obeyed; and that which in contemplation is as the cause is in operation as the rule.”
—Francis Bacon (1560–1626)
“But when with moving accents thou
Shalt constant faith and service vow,
Thy Celia shall receive those charms
With open ears, and with unfolded arms.”
—Thomas Carew (1589–1639)
“An entertainment is something which distracts us or diverts us from the routine of daily life. It makes us for the time being forget our cares and worries; it interrupts our conscious thoughts and habits, rests our nerves and minds, though it may incidentally exhaust our bodies. Art, on the other hand, though it may divert us from the normal routine of our existence, causes us in some way or other to become conscious of that existence.”
—Sir Herbert Read (1893–1968)