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 15:07, 23 February 2012
, 23 February 2012→Abstract
(→Method) |
|||
| 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; theory suggests it "should" be slower, and measurement confirms that the Close table is doing more memory accesses and more branches. More investigation is needed | '''Speed.''' The Close table implementation was very fast, faster than the open addressing implementations. (It is unclear why; theory suggests it "should" be slower, and measurement confirms that the Close table is doing more memory accesses and more branches. More investigation is needed!) | ||
'''Memory.''' The Close table implementation allocates 29% more memory on average than the leanest open addressing implementation on 32-bit systems, 37% more on 64-bit systems | '''Memory.''' The Close table implementation allocates 29% more memory on average than the leanest open addressing implementation on 32-bit systems, 37% more on 64-bit systems. | ||
= Background = | = Background = | ||