638
edits
User:Jorend/Deterministic hash tables: Difference between revisions
Jump to navigation
Jump to search
m
User:Jorend/Deterministic hash tables (view source)
Revision as of 19:46, 27 February 2012
, 27 February 2012→Theory: fmt
(→Theory) |
m (→Theory: fmt) |
||
| Line 46: | Line 46: | ||
A Close table has three sources of overhead: the entire <code>hashTable</code>, the <code>chain</code> pointers in the <code>dataTable</code>, and the unused portion of the <code>dataTable</code>. In <code>CloseTable</code>, the <code>chain</code> pointer causes each entry to require ''(3/2)E'' memory rather than ''E''. The <code>dataTable</code> doubles in size when it becomes completely full, so its size is ''(3/2)(1/u)NE'' where ''u'' is the proportion of the <code>dataTable</code> that is in use and ''1/2 < u ≤ 1''. The <code>hashTable</code> is always 1/16 the size of the <code>dataTable</code> (1/8 on 64-bit platforms), so the total size of both tables is ''(1+1/16)(3/2)(1/u)NE'' (substitute 1/8 on 64-bit platforms). | A Close table has three sources of overhead: the entire <code>hashTable</code>, the <code>chain</code> pointers in the <code>dataTable</code>, and the unused portion of the <code>dataTable</code>. In <code>CloseTable</code>, the <code>chain</code> pointer causes each entry to require ''(3/2)E'' memory rather than ''E''. The <code>dataTable</code> doubles in size when it becomes completely full, so its size is ''(3/2)(1/u)NE'' where ''u'' is the proportion of the <code>dataTable</code> that is in use and ''1/2 < u ≤ 1''. The <code>hashTable</code> is always 1/16 the size of the <code>dataTable</code> (1/8 on 64-bit platforms), so the total size of both tables is ''(1+1/16)(3/2)(1/u)NE'' (substitute 1/8 on 64-bit platforms). | ||
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 have about (1/(3F/4))& | 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 have about (1/(3F/4))×100% - 100% = 78% memory overhead, and a <code>CloseTable</code> about 113% (125% 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. | '''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. | ||
| Line 56: | Line 56: | ||
<table class="data"> | <table class="data"> | ||
<tr> | <tr> | ||
<th | <th></th> | ||
<th colspan=2>Expected cost of unsuccessful lookup (miss)</th> | <th colspan=2>Expected cost of unsuccessful lookup (miss)</th> | ||
<th colspan=2>Expected cost of successful lookup (hit)</th> | <th colspan=2>Expected cost of successful lookup (hit)</th> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<th>Data structure</th> | |||
<th>Maximum load</th> | <th>Maximum load</th> | ||
<th>Typical load</th> | <th>Typical load</th> | ||