Only quadratic speedup for most problems, like search. That's why hash functions with key size 256 or higher are safe, for example.