【Java】BitSet简介

1，简介

工欲善其事必先利其器，好的数据结构搭配算法，才能高效完成一些较难的任务。

此次介绍BitSet数据结构，但在介绍之前，先思考一个问题。

如果在16G的机器上，高效去重40亿个整数（Int）？

40亿整数约160G内存，显示全部写进机器中，内存不够。如果使用BitSet，由于最大的整数不超过2^31-1 bit，约256MB，因此，从磁盘中依次读取整数，通过BitSet标记则可判断整数是否存在。随后，遍历BitSet，标记为1的则是存在的整数，否则不存在，因此这么做，还算得上计数排序的思维。

2，解析

1，容量

BitSet内部使用long[]数组存储bit位，因此，理论上，最多可存储(2^63 -1 ) * 64个bit位

但实际上受内存限制，其set参数为Int，因此最多设置（2^31 - 1）个bit位。

2，set（自动扩容）

简单看下set方法，由于一个long占64bit，因此，当bitIndex超过当前words.length*64时，就得扩容。