Go中秘而不宣的数据结构 BitVec：位向量125MB存储10亿个数据

文章预览

秘而不宣系列 Go中秘而不宣的数据结构 Treap：平衡树不一定就用红黑树 Go中秘而不宣的数据结构 runq, 难怪运行时调度那么好 Go中秘而不宣的数据结构 spmc, 10倍性能于 channel 位图(bitmap)是一种优雅而高效的数据结构,它巧妙地利用了计算机最底层的位运算能力。你可以把它想象成一个巨大的开关阵列,每个开关只有打开和关闭两种状态 —— 这就是位图的本质。每一位都可以独立控制,却又可以通过位运算实现群体操作。 在实际应用中,位图的威力令人惊叹。设想你需要在海量数据中查找重复的数字,传统的哈希表或数组都会占用大量内存。而位图却能巧妙地用一个比特位标记一个数字的出现情况,极大地压缩了存储空间。在处理 10 亿个不重复的整数 时,位图仅需要 125MB 内存 ,相比其他数据结构动辄需要几个 GB,效率提升显著。 位图的运用也体现在我们日常 ………………………………