In my earlier finite map benchmarks which compared several hash tables and functional maps (AVL trees and ternary trees), separate chaining (with $$\alpha = 0.47$$) beat double hashing ($$\alpha = 0.42$$) at unsuccessful searches (1% hit rate), but was slower at successful ones.
Theory predicts the following average number of probes for unsuccessful and successful lookups (expressions below): 
Separate chaining looks much better here, but the graphs are misleading, because we don't actually care as much about the load factor as about memory usage, so we want to compare the collision resolution schemes when the latter is the same.
If we use a linked list for the collision chain, this represents one word of overhead per item compared to double hashing. For instance, if the load factor with separate chaining is 1, we can afford to have a table twice as big with double hashing for the same amount of memory and a load factor of 50%. In other words, $$N + n = N'$$ where $$N$$ and $$N'$$ are the sizes of the tables for separate chaining and double hashing, and $$n$$ the number of elements. The respective load factors are
\[\begin{eqnarray*}
\alpha & = & \frac{n}{N}\\
\alpha' & = & \frac{n}{N'}\\
& = & \frac{n}{N+n}\\
\alpha' & = & \frac{\alpha}{1+\alpha}\end{eqnarray*}
\]The expressions for the average number of probes for unsuccessful and successful searches are (Knuth, TAOCP Vol 3, Section 6.4), for separate chaining
2009-07-02T13:22:19Z
The 24th of June, the 
![[RSS 1.0 Feed]](images/rss10.png){kind=small}
![[RSS 2.0 Feed]](images/rss20.png){kind=small}
![[FOAF Subscriptions]](images/foaf.png){kind=small}
![[OPML Subscriptions]](images/opml.png){kind=small}
