同步操作将从 崔文俊/quick 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
核心思想是这样的:
一个字节8个bit,每个bit取值1或0用于表示存在或者不存在,这已经是最节约内存的做法。
要判断某个数据是否存在,只要把这个数据映射到字节数组中的某个bit上后,就可以快速定位到这个数据是否存在。这个效率是比较高效和节约内存空间的。
private final static int ADDRESS_BITS_PER_WORD = 6;
private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD; //1左移6位是64,也就是说BITS_PER_WORD=64
一个默认大小的BitSet里面是64个bit,也就是说有64个开关量,可以用于标记64个数据是否存在
/**
* Creates a new bit set. All bits are initially {@code false}.
*/
public BitSet() {
initWords(BITS_PER_WORD); //默认64,这个64不是指字节,而是指64个Bit,就是8个字节,所以一个long正好是8个字节
sizeIsSticky = false;
}
BitSet里面是用long数组来维持标记的,一个long是8个字节,一个长度为1的long[]就可以表示64个bit的开关量
如果默认的64个bit不够,假设你现在要在100万个用户中判断某个用户是否存在,假设用户ID都是数字,那么nbits就可以取更大的值,比如传入100万
/**
* Creates a bit set whose initial size is large enough to explicitly
* represent bits with indices in the range {@code 0} through
* {@code nbits-1}. All bits are initially {@code false}.
*
* @param nbits the initial size of the bit set
* @throws NegativeArraySizeException if the specified initial size
* is negative
*/
public BitSet(int nbits) {
// nbits can't be negative; size 0 is OK
if (nbits < 0)
throw new NegativeArraySizeException("nbits < 0: " + nbits);
initWords(nbits);
sizeIsSticky = true;
}
100万个数据的话,最终计算出来是需要15625个长度的long型数组,也就是new long[15625],实际上就是15625 * 8 * 8 =
这里可以初始化为100个bit,很明显不够,下面我set的时候传入的是46000,所以BitSet会自动扩容
BitSet bitSet = new BitSet(100);
System.out.println("bitSet.size = " + bitSet.size() + ", bitSet.length = " + bitSet.length());
bitSet.set(46000, true);
System.out.println("bitSet = " + bitSet.get(45999));
System.out.println("bitSet = " + bitSet.get(46000));
System.out.println("bitSet = " + bitSet.get(46001));
System.out.println("bitSet.size = " + bitSet.size() + ", bitSet.length = " + bitSet.length());
看一下输出结果,size已经扩容到超过4万6,否则无法容纳,为啥扩容,因为调用了set(46000, true),原来只有100个bit是无法存放的,必须扩容到超过46000个bit才行
初始:bitSet.size = 128, bitSet.length = 0 bitSet = false bitSet = true bitSet = false 扩容后:bitSet.size = 46016, bitSet.length = 46001
从bitSet.get(45999)和bitSet.get(46001)都可以看得出来,这2个值都是false,证明BitSet内部的long[]数组里面相应的bit位并没有被置为true,所以返回false
正因为BitSet内部用数组中的bit来表示有或者无,再加上调用get(xxxxx)的时候,是把xxxxx这个数字映射到具体的某个bit槽位上的,这个过程CPU运算是非常快的,所以可以使用BitSet来进行海量数据的存在与否判断,非常节约内存,同时运算速度也非常快,在做项目的时候如果遇到特定场景,可以尝试使用它。
另外一个就是布隆过滤器的使用,也是值得使用的,海量数据判存在与否的逻辑,都可以尝试BitSet和布隆过滤器。
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。