Какова основная идея реализации разреженной хеш-таблицы?

Question

Почему у библиотеки с открытым исходным кодом Google sparsehash есть две реализации: плотная хеш-таблица и редкая?

Answer 1

Плотная хеш-таблица - это обычная реализация хеш-таблицы учебника.

В разреженной хеш-таблице хранятся только те элементы, которые фактически были установлены, разделенные на несколько массивов. Чтобы процитировать комментарии в реализации разреженных таблиц:

// 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).

Чтобы узнать, какие элементы массивов установлены, разреженная таблица включает в себя растровое изображение:

// 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.

так что каждый элемент несет накладные расходы только 1 бит (в пределе).

Answer 2

sparsehash - это эффективный для памяти способ сопоставления ключей со значениями (1-2 бита на ключ). Фильтры Блума могут дать вам еще меньше битов на ключ, но они не привязывают значения к ключам, отличным от внешнего /, вероятно, внутреннего, что немного меньше информации.