Trade-offs

El mismo problema, otro tamaño

El contador de palabras ahora procesa todo internet: miles de millones de palabras distintas, que no caben en memoria.

El contador de palabras ahora procesa todo internet: miles de millones de palabras distintas, que no caben en memoria. ¿Qué cambia en la elección?Nada: el hash es O(1) esperado, y ese costo no depende de cuántas palabras haya guardadas en la tablaBasta con un heap más grande, que guarde las palabras más frecuentes de todo internet y nada másLa tabla hash completa no cabe: hay que repartir el trabajo, aproximar o guardar en disco con un B-treeHay que pasar a un árbol rojinegro en memoria, que ocupa menos que una tabla hash porque no deja huecos