3 ms·
I think LRU does NOT work with this trick, because there's no easy way to "move-to-front" in O(1) time. The article mentions Java's LinkedHashMap, which actual
by marvy 5y ago
I think LRU does NOT work with this trick, because there's no easy way to "move-to-front" in O(1) time.
The article mentions Java's LinkedHashMap, which actually can do LRU. But as the name implies, they rely on a linked list, where move=to-front is natural.
But this superpower does not come for free: a Java-style linked hash map will use more memory than the technique described in the article.
- ErikCorry 5y agoI think you can move to front by removing the entry and then adding it again. This won't be O(1) currently, but with the tombstone trick from my blog post I think it would be.
- deleted 5y ago[deleted]
- marvy 5y agoOoh nice! I didn't think of that! Since appending to an array is cheap, you can just move-to-end instead of move-to-front, and then iterate in "reverse" order, so from the outside everything seems to Just Work.