There are resizing algorithms out there which specifically avoid the single-insertion-spike that you're worried about. http://stackoverflow.com/a/2200345 http:

There are resizing algorithms out there which specifically avoid the single-insertion-spike that you're worried about. http://stackoverflow.com/a/2200345 http://stackoverflow.com/a/2200345 If you're working with small data sizes, the difference between O(1) and O(lgN) isn't that big a deal, so you can use whatever you want. But once you start working with larger datasets containing millions of elements, and the only thing you care about is insertions and exact-match-lookups, it's hard to justify using a tree over a hash map.