The best list that I could find, that has [probabilistic][1] [data structures][2] is [this Wikipedia page.][3] The problem here is, the page also includes probabilistic algorithms. The list that I know of is:

 - [Bloom Filter][4]
 - [Random Tree][5] - This is a general term, and "umbrellas" many different structures.
 - [Skip List][6]
 - [Treap][7]

There are probably many more, but these are the ones that I have found or that I was aware of.




  [1]: http://en.wikipedia.org/wiki/Randomized_algorithm
  [2]: http://en.wikipedia.org/wiki/Data_structure
  [3]: http://en.wikipedia.org/wiki/Category:Probabilistic_data_structures
  [4]: http://en.wikipedia.org/wiki/Bloom_filter
  [5]: http://en.wikipedia.org/wiki/Random_tree
  [6]: http://en.wikipedia.org/wiki/Skip_list
  [7]: http://en.wikipedia.org/wiki/Treap