In this paper we analyze the performance of a well known algorithm known as double hashing [Knuth]. In this method we probe the hash table along arithmetic progressions, where both the initial element and the increment of the progression are chosen randomly and independently depending only on the key K of the search. We prove that double hashing is asymptotically equivalent to uniform probing, an idealized hashing technique that exhibits no clustering and is known to be optimal in a certain sense. Between steps of the extension process we can show that the effect of clustering is negligible, and that we therefore never depart too far from the truly random situation.