Timeline for What is a TrieMap and what is its advantages/disadvantages compared to a HashMap?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 12, 2021 at 15:16 | comment | added | axel22 |
The get is never O(1) in the standard Scala TrieMap - it's always expected O(log n), but with a low constant factor (because the nodes are very wide). This is the case both with and without lazy duplication. The similar data structure that has expected O(1) operations is called cache-trie: dl.acm.org/doi/abs/10.1145/3178487.3178498 (but this is not implemented in the Scala stdlib, it's available on github as a standalone repo) If you added snapshots to cache-tries, the get before duplication would be O(1), but after the duplication, it would briefly be O(log n).
|
|
| Apr 11, 2021 at 2:27 | comment | added | cpchung |
What will be the run time complexity for this lazy duplication before the actual get()? and what will be the run time complexity for the get() after the lazy duplication?
|
|
| Apr 11, 2021 at 2:18 | comment | added | cpchung |
@axel22 the relevant parts of the TrieMap will be lazily duplicated. Does that mean when the key is accessed from the clone/snapshot, it is no longer O(1) get() as in hashmap? What will be the run time complexity for this lazy duplication? the height of the underlying tree like O(lgN)?
|
|
| Apr 4, 2021 at 10:29 | comment | added | axel22 |
The new snapshot (i.e. clone) of the TrieMap will be created in a constant amount of time (i.e. in the same amount of time independent of how many keys you stored). Later, when you try to access some of the keys in that snapshot or in the original TrieMap, the relevant parts of the TrieMap will be lazily duplicated.
|
|
| Apr 1, 2021 at 17:46 | comment | added | cpchung |
@axel22 trying to get you attention here to explain how to use snapshot properly: stackoverflow.com/questions/66897678/… Basically I am trying to understand how is O(1) time snapshot operation interpreted.
|
|
| Oct 11, 2016 at 19:24 | vote | accept | Pinch | ||
| Aug 1, 2016 at 22:04 | comment | added | Pinch | Slightly unrelated, but there is a open-source port of the scale TrieMap to Java available: github.com/romix/java-concurrent-hash-trie-map. | |
| Aug 1, 2016 at 13:26 | history | answered | axel22 | CC BY-SA 3.0 |