Limitations
For linear probing it is a bad idea to let the hash table get nearly full, because performance is degraded as the hash table gets filled. In the case of quadratic probing, the situation is even more drastic. With the exception of the triangular number case for a power-of-two-sized hash table, there is no guarantee of finding an empty cell once the table gets more than half full, or even before the table gets half full if the table size is not prime. This is because at most half of the table can be used as alternative locations to resolve collisions. If the hash table size is b (a prime greater than 3), it can be proven that the first alternative locations including the initial location h(k) are all distinct and unique. Suppose, we assume two of the alternative locations to be given by and, where 0 ≤ x, y ≤ (b / 2). If these two locations point to the same key space, but x ≠ y. Then the following would have to be true,
As b (table size) is a prime greater than 3, either (x - y) or (x + y) has to be equal to zero. Since x and y are unique, (x - y) cannot be zero. Also, since 0 ≤ x, y ≤ (b / 2), (x + y) cannot be zero.
Thus, by contradiction, it can be said that the first (b / 2) alternative locations after h(k) are unique. So an empty key space can always be found as long as at most (b / 2) locations are filled, i.e., the hash table is not more than half full.
Read more about this topic: Quadratic Probing
Famous quotes containing the word limitations:
“That all may be so, but when I begin to exercise that power I am not conscious of the power, but only of the limitations imposed on me.”
—William Howard Taft (1857–1930)
“Much of what contrives to create critical moments in parenting stems from a fundamental misunderstanding as to what the child is capable of at any given age. If a parent misjudges a child’s limitations as well as his own abilities, the potential exists for unreasonable expectations, frustration, disappointment and an unrealistic belief that what the child really needs is to be punished.”
—Lawrence Balter (20th century)
“No man could bring himself to reveal his true character, and, above all, his true limitations as a citizen and a Christian, his true meannesses, his true imbecilities, to his friends, or even to his wife. Honest autobiography is therefore a contradiction in terms: the moment a man considers himself, even in petto, he tries to gild and fresco himself.”
—H.L. (Henry Lewis)