I wrote GrabBag as a datastructure to hold genetically evolving programs (see OGPF). Unlike most collections, this one assumes that when you add an element you don't care where it goes (unordered insertion) and that when you pull out an element you specifically want a uniformly random element.

See the grabbag directory for the source code (GPLed unless you talk to me).

This particular implementation is based on a binary tree which keeps track of how many leaves it has on both its left and right side (the actual data is stored in the leaves). This makes it easy to find the size -- you just add those two numbers from the root of the tree. To grab something at random we take the size (total number of things we have), pick a random number up to that. Then we start at the root... if the number is bigger than the left, we go right and so on until we find the node and pull it out. We make a note of the removal by subtraction on the way back out. 2^n nodes can thus be accessed in 2*n operations (which is equivalent to O(ln n) I believe). Adding works similarly -- we move down the tree finding out where it is lopsided and add the new thingie there, thereby keeping things pretty even.