当前位置：新励学网 > 秒知问答 > 位向量工作原理

位向量工作原理

发表时间：2024-07-28 03:42:03 来源：网友投稿

位向量也叫位图，是一个我们经常可以用到的数据结构，在使用小空间来处理大量数据方面有着得天独厚的优势；位向量的定义就是一串由0.1组成的序列。

Java中对位向量的实现类时Java.util.BitSet;C++标准库中也有相应的实现，原理都是一样的； BitSet源码也很简单，很容易看懂，如果读者在对位向量有一定的了解后，可以通过读源码来了解BitSet的具体实现。

一个bit上有两个值，正好可以用来判断某些是非状态的场景，在针对大数据场景下判断存在性，BitSet是相比其他数据结构比如HashMap更好的选择，在Java中，位向量是用一个叫words的long型数组实现的，一个long型变量有64位，可以保存64个数字；比如我们有[2,8,6,10,15]这5个数要保存，一般存储需要 5*4 = 20字节的存储空间。但是如果我们使用Java.util.BitSet进行存储则可以节省很多的空间只需要一个long型数字就够了。BitSet只面向数字只面向数字使用，对于string类型的数据，可以通过hashcode值来使用BitSet。

由于1 << 64, 1<<128, 1<<192 这些数字的结果都为1，BitSet内部，long[]数组的大小由BitSet接收的最大数字决定，这个数组将数字分段表示[0,63],[64,127],[128,191]...。即long[0]用来存储[0,63]这个范围的数字的“存在性”，long用来存储[64,127]，依次轮推，这样就避免了位运算导致的冲突。原理如下：

|------------|----------|----------|----------|----------| |

Java的BitSet每次申请空间，申请64位，即一个long型变量所占的位数；

免责声明：本站发布的教育资讯（图片、视频和文字）以本站原创、转载和分享为主，文章观点不代表本网站立场。

如果本文侵犯了您的权益，请联系底部站长邮箱进行举报反馈，一经查实，我们将在第一时间处理，感谢您对本站的关注！