As far as i remember from university, it also depends on what you mean by 'finding' in your scenario.
If you need to retrieve a value by key lookup hashmaps are perfect, if you want to find within a range then there are other data structures like B+ trees.
Interesting comparison anyway! Seeing big-O notation made me feel at school again ;-)