Editing Double hashing (section)

== Analysis ==

Let <math>n</math> be the number of elements stored in <math>T</math>, then <math>T</math>'s load factor is <math>\alpha = n/|T|</math>.  That is, start by randomly, uniformly and independently selecting two [[universal hash]] functions <math>h_1</math> and <math>h_2</math> to build a double hashing table <math>T</math>. All elements are put in <math>T</math> by double hashing using <math>h_1</math> and <math>h_2</math>.
Given a key <math>k</math>, the <math>(i+1)</math>-st hash location is computed by:

<math display=block> h(i,k) = ( h_1(k) + i \cdot h_2(k) ) \bmod |T|.</math>

Let <math>T</math> have fixed load factor <math>\alpha: 1 > \alpha > 0</math>.
Bradford and [[Michael N. Katehakis|Katehakis]]<ref>{{citation
 | last1 = Bradford | first1 = Phillip G.
 | last2 = Katehakis | first2 = Michael N. | author2-link = Michael N. Katehakis
 | doi = 10.1137/S009753970444630X
 | journal = SIAM Journal on Computing
 | volume = 37
 | issue = 1
 | pages = 83–111
 | date = April 2007
 | mr = 2306284
 | title = A Probabilistic Study on Combinatorial Expanders and Hashing
 | url = http://phillipbradford.com/papers/AProbStudyExpandersAndHashing.pdf
 | archive-url = https://web.archive.org/web/20160125172602/http://phillipbradford.com/papers/AProbStudyExpandersAndHashing.pdf
 | archive-date = 2016-01-25
}}.</ref>
showed the expected number of probes for an unsuccessful search in <math>T</math>, still using these initially chosen hash functions, is <math>\tfrac{1}{1-\alpha}</math> regardless of the distribution of the inputs. Pair-wise independence of the hash functions suffices.

Like all other forms of open addressing, double hashing becomes linear as the hash table approaches maximum capacity. The usual heuristic is to limit the table loading to 75% of capacity.  Eventually, rehashing to a larger size will be necessary, as with all other open addressing schemes.