Encuentro que si inicializo un diccionario vacío al principio y luego agrego elementos al diccionario en un bucle for (alrededor de 110,000 claves, el valor de cada clave es una lista, que también aumenta en el bucle), la velocidad disminuye a medida que para el bucle va.

Sospecho que el problema es que el diccionario no conoce la cantidad de claves en el momento de inicio y no está haciendo algo muy inteligente, por lo que tal vez la colisión de almacenamiento sea bastante frecuente y se ralentice.

Si conozco la cantidad de claves y exactamente cuáles son esas claves, ¿hay alguna manera en Python para hacer que un dict (o una tabla hash) funcione de manera más eficiente? Recuerdo vagamente que si conoce las claves, puede diseñar la función de hash de manera inteligente (¿hash perfecto?) Y asignar el espacio de antemano.