Google Entrevista Pregunta

Question

Esta fue una de las preguntas de la Entrevista de Google.

¿Cuál es el problema si es posible Tabla de Hash crece más de 30 gb (ignorar problemas como la mala función hash)

Yo no lo sabía. ¿Qué podría ser una respuesta satisfactoria?

Gracias

Answer 1

Algunos problemas:

1. Hash Collision podría ser uno de los principales problemas posibles.
2. También será ineficiente realizar frecuentes lecturas de disco cuando el almacenamiento de datos en el disco sea una tabla hash.

Answer 2

creo que el entrevistador estaba esperando algo en las líneas de Distributed Hash table, desde una tabla hash de 30 GB no se puede almacenar en una sola máquina (por lo menos en el mundo actual de 64 bits); Desde mi experiencia personal, un buen número de las Qs Google giran en torno a la computación distribuida, mapas reducir etc,

Answer 3

La respuesta depende en parte de si están hablando de una aplicación tabla hash clásica (como HashTable/HashMap en Java) o algo más sofisticado Al final, 30 GB de memoria todavía es bastante grande para una sola máquina/VM según los estándares actuales.

por lo que pensar acerca de lo que está pasando debajo:

1. Se tiene que leer de escritura en una posición arbitraria en alguna arsenal masivo.
2. Tiene que crecer si se llena más allá de alguna medida; ver 'factor de carga' en la implementación de Java.
3. En una basura recogida lenguaje/aplicación, todos los objetos almacenados en la tabla hash deben ser inspeccionados por el recolector de basura

que nos lleva a los siguientes problemas:

1. No está claro que incluso los sistemas operativos actuales se manejan bien con la asignación de trozos de memoria en decenas de GB
2. Por simplicidad, digamos que la mitad de la tabla fue utilizada realmente por la tabla misma (no la clave y los objetos de valor). Entonces hay una matriz de 15 gb adentro. Así que cada vez crece la mesa, tiene que asignar al menos otro 15 gb
3. Incluso si se le asignó una gama decenas de GB, el sistema operativo haría página parte de esta memoria. Dado que asumimos una buena función hash, romperemos el almacenamiento en caché de la página si usamos la mayoría de los datos en la matriz. Habrá una gran cantidad de fallas de página.
4. Digamos que no utilice utilice todos los datos. Algunas teclas se usan con frecuencia y otras no. Para ilustrar, diga que cada valor-clave es minúsculo: 128 bytes. Y para simplificar, digamos que almacenamos todo en la tabla hash como valores. Entonces 30G/128 = ~ 250M entradas. Pero diga 25k teclas comúnmente utilizadas. (25k/250M = 0.01%). Pero con una buena función de hash, estos se distribuirán uniformemente a través de la matriz masiva. Incluso con tamaños de página pequeños: digamos 4kb, los 25K (entradas) * 128 bytes (tamaño de entrada) = ~ 3.5Mb en valor de datos de uso común nos cuesta 25K (entradas) * 4K (tamaño de página) = ~ 100Mb de memoria que debe mantenerse en busca ... ¡con una enorme eficiencia del 3.5%!
5. En el mundo de Java, los profesionales no recomiendan tamaños de pila mayores de 4 - 8 Gb. Claro que hay cosas como Azul, pero eso simplemente prueba el punto: un recolector de basura típico no se adapta a estos tamaños muy bien.

Estoy de acuerdo con otros carteles que Google está buscando como una solución. Pero creo que en el fondo, una tabla hash simple deja de escalar más allá de un punto. En lo anterior,

1. Usted tendría que distribuir si se accede a todas las entradas de manera relativamente uniforme
2. Si algunos se accede a la mayoría de las veces, utilizando dos mapas (uno para uso más frecuente) puede comprar una mucho.
3. En el mundo de Java, el uso de mapas especializados que almacenan datos fuera del montón también puede comprarle rendimiento; ver Peter Lawrey's work por ejemplo.
4. Incluso si solo se divide el conjunto subyacente en una tabla hash (como ocurre con el software ConcurrentHashMap de Java) puede comprar grandes mejoras cuando se tiene que hacer crecer la tabla hash.