資料結構 – 稀疏雜湊表背後的主要實現思想是什麼？

密集雜湊表是您普通教科書的雜湊表實現.

稀疏雜湊表僅儲存實際設定的元素,並分割陣列.引用從ofollow,noindex" target="_blank">comments 執行稀疏表：

// 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位的開銷(限制).