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)
“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)
“For me, it is as though at every moment the actual world had completely lost its actuality. As though there was nothing there; as though there were no foundations for anything or as though it escaped us. Only one thing, however, is vividly present: the constant tearing of the veil of appearances; the constant destruction of everything in construction. Nothing holds together, everything falls apart.”
—Eugène Ionesco (b. 1912)
“...every woman who has any margin of time or money to spare should adopt some one public interest, some philanthropic undertaking, or some social agitation of reform, and give to that cause whatever time and work she may be able to afford ...”
—Frances Power Cobbe (1822–1904)