Postgresql Bitmapset

2023年 8月 13日 83.4k 0

BitMap

前言

Bitmap的基本思想就是用一个bit位来标记某个元素对应的Value,而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。

原理

bitmap就是使用bit位的值0或1标识一个数是否存在,0表示存在,1则表示不存在

如何使用bitmap表示一个数?

根据上述的实现原理可知,每一位表示一个数,0表示不存在,1表示存在。例如:{1,2,4,6}这几个数怎么在bitmap中表示?

image.png

计算机内存分配的最小单位是字节,也就是8位,那如果要表示{12,13,15}怎么办呢?当然是在另一个8位上表示了:
image.png
1个int占32位,那么只需要申请一个int数组长度为 int tmp[1+N/32] 即可存储,其中N表示要存储的这些数中的最大值,于是乎:

tmp[0]:可以表示0-31
tmp[1]:可以表示32-63
tmp[2]:可以表示64~95

给定任意整数M,那么M/32就得到下标,M%32就知道它在此下标的哪个位置

bitmap操作

添加元素

怎么把一个数添加到bitmap中呢?例如,想把5这个数字添加到bitmap?
首先,5/32=0,5%32=5,也是说它应该在tmp[0]的第5个位置,那我们把1向左移动5位,然后按位或:
image.png
相当于:86 | (1

相关文章

JavaScript2024新功能:Object.groupBy、正则表达式v标志
PHP trim 函数对多字节字符的使用和限制
新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
为React 19做准备:WordPress 6.6用户指南
如何删除WordPress中的所有评论

发布评论