Bloom filter for storage
There is a data structure called an "invertible Bloom filter" due to Goodrich and myself that can be used for storage: you can add and remove keys and, whenever the current number of keys is below the capacity of the structure, determine what they are with high probability (regardless of whether it was ever above capacity in the past). Goodrich and Mitzenmacher have generalized this to allow values to be associated with the keys as well.

However, one drawback to these structures is that they use quite a bit more space than a normal Bloom filter: basically, a logarithmic number of bits per key rather than a constant number of bits per key.

See 

Space-efficient straggler identification in round-trip data streams via Newton's identitities and invertible Bloom filters.
D. Eppstein, and M. T. Goodrich.
arXiv:0704.3313.
IEEE Trans. Knowledge and Data Engineering 23(2): 297-306, 2011.

and

Invertible Bloom Lookup Tables
Michael T. Goodrich, Michael Mitzenmacher
arXiv:1101.2245