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:23, 23 February 2012
, 23 February 2012→Background
| Line 11: | Line 11: | ||
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. | ||
<code>Map</code> and <code>Set</code> 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? | <code>Map</code> and <code>Set</code> 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 order is deterministic? | ||
Tyler Close has developed a nondeterministic hash table that is structured like this (pseudocode): | |||
struct Entry { | |||
Key key; | |||
Value value; | |||
Entry *chain; | |||
} | |||
class CloseTable { | |||
Entry*[] hashTable; // array of pointers into the data table | |||
Entry[] dataTable; | |||
} | |||
Lookups and inserts proceed much like a bucket-and-chain hash table, but instead of each entry being allocated separately from the heap, they are stored in the <code>dataTable</code> in insertion order. | |||
Removing an entry simply replaces its <code>key</code> with some sentinel while leaving the <code>chain</code> intact. | |||
= Method = | = Method = | ||