3

I have been learning about Hash Tables lately. There are a couple of examples of Collision Resolutions and one of them is Quadratic probing.Why would someone use quadratic probing? Does he know that the hash table will always be less than half full? And if so why does he use such a big table to begin with?

Danny Beckett
  • 20,529
  • 24
  • 107
  • 134
user2278279
  • 65
  • 1
  • 7

2 Answers2

2

Why would someone use quadratic probing?

Assuming we need some collision resolution algorithm,

Quadratic probing can be a more efficient algorithm in a closed hash table, since it better avoids the clustering problem that can occur with linear probing, although it is not immune.

(From Wikipedia)

Quadratic probing isn't perfect, but it does offer some advantages over alternatives:

The advantages of quadratic (or other forms of) chaining are

  • simpler logic for storage management (no dynamic allocation)
  • faster inserts (for reason of simpler storage)
  • reduced storage requirement in general

(from mjv's answer)

Does he know that the hash table will always be less than half full?

Not necessarily; it depends on the resizing strategy used, if any.

Consider your learning on QP to be primarily educational. Practical hash table implementations don't often use open addressing, in my experience.

Community
  • 1
  • 1
Matt Ball
  • 354,903
  • 100
  • 647
  • 710
  • 1
    Oh ok, so you can start with whatever size you want and whenever it gets more than half full resize the table. Wouldn't that be a waste of space? Wouldn't it be better to change the hashing function? – user2278279 Apr 13 '13 at 20:55
  • @user2278279- This wouldn't waste too much space. Usually, you have no more than 4x more space than you need, since any time you have 2x space you double the table size. This is a fairly standard implementation. – templatetypedef Apr 13 '13 at 21:01
  • Now I understand. It would depend on how you implement the hash table, if you use an array of pointer then twice as many pointers isn't that bad compared to how simple the hashing function is, but if you use an array of big objects then you would be wasting space. – user2278279 Apr 13 '13 at 21:09
  • Of course it depends on that `:)` quadratic probing is an implementation detail. – Matt Ball Apr 13 '13 at 21:31
1

Quadratic rehash is a very simple and fast way to avoid the clustering problem of linear hash. It's normally used only when table size is prime (which may also be good for other reasons).

To avoid any worry about "table being half-full" it is simplest to switch to linear probe at some point. (You can put the threshold test for such switching inside the usual if (index >= size) {index -= size;} block, to avoid any performance loss.

James Dow Allen
  • 11
  • 1