Hacker News Reader

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.

View on HN

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.

Reply on news.ycombinator.com