位图
每一个比特位来表示当前比特位对应的数据是否存在,存在为1,不存在为0
整数数组:
- 整数位置:n/32
- 整数位置中具体的bit位置:n%32
- 右移相当于除,右移n位 == 数字➗2^n^
位图实现:哈希表
- 实现:整数数组
- 数据单元是bit位
- 节省空间,一个字节可以存放8个整数的二值信息(存在与否),不存放数据本身
- 操作效率高,通过哈希映射获取位置,通过位运算执行操作, 时间效率O(1)
- 位置映射:
- 获取整数位置,n / 32
- 获取整数的比特位:n % 32
- 位图需要的空间大小和数据的范围有关,和数据本身大小没有关系
- 适合的场景:数据不重复,信息简单