Talk:Quadratic probing

suggestions

Write program for quadratic probing. Create a gif image to show the insertion and search. Proper formatting of page (wikify). abhijit13(talk) 07:06, 15 September 2011 (UTC)

Triangular numbers

Article contains oft-repeated garbage. Quadratic probing can be used with a power of two hash table, and it is guaranteed to find an empty slot. See http://www.chilton-computing.org.uk/acl/literature/reports/p012.htm — Preceding unsigned comment added by 70.69.216.248 (talk) 04:17, 12 April 2016 (UTC)

When Donald Knuth covered quadratic probing in The Art of Computer Programming, he noted that the triangular numbers completely cover any hash table of size 2^n. This doesn't seem to be mentioned in the article, though. Worth adding? Chris Purcell (talk) 20:01, 31 March 2018 (UTC)

(Replying to two comments at once.) @Chris Purcell: It was already in the article, although not well presented. Yes, it needs a lot of work; I've just been rearranging the deck chairs.

The proof for prime-modulus tables is overcomplex. It's easy to see that i and (m − i) ≡ −i have the same square mod m, so half of the possible indexes are redundant. Proving that there are no earlier cases can be written more simply than given. Suppose that i² ≡ j² (mod m). Therefore i² − j² = (i + j)(i − j) ≡ 0 (mod m).

If m is prime, this implies that either i − j ≡ 0 (mod m), meaning that i and j are equal, or i + j ≡ 0 (mod m), which is the case previously described. There are no other cases.

(If m is composite, there are more possibilities.)

The interesting one is the proof for triangular numbers. The Hopgood & Davenport proof covers both straight triangular numbers and triangular numbers with a linear offset. Let's see if I can work it out.

First, the straight triangular numbers case. Table size m = 2^t, offset = i*(i+1)/2, for i = 0, 1, 2....

Suppose that i*(i+1)/2 − j*(j+1)/2 ≡ 0 (mod 2^t), for i ≠ j.

i*(i+1)/2 − j*(j+1)/2 = 0.5 * (i^2 − j^2 + i − j) = 0.5 * (i − j) * (i + j + 1)

So (i − j) * (i + j + 1) / 2 ≡ 0 (mod 2^t)

So (i − j) * (i + j + 1) ≡ 0 (mod 2^t+1)

Now, of the two terms above, exactly one must be odd. Considered modulo 2, i + j ≡ i − j, and there are only two possible values, even and odd.

Therefore the even term must provide all of the powers of two requires. I.e. either

i − j ≡ 0 (mod 2^t+1), which can only be true if i = j, or

i + j + 1 ≡ 0 (mod 2^t+1).

In the latter case, the least i > j ≥ 0 which can satisfy this is i = 2^t = j + 1.

So the offset is distinct for 0 ≤ j < m, full period.

Apparently if you add c₁ − 1⁄2 ≠ 0, the period ends up being m − (c₁ − 1⁄2). It makes sense that the period is no longer than this, because the delta between offsets, c₁i + i²/2 − c₁(i−1) − (i−1)²/2 = c₁ + i − 1⁄2, reaches m then and causes a repeat.

The preceding proof can be worked through with the additional non-zero constant to prove that there are no earlier repeats.

TODO: Clean up the preceding and add it to the article. 196.247.24.12 (talk) 11:05, 7 March 2020 (UTC)

maintenance tags

C code (or Java, Python, etc) and even pseudo-code are how-to, and unless cited and faithful to the source (might be copyright issues), are original research. I think we we can delete this, as well as any uncited text, straight away and give this article (or what's left of it), a clean referenced start.Sbalfour (talk) 17:36, 18 September 2019 (UTC)

Ok, fixed, mostly. The problem now is referencing and sloppy diction. Sbalfour (talk) 18:00, 18 September 2019 (UTC)

India Education Program course assignment

This article was the subject of an educational assignment at College Of Engineering Pune supported by Wikipedia Ambassadors through the India Education Program during the 2011 Q3 term. Further details are available on the course page.

The above message was substituted from {{IEP assignment}} by PrimeBOT (talk) on 20:14, 1 February 2023 (UTC)