Wow, this is ambitious / tough :-)

My immediate thought is to have a look at the way MS has implemented their in-memory OLTP database technology. Essentially the idea is that every change is saved and linked through the use of timestamps. The current value of something is maintained and updated only upon completion of transactions. Its really memory intensive, however it is ACID and blisteringly fast.

Back to your requirements - Keeping a data set that maintains a record of transactions in time means that you can create an iterator that will return the contents of the hash as it existed at the time of the iterators creation, which I think would prevent a whole lot of these issues. Making your object time aware then gives you options that allow users of the object to select the behaviour (eg, let them choose if they want to iterate completely through the hash without anything updating, or iterate until the live hash was updated more than x milliseconds ago (or whatever other logic you want to have, such as keys deleted / added), or even iterate only over live data - When the iterator is invalidated is then controlled by the logic of the choice the user makes)