User:Jorend/Deterministic hash tables: Difference between revisions

User:Jorend/Deterministic hash tables (view source)

823 bytes added , 24 February 2012

638

edits

@@ Line 81: / Line 81: @@
 All three implementations double the size of the table whenever it gets too full. On a log-log plot, this shows as stair-steps of a constant height. The slope of each staircase is 1, indicating linear growth.
-CloseTable is much more memory-efficient than DenseTable, because the latter is tuned for fast lookups at all costs.
+Both OpenTable and CloseTable are much more memory-efficient than DenseTable, because <code>dense_hash_map</code> is tuned for fast lookups at all costs.
+For any large enough number of entries ''N'', a CloseTable with ''N'' entries allocates '''either 1.125x or 2.25x as much memory''' as an OpenTable with ''N'' entries. Both tables double in size at certain thresholds, and the thresholds for CloseTable are lower than those for OpenTable. That is, as a CloseTable is populated, it doubles in size sooner than the corresponding OpenTable. This is because CloseTable entries are 50% larger, and it therefore takes fewer of them to fill up a power-of-two-sized allocation.
+(It is tempting to reduce this complicated picture to a single number, and write that CloseTables are, for example, 20% larger. Or 30%. But such a number would not be easily justified mathematically: the ratio does not converge as the number of entries increases.)
 [[Image:jorendorff-dht-figure-2.png]]