A HashMap is only as good as it's hashing algorithm. For instance a HashMap that throws everything into 1 bucket is equally as useless as a HashMap which throws everything into it's own bucket. The short answer to your question would be "yes", a HashMap or any of the HashXXX objects are designed to divide and conquer large sets of data. If you need other features such as index then a different collection would be needed.
Hope that helps somewhat... if not, please give more details.