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
  • 113 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by Narue
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.