Diagnóstico

La tabla que se volvió lenta

Una tabla hash de identificadores de usuario funciona bien en pruebas, que usan identificadores al azar. En producción, buscar se vuelve lento a medida que crece. Los identificadores son múltiplos de 64 (los genera otro sistema así), la capacidad es 64 y la función hash es hash(id) = id.

Una tabla hash de identificadores va bien en pruebas, con id al azar, pero en producción buscar se vuelve lento al crecer. Allí los id son múltiplos de 64, la capacidad es 64 y hash(id) = id. ¿Qué hipótesis explica el síntoma y qué evidencia la confirma?La tabla está llena y necesita duplicar la capacidad; se confirma mirando el factor de cargaTodos los id caen en la cubeta 0: la tabla es una cadena; se confirma contando claves por cubetaLa tabla es demasiado grande y no cabe en la caché; se confirma midiendo la memoria que ocupaLa función hash es lenta de calcular; se confirma midiendo el tiempo de una llamada a hash