Fri, 15 Jan 2010 08:55:39 -0800 Jon Cruz <jon@...18...> kirjoitti:

We need to see a bit of the actual numbers involved. Among other things, CPU look-ahead and caching can significantly affect performance... I've seen simple arrays and array walking outperform hash tables/maps contrary to Big-O predictions. (If interested, I think MSDN has a decent article on this).

Sorry to be pedantic here, but there's a misunderstanding of Big-O notation here I'd like to correct.

For example, for some certain amount of stored values, array walk can outperform hash map when searching for a key. However, this is _not_ contrary to Big-O predictions! The fact that linear search of an array is O(n) and searching hash map for a key is O(1) tells that hash map will be faster for any _large enough_ amount of stored values. Also, for small amounts of values the time taken will usually be small either way, so the difference is likely to be irrelevant.