data structures - tablas - ¿Cuál es la idea principal de implementación detrás de la tabla hash dispersa?

tablas hash c++

Question

¿Por qué la biblioteca de código abierto de Google Sparsehash tiene dos implementaciones: una tabla hash densa y una dispersa?

Answer 1

La tabla hash densa es la implementación de tabla hash de un libro de texto normal.

El hashtable disperso almacena solo los elementos que realmente se han establecido, divididos en una serie de arreglos. Para citar de los comments en la implementación de tablas dispersas:

// The idea is that a table with (logically) t buckets is divided
// into t/M *groups* of M buckets each.  (M is a constant set in
// GROUP_SIZE for efficiency.)  Each group is stored sparsely.
// Thus, inserting into the table causes some array to grow, which is
// slow but still constant time.  Lookup involves doing a
// logical-position-to-sparse-position lookup, which is also slow but
// constant time.  The larger M is, the slower these operations are
// but the less overhead (slightly).

Para saber qué elementos de las matrices están configurados, una tabla dispersa incluye un mapa de bits:

// To store the sparse array, we store a bitmap B, where B[i] = 1 iff
// bucket i is non-empty.  Then to look up bucket i we really look up
// array[# of 1s before i in B].  This is constant time for fixed M.

de modo que cada elemento incurre en una sobrecarga de solo 1 bit (en el límite).

Answer 2

sparsehash es una forma eficiente de memoria de asignar claves a valores (1-2 bits por clave). Los filtros Bloom pueden proporcionarle incluso menos bits por clave, pero no adjuntan valores a otras claves que no sean el exterior / probablemente el interior, lo cual es un poco menos que un poco de información.