That's addressed in that very section: > Moreover, an adversary can try to increase a number of necessary rehashes. It seems to me that the section is a bit t

That's addressed in that very section: > Moreover, an adversary can try to increase a number of necessary rehashes. It seems to me that the section is a bit too dismissive, though, as there are hash tables and hash functions that mitigate these concerns. In particular, collisions can be replaced with trees, like in Java, limiting the worst case to O(log n) again.