Почему библиотека open-source Google sparsehash имеет две реализации: плотную хэш-таблицу и редкую?
Какова основная идея реализации редкой хеш-таблицы?
Ответ 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 бит (в пределе).
Ответ 2
sparsehash - эффективный способ сопоставления ключей со значениями (1-2 бит на ключ). Фильтры Bloom могут дать вам еще меньше бит на ключ, но они не придают значения клавишам, отличным от внешнего/возможно-внутри, что немного меньше, чем немного информации.