638
edits
Changes
→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, 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. The implementation can probably trade speed for compactness, but again, more investigation is needed.
= Background =
