Quadratic Function
Let h(k) be a hash function that maps an element k to an integer in, where m is the size of the table. Let the ith probe position for a value k be given by the function
where c2 ≠ 0. If c2 = 0, then h(k,i) degrades to a linear probe. For a given hash table, the values of c1 and c2 remain constant.
Examples:
- If, then the probe sequence will be
- For m = 2n, a good choice for the constants are c1 = c2 = 1/2, as the values of h(k,i) for i in are all distinct. This leads to a probe sequence of where the values increase by 1, 2, 3, ...
- For prime m > 2, most choices of c1 and c2 will make h(k,i) distinct for i in . Such choices include c1 = c2 = 1/2, c1 = c2 = 1, and c1 = 0, c2 = 1. Because there are only about m/2 distinct probes for a given element, it is difficult to guarantee that insertions will succeed when the load factor is > 1/2.
Read more about this topic: Quadratic Probing
Famous quotes containing the word function:
“As a medium of exchange,... worrying regulates intimacy, and it is often an appropriate response to ordinary demands that begin to feel excessive. But from a modernized Freudian view, worrying—as a reflex response to demand—never puts the self or the objects of its interest into question, and that is precisely its function in psychic life. It domesticates self-doubt.”
—Adam Phillips, British child psychoanalyst. “Worrying and Its Discontents,” in On Kissing, Tickling, and Being Bored, p. 58, Harvard University Press (1993)