This week's book giveaway is in the OCAJP 8 forum. We're giving away four copies of OCA Java SE 8 Programmer I Study Guide and have Edward Finegan & Robert Liguori on-line! See this thread for details.
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.