User: Password:
Subscribe / Log in / New account

Worst case performance and "impossibly unlikely" conditions

Worst case performance and "impossibly unlikely" conditions

Posted Jan 13, 2012 20:53 UTC (Fri) by jzbiciak (subscriber, #5246)
In reply to: Worst case performance and "impossibly unlikely" conditions by Cyberax
Parent article: Denial of service via hash collisions

I think the comment on trees vs. hashes was meant to consider an apples-to-apples comparison at the next level up. For example, if you were to replace Perl's "hash" implementation with an automatically balanced tree representation--eg. AVL tree or RB tree or the like--under the hood, almost nobody would notice, but the time complexity would change from "nearly constant time for non-pathological data" to "logarithmic time for all data." Perl programmers don't change a line of Perl, they just see different performance characteristics.

Now, the details of other languages container types is a different story. I realize that the comment you replied to mentions C++, and your complaint seems C++ specific. But if you compare a hash_map to a map where your keys are strings, there really isn't a lot of difference between using either. You either provide an equals operator or a less-than operator. Ooooh.

(Log in to post comments)

Copyright © 2018, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds