HashMap usually performs search operations bounded with complexity of O(1)<=T(n)<=O(n). BST performs search operations in O(logN)<=T(n)<=O(N).
HashMap is implemented with array and hash function. HashMap has O(1) lookup time when the hashcode disperse keys appropriately.
For some special cases, lookup time can be much longer if the number of elements stored is sufficiently large.
原文：http://www.cnblogs.com/touchdown/p/5143655.html