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:
“I am hungry and you give me
a dictionary to decipher.”
—Anne Sexton (1928–1974)
“Waiting for the race to become official, he began to feel as if he had as much effect on the final outcome of the operation as a single piece of a jumbo jigsaw puzzle has to its predetermined final design. Only the addition of the missing fragments of the puzzle would reveal if the picture was as he guessed it would be.”
—Stanley Kubrick (b. 1928)
“What, to the American slave, is your Fourth of July? I answer: A day that reveals to him, more than all other days in the year, the gross injustice and cruelty to which he is the constant victim. To him your celebration is a sham.”
—Frederick Douglass (c.1817–1895)
“The parent who loves his child dearly but asks for nothing in return might qualify as a saint, but he will not qualify as a parent. For a child who can claim love without meeting any of the obligations of love will be a self-centered child and many such children have grown up in our time to become petulant lovers and sullen marriage partners because the promise of unconditional love has not been fulfilled.”
—Selma H. Fraiberg (20th century)