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?
The difference in processing cost between the two approaches are that of
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
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.
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).
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.