User:Jorend/Deterministic hash tables: Difference between revisions
| Line 3: | Line 3: | ||
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. | 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. | ||
'''Speed.''' The Close table implementation was very fast, faster than the open addressing implementations. (It is unclear why | '''Speed.''' The Close table implementation was very fast, faster than the open addressing implementations. (It is unclear why; theory suggests it "should" be slower. More investigation is needed.) | ||
'''Memory.''' The Close table allocates | '''Memory.''' The Close table implementation allocates 37% more memory on average than the leanest open addressing implementation. (The implementation can probably trade speed for compactness, but again, more investigation is needed.) | ||
= Background = | = Background = | ||
Revision as of 20:25, 22 February 2012
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.
Speed. The Close table implementation was very fast, faster than the open addressing implementations. (It is unclear why; theory suggests it "should" be slower. More investigation is needed.)
Memory. The Close table implementation allocates 37% more memory on average than the leanest open addressing implementation. (The implementation can probably trade speed for compactness, but again, more investigation is needed.)
Background
Most hash table APIs (including C++'s unordered_map, Java's java.util.HashMap, Python's dict, Ruby's Hash, 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.
Map and Set data structures are proposed for a future version of the ECMAScript programming language. The standard committee would like to avoid underspecification if possible. Can a data structure retain the performance of traditional, arbitrary-order hash tables while also storing the order in which entries were added, so that iteration is deterministic?
...
Method
Source code: https://github.com/jorendorff/dht
Results
