A new dynamic Interpolation Search (IS) data structure is presented that achieves O(log log n) search time with high probability on unknown continuous or even discrete input distributions with mea- surable probability of key collisions, including power law and Binomial distributions. No such previous result holds for IS when the probabil- ity of key collisions is measurable. Moreover, our data structure exhibits O(1) expected search time with high probability for a wide class of in- put distributions that contains all those for which o(log log n) expected search time was previously known.