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.
