638
edits
Changes
→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.
<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?
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 =
