638
edits
User:Jorend/Deterministic hash tables: Difference between revisions
Jump to navigation
Jump to search
User:Jorend/Deterministic hash tables (view source)
Revision as of 01:07, 22 February 2012
, 22 February 2012no edit summary
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
= Abstract = | |||
A deterministic hash table proposed by Tyler Close was implemented in C++ and its performance was compared to two hash table implementations using open addressing. Speed and memory usage were measured. The Close table implementation was very fast, faster than the tables with open addressing. It uses more memory (up to 75% more). This is somewhat mitigated by the fact that, unlike a hash table with open addressing, the Close table can leave some of the memory it allocates uninitialized until it is needed. | A deterministic hash table proposed by Tyler Close was implemented in C++ and its performance was compared to two hash table implementations using open addressing. Speed and memory usage were measured. The Close table implementation was very fast, faster than the tables with open addressing. It uses more memory (up to 75% more). This is somewhat mitigated by the fact that, unlike a hash table with open addressing, the Close table can leave some of the memory it allocates uninitialized until it is needed. | ||
= Background = | |||
Most hash table APIs (including C++'s <code>unordered_map</code>, Java's <code>java.util.HashMap</code>, Python's <code>dict</code>, Ruby's <code>Hash</code>, and many others) allow users to iterate over all the entries in the hash table in an arbitrary order. This exposes the user to nondeterminism in the implementation. | Most hash table APIs (including C++'s <code>unordered_map</code>, Java's <code>java.util.HashMap</code>, Python's <code>dict</code>, Ruby's <code>Hash</code>, and many others) allow users to iterate over all the entries in the hash table in an arbitrary order. This exposes the user to nondeterminism in the implementation. | ||
| Line 12: | Line 12: | ||
= | = Method = | ||
| Line 18: | Line 18: | ||
Source code: https://github.com/jorendorff/dht | Source code: https://github.com/jorendorff/dht | ||
= Results = | |||
[[Image:jorendorff-dht-figure-1.png]] | [[Image:jorendorff-dht-figure-1.png]] | ||
[[Image:jorendorff-dht-figure-2.png]] | [[Image:jorendorff-dht-figure-2.png]] | ||