I don't think it directly relates to your problem, but it reminds me of Strings and numbers: losing memory and mind. In that case, my large data structure started out as strings and was converted to numbers on the fly as I used it. That caused a lot more memory usage after the point where I thought it would be static. Maybe your data structure is experiencing a similar "one time cost" as it's accessed.