The best list that I could find, that has probabilistic data structures is this Wikipedia page. The problem here is, the page also includes probabilistic algorithms. The list that I know of is:
- Bloom Filter
- Random Tree - This is a general term, and "umbrellas" many different structures.
- Skip List
- Treap
There are probably many more, but these are the ones that I have found or that I was aware of.
Please leave a comment if there is anything that I missed.