I had a similar problem in the past and I have considered a similar solution.
However, I ended up using one custom fixed size hash table with open addressing. Idea is that table once filled up, start throwing away one element everytime another one needs to be inserted. Table doesn't ever grow. It was not as generic and it was O(1) just for a subset of operations, but it was much faster. Answer: it depends on what operations you are going to use most. I ended up inserting in 99.99999% cases, no del, no lookup.
