Quadratic Probing - Quadratic Function

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:

    “Our father has an even more important function than modeling manhood for us. He is also the authority to let us relax the requirements of the masculine model: if our father accepts us, then that declares us masculine enough to join the company of men. We, in effect, have our diploma in masculinity and can go on to develop other skills.”
    —Frank Pittman (20th century)