My introduction to probabilistic data structures was Pugh's skip list, which is probabilistic in structure and performance, but precise with answers.