A standard Hash Map (or dictionary) is a foundational data structure that maps keys to values, allowing for quick and efficient data retrieval. But what happens if your application needs to access a previous state of that data?
Enter the Time-Travelling HashMap. This specialized data structure not only stores values but also retains multiple versions of values for the same key based on their insertion time. By providing a key and a specific timestamp, you can "travel back in time" to see exactly what the value was at that given moment.
The Core Requirements
According to the design guidelines, a time-traveling hash map must meet a few specific functional requirements:
-
Constant Time Insertion: The map must be able to insert values in constant time (
O(1)), and the time recorded for each entry is its exact insertion time. -
Time-Based Retrieval: When executing a
get(K, t)query, the hash table must return the value exactly as it would have appeared if you were querying the map at timetin the past (before more recent values were added). -
Closest Past Value Fallback: It is highly unlikely that a query will match the exact millisecond a value was inserted. Therefore, if the exact time
tdoes not exist, the map must return the closest past timet'that is smaller thant. For example, if a map receives updates for a key at time1and time2, a query requesting the value at time1.5should return the value from time1.
Under the Hood: The JavaScript Implementation
The provided JavaScript implementation achieves this time-traveling behavior by creatively wrapping native JavaScript Map objects.
1. Data Structures
The TimeTravellingHashMap class uses two internal maps to keep track of data:
-
_map: A standardMapthat stores the actual values. It uses a generated "composite key" (a combination of the base key and the timestamp) to ensure no values are overwritten. -
_keyLookUpTable: This acts as a historical ledger. It maps a standard base key to an array containing all the composite keys (versions) associated with it.
2. Recording Data (The set Method)
When a new key-value pair is set, the class generates a composite key by concatenating the original key, a unique separator (utilizing a JavaScript Symbol), and the current ISO string timestamp.
The value is then saved in _map using this new composite key. Crucially, this composite key is also appended to the history array for that base key inside the _keyLookUpTable. Because new keys are pushed to the end of the array, the lookup table naturally remains sorted chronologically.
3. Time Traveling (The get Method)
The get method handles the logic of looking into the past. It first creates a composite key using the requested time. If an exact match exists in the _map, it is returned immediately.
If there is no exact match, the map performs its fallback logic:
- It retrieves the chronological array of composite keys for the requested base key from the
_keyLookUpTable. - It iterates backward through this array (starting from the most recent entry).
- It compares the timestamp of each historical entry against the requested time using a custom
_getTimeFromKeyWithTimehelper method. - As soon as it finds a timestamp that is less than or equal to the requested time, the loop stops, and the corresponding historical value is returned.
Testing the Implementation
To prove that the hash map accurately tracks time, the implementation uses asynchronous JavaScript (setTimeout) to simulate the real-world passage of time.
In the test suite, an initial key is set to "v1", and shortly after, a timestamp variable (timeToRound) is captured. Later on, the same key is overwritten with "v2". Finally, a query is made using the captured timeToRound timestamp. Because the requested time occurred before "v2" was inserted, the map successfully ignores the newer entry and travels back to return "v1", proving the logic works perfectly.
Conclusion
The Time-Traveling HashMap is an excellent exercise in understanding state management and historical data tracking. By using composite keys and a chronological ledger, developers can create reliable structures capable of version control, undo/redo features, and complex historical data querying, all without permanently overwriting older states.
Top comments (0)