¿Cuándo elegirías un hash map en lugar de un árbol binario de búsqueda balanceado?

Elige un hash map cuando solo necesitas búsquedas, inserciones y borrados por clave y quieres tiempo constante en promedio. Elige un árbol balanceado cuando necesitas orden: recorridos por rango, la clave más cercana o iterar en orden, todo en tiempo logarítmico. Los árboles además te dan un peor caso predecible, mientras que un hash map puede degradarse mucho con un hash malo o atascarse en un redimensionado en el peor momento.

Mi opción por defecto es un hash map, porque la mayor parte del tiempo hago búsquedas puntuales por id y el tiempo constante en promedio es difícil de batir. Ahora bien, en cuanto el requisito implica orden, cambio. Cualquier cosa del tipo dame todos los eventos entre dos marcas de tiempo, o encuéntrame la siguiente clave después de esta, es una consulta por rango, y un hash map no puede hacerlo sin recorrerlo todo. Eso pide un árbol o, en la práctica, una estructura ordenada con búsqueda binaria. También pienso en la cola. Las búsquedas hash son constantes en promedio, pero una función de hash mala o un rehash pueden dispararse, y dentro de un presupuesto de latencia eso me importa. En una funcionalidad de leaderboard que construí empezamos con un diccionario de usuario a puntuación y luego teníamos que ordenar todo en cada lectura. En cuanto pasamos a un sorted set en Redis, las lecturas se volvieron logarítmicas y el endpoint dejó de caerse en pico. Los mismos datos, otro patrón de acceso, otra estructura.