Implement a hash map with chaining, then replace each chain with a treap. How does a treap's expected O(log n) differ from the strict O(log n) of a balanced tree?

Implement a hash map that resolves collisions by chaining, then replace each chain with a treap. Which balancing schemes exist, and what is the difference between an expected O(log n) treap and a strictly O(log n) balanced tree?