HashMap en Java

Un HashMap, es una colección de objetos, (como los Arrays), pero estos no tienen orden. ¿De que se trata?

Cada objeto se identifica mediante algun indentificador apropiado, por ejemplo un "uuid".
El nombre HASH, hace referencia a una tecnica de organizacion de archivos llamada hashing o "dispersion" en el cual se almacenan registrso en una direccion del archivo que es generada por una funcion que se aplica sobre la llave del registro.

El concepto para JAVA es parecido, el HASHMAP posee un espacio de memoria, y cuando se guarda un objeto alli, se determina su direccion aplicandole una funcion a la llave que le indicamos.

 
Por ejemplo:

    HashMap contenedor = new HashMap();
    Object objeto = new Object();
    String llave = new String("identificador de objeto");    contendor.add(llave,objeto);

La biblioteca estándar de Java tiene dos tipos diferentes de objetos Map (que es una interfaz con cierta funcionalidad): HashMap y TreeMap.

Ambos tienen la misma interfaz (dado que implementan Map), pero difieren claramente en la eficiencia.

Si se observa lo que hace un get(), parecerá bastante lento hacerlo buscando a través de la clave, por ej. de un ArrayList. Es aquí donde un HashMap acelera considerablemente las cosas. En vez de hacer una búsqueda lenta de la clave, usa un valor especial denominado "código de tipo hash". Ésta es una manera de tomar cierta información del objeto en cuestión y convertirlo en un entero "relativamente único" para ese objeto.

Todos los objetos de Java pueden producir un código de tipo hash, y HashCode() es un método de la clase raíz Object. Un HashMap toma un hashCode() del objeto y lo utiliza para localizar rápidamente la clave. Esto redunda en una mejora dramática de rendimiento.  

¿Cuando usar ArrayList y cuando usar HashMap?

Ambas estructuras de datos almacenan Objects y por defecto en Java todas las clases heredan de Object. Es decir, puedes guardar cualquier objeto en cada una de ellas. 

El asunto es ¿cuándo emplear una u otra? 

Por ejemplo, usas un ArrayList cuando necesitas acceder al n-avo elemento. Haz cuenta de que un ArrayList es una columna de objetos en línea y que un HashMap es algo así como una sala llena de objetos dispersos al que llamas por su nombre (clave-valor).

En lo personal suelo usar mas un TreeMap para almacenar miles de objetos, pues el tiempo de recorrido es mucho menor al de un ArrayList, las listas las utilizo para manejar no mas de 500 elementos.

De más está decir que esas no son las únicas estructuras de datos que existen en Java. Tienes además Vector, LinkedList, TreeSet, TreeMap... etc, etc. y cada una de ellas tiene características que las diferencian del resto y que por ende son más óptimas que cualquier otra en cada caso.