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.
I 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.
Ooh 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.
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.