User:Jorend/Deterministic hash tables: Difference between revisions

Jump to navigation Jump to search

User:Jorend/Deterministic hash tables (view source)

Revision as of 21:10, 27 February 2012

933 bytes removed ,  27 February 2012
→‎Theory: remove extra table, it doesn't really help
(→‎Theory: remove extra table, it doesn't really help)
Line 48: Line 48:
For back-of-envelope purposes, then, ''f'' may be expected to be about ''3F/4'' (halfway between F/2 and F) and ''u'' about 3/4 on average; plugging these numbers in, we expect an <code>OpenTable</code> to use about (1/(3F/4)) = 1.78&times;''NE'', and a <code>CloseTable</code> about 2.13&times;''NE'' (2.25&times;''NE'' on 64-bit), on average. This would mean that the <code>CloseTable</code> would be 20% larger on average (27% larger on 64-bit). However, see the Results section for a picture of how the two implementations compare in practice.
For back-of-envelope purposes, then, ''f'' may be expected to be about ''3F/4'' (halfway between F/2 and F) and ''u'' about 3/4 on average; plugging these numbers in, we expect an <code>OpenTable</code> to use about (1/(3F/4)) = 1.78&times;''NE'', and a <code>CloseTable</code> about 2.13&times;''NE'' (2.25&times;''NE'' on 64-bit), on average. This would mean that the <code>CloseTable</code> would be 20% larger on average (27% larger on 64-bit). However, see the Results section for a picture of how the two implementations compare in practice.


'''Speed.''' We consider the speed of lookups only. The <code>get</code>, <code>has</code>, <code>set</code>, and <code>delete</code> operations all start with a lookup. We will quantify the speed of lookups in terms of how many memory locations must be accessed. To simulate locality effects, we treat multiple reads from a single entry, or from the table object, as a single read.
'''Lookup speed.''' The <code>get</code>, <code>has</code>, <code>set</code>, and <code>delete</code> operations all start with a lookup. We will quantify lookup speed in terms of how many memory locations must be accessed. To simulate locality effects, we treat multiple reads from a single entry, or from the table object, as a single read.
 
<table class="data">
  <tr>
    <th colspan=3>Number of collisions</th>
    <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;0&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</td>
    <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</td>
    <td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;2&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</td>
  </tr>
  <tr>
    <th rowspan=4>Number of reads</th>
    <th rowspan=2>Unsuccessful lookup (miss)</th>
    <th><code>OpenTable</code></th>
    <td>2</td>
    <td>3</td>
    <td>4</td>
  </tr>
  <tr>
    <th><code>CloseTable</code></th>
    <td>2</td>
    <td>3</td>
    <td>4</td>
  </tr>
  <tr>
    <th rowspan=2>Successful lookup (hit)</th>
    <th><code>OpenTable</code></th>
    <td>2</td>
    <td>2 to 3</td>
    <td>2 to 4</td>
  </tr>
  <tr>
    <th><code>CloseTable</code></th>
    <td>3</td>
    <td>3 to 4</td>
    <td>3 to 5</td>
  </tr>
</table>


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. A successful lookup performs half as many probes on average. Before probing the table, the lookup must access the <code>OpenTable</code> struct itself, so the final numbers are as shown in the table: 5 reads, 3.3 reads, etc.
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. A successful lookup performs half as many probes on average. Before probing the table, the lookup must access the <code>OpenTable</code> struct itself, so the final numbers are as shown in the table: 5 reads, 3.3 reads, etc.
Jorend
638

edits

Retrieved from "https://wiki.mozilla.org/Special:MobileDiff/401468"

Navigation menu