Member Avatar for btech

I have a question about hashing. If you have a hash table that is 101 in size. and the items are inserted into the table using quadratic probing. I want to insert a new item with address 30. If position 30 in the hash table is occupied and the next 4 positions are also occupied, where in the table will the item be inserted.

If I understand quadratic hashing The first rehash adds 1 to HashValue, the second rehash adds 4, and the third rehash adds 9, and so on. So my question is would the position be 39?

  • 2 Contributors
  • 3 Replies
  • 127 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by Narue

Dani AI

Generated

Short answer for : quadratic probing does not check every consecutive index. It checks slots using the squared offset sequence (index = (h + i*i) mod N). For a table of size 101 and h = 30 the probes after the initial slot are (i = 1,2,3,4 ...): 31, 34, 39, 46, 55, ... So you land at 39 only if the earlier quadratic probes it would examine (31 and 34 in this case) are also occupied. If 31 is free you insert there; if 31 is occupied but 34 is free you insert at 34; only if both are occupied will 39 be tried next.

Concrete insertion pseudocode (common convention: try i = 0 first):

function insert(key):
    h = hash(key) % N
    for i from 0 to N-1:
        idx = (h + i*i) % N
        if slot[idx] is empty or deleted:
            slot[idx] = key
            return true
    return false   # no reachable empty slot

Notes and practical tips:

  • The phrase "next 4 positions are occupied" usually means contiguous slots; quadratic probing frequently skips some of those, so that phrase alone doesn't determine the result.
  • With the simple i^2 probe you only generate about half the distinct offsets modulo a prime table size, so high load factors can prevent finding a free slot even when the table is not full. For more robustness use double hashing or separate chaining.
  • If using a variant with coefficients (c1i + c2i^2), recompute the probe sequence accordingly.

Further reading: Quadratic probing and Open addressing. This clarifies the mismatch between s expectation and s earlier explanation.

Recommended Answers

All 3 Replies

Member Avatar for Narue

Quadratic probing uses a quadratically growing increment that's added to the address. So if you have address 30, you would start with an increment of 1. If 31 is occupied, you square the increment to 2 and try address 33. If 33 is occupied, you square the increment to 4 for address 37, then to 16 for address 53, then to 256 for address 309. But because that would be well beyond the limits of the table, you wrap around and around until you've shucked off the extra numbers and that would give you address 6. Repeat as necessary, but if you get too many collisions, the table is probably too full to be efficient.

In fact, quadratic probing isn't guaranteed to work if the load factor of the table exceeds .5, and the table size has to be prime in this resolution scheme. You would be better off using double hashing if you have a choice.

Member Avatar for btech

Quadratic probing uses a quadratically growing increment that's added to the address. So if you have address 30, you would start with an increment of 1. If 31 is occupied, you square the increment to 2 and try address 33. If 33 is occupied, you square the increment to 4 for address 37, then to 16 for address 53, then to 256 for address 309. But because that would be well beyond the limits of the table, you wrap around and around until you've shucked off the extra numbers and that would give you address 6. Repeat as necessary, but if you get too many collisions, the table is probably too full to be efficient.

Then from what you are saying the item "30" will be inserted into position 53. Is this correct?

Member Avatar for Narue

>Then from what you are saying the item "30" will be inserted into position 53.
Maybe, but judging from your description, if address 30 is occupied and the next four indices are also occupied (even though only two of them will be checked), the next possible choice would be 37. Read my description a few more times. You still seem to be confused.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.