Collision Resolution : Quadratic Probing vs. Separate Chaining

Question

Ok, so I've been doing some experiments with hash tables and different collision resolution problems. I'm trying to figure out which is more efficient for doing finds, a hash table that uses separate chaining or quadratic probing for collision resolution. My results suggest that separate chaining is faster than quadratic probing even for small load factors such as 0.4 or 0.2. Is this the case or are my results wrong?

Answer 1

The difference in processing cost between the two approaches are that of
  (with chaining)
  - an indirection, i.e. pointer dereferencing
vs.
  (with quadratic probing)
  - evaluation of a [simple but composite] arithmetic formula
  - indexing to the new location
  - possible repeats thereof (due to collision between the probe value and non-target values stored at these locations; something chaining doesn't have to worry about.

It should therefore be little surprise that chaining is faster; pointer dereferencing is a "native" instruction of most CPUs, comparable (identical in most cases) to that of indexing into the array, leaving the arithmetic operations and possible collisions as overhead in disfavor of probing. The simplest of probing sequence's formula will require a few CPU instructions (initialize stepNr, typically some shifting of the stepNr, adding to current location/probe) which in of itself is readily several times slower than pointer dereferencing. (Poss. caveat: please see 'Edit' shortly thereafter, as it discusses how chaining may incur more CPU-level cache misses hence making it less efficient than linear probing)

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

Thinking about this Space vs. Speed (or also Insert-time vs. Search-time) compromise in very broad terms, the storage overhead of chaining (mostly for the pointers themselves, not considering possible heap-management overhead) is used for storing pre-calculated values of [what would be with probing] "probe locations". Since these calculations are readily done, the chaining approach is faster at search-time.
Edit (thanks, Ants Aasma)
A caveat to this argument [about pre-calculated locations] is that on modern CPUs and their caches, the cost of running a small calculation can be much less than that of accessing [data] memory when the cache misses. This suggests that probing sequentially (or more generally with probing functions which produce locations physically close to the collision spot) could outperform a chaining strategy because of the lower ratio of cache misses. In this light, the purely sequential probing approach is the best of the probing functions, because of its very simple calculation but more importantly because it maximizes the odds of cache hits. With this in mind, when the hash function has a good distribution and the load factor is small (hence with a short/local search path past an initial collision) one should experiment with a linear (or very local) probing approach; one should however avoid probing functions which provide a search path that's not physically local.

---

It is hard to comment specifically on the experiment mentioned in the question, for example not knowing the size of the hash (if this size matches that of words/registers in the CPU, the arithmetic can be faster), or not knowing the collision ratio (let's assume a good, well distributed hash function).
As you keep experimenting with this it would be interesting to gather a separate set of timings/statistics for accessing items with their hash-slot vs. the ones that produced a collision.

The "even" in "...even for small load factors..." indicates your expectation that the relative advantage of chaining should further increase with the load, hence as the collisions become more numerous. I too expect this to would be the case.
Furthermore, increasing the load may illustrate yet another drawback of probing: cases when probing cycles and/or more generally when there's no room to fit a particular item.