Caso real

Crecer de golpe o de a poco

Recolocar todas las claves de una vez produce una pausa: una inserción tarda mucho más que las demás. Redis, una base de datos en memoria muy usada, hace el rehash de forma gradual: mantiene las dos tablas, y en cada operación mueve unas pocas cubetas de la vieja a la nueva. Mientras dura, busca en las dos.

Fíjate en el detalle de la mitad del camino: la tabla vieja todavía tiene claves por mover y llegan operaciones nuevas. ¿Dónde se inserta una clave que llega entonces?

Una tabla crece de forma gradual: mantiene la vieja y la nueva, y en cada operación mueve 4 cubetas de una a otra. A mitad del proceso llega una inserción nueva. ¿Dónde pones la clave?En la que tenga menos carga en ese momento, comprobándolo en cada inserciónEn las dos, para que la búsqueda la encuentre en cualquieraEn la tabla nueva: así la vieja solo pierde claves y el proceso terminaEn la tabla vieja: es donde todavía están la mayoría de las claves