¿Cómo funciona un hash map por dentro?

Un array de buckets. hash(key) % capacity elige el bucket.
Colisiones (dos claves, mismo bucket): chaining (una lista pequeña por bucket) u open addressing (probar las siguientes posiciones; así lo hacen los dicts de Python).
Cuando se llena demasiado (load factor), se redimensiona: un array mayor y cada clave recolocada. Inserciones en O(1) amortizado.
Las claves deben ser hashable y no deben cambiar; las claves iguales deben tener hashes iguales.
get/put/delete en O(1) de media; O(n) en el peor caso con muchas colisiones.