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

Question

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

Answer 1

La hashtable densa es la implementación habitual de hash textbook.

La tabla hash dispersa solo almacena los elementos que se han establecido, divididos en varias matrices. Citando el comments en la implementación de mesas 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). 

a saber qué elementos de las matrices se establecen, una mesa de escasa 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. 

manera 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 darle incluso menos bits por clave, pero no agregan valores a claves que no sean externas/probablemente internas, lo que es un poco menos que un poco de información.