638
edits
User:Jorend/Deterministic hash tables: Difference between revisions
User:Jorend/Deterministic hash tables (view source)
Revision as of 19:13, 27 February 2012
, 27 February 2012→Theory: fmt
m (→Theory: fmt) |
|||
| Line 52: | Line 52: | ||
In an open addressing hash table with fill factor ''f'', an unsuccessful lookup performs about ''1/(1-f)'' probes.[https://en.wikipedia.org/wiki/Hash_table#Performance_analysis] In an <code>OpenTable</code>, at worst ''f=F=3/4'' and so an unsuccessful lookup performs 4 probes on average. In the usual case, ''f=3F/4=9/16'', so about 2.3 probes on average. | In an open addressing hash table with fill factor ''f'', an unsuccessful lookup performs about ''1/(1-f)'' probes.[https://en.wikipedia.org/wiki/Hash_table#Performance_analysis] In an <code>OpenTable</code>, at worst ''f=F=3/4'' and so an unsuccessful lookup performs 4 probes on average. In the usual case, ''f=3F/4=9/16'', so about 2.3 probes on average. | ||
<table> | <table class="data"> | ||
<tr> | <tr> | ||
<th rowspan=2>Data structure</th> | <th rowspan=2>Data structure</th> | ||