搜公众号
推荐 原创 视频 Java开发 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库
Lambda在线 > 蹲厕所的熊 > BitSet的原理以及应用

BitSet的原理以及应用

蹲厕所的熊 2018-07-10
举报

蹲厕所的熊 转载请注明原创出处,谢谢!

1、概述

位图(Bitmap),即位(Bit)的集合,是一种常用的数据结构,可用于记录大量的0-1状态,在很多地方都会用到,比如Linux内核(如inode,磁盘块)、Bloom Filter算法等,其优势是可以在一个非常高的空间利用率下保存大量0-1状态。在Java中,直接面向程序员的最小数据操作粒度是byte,并不提供能够直接操作某个bit的途径,但是程序员可以通过使用位运算符(& | ~ << >> 等等)自己封装位操作。如果不想自己动手,可以使用Java内置的BitSet类,其实现了位图数据结构并提供了一系列有用的方法。

2、使用

 
   
   
 
  1. public class BitSetTest {

  2.    public static void main(String[] args) {

  3.        BitSet bitSet = new BitSet(128);

  4.        bitSet.set(77);

  5.        // true

  6.        System.out.println(bitSet.get(77));

  7.    }

  8. }

一个简单的例子,可能大家刚开始不太好理解BitSet,其实你们就把BitSet想象成是一个拥有N个槽位的大数组,而set方法就是找到对应的槽位并填充,这样下次get对应槽位就会返回是否被填充过。上面这个例子就是在77这个位置进行了填充。

那么这个类有什么作用呢?我们先来分析它的源码,最后给出一个面试经常遇到的题目让大家深入理解。

3、源码分析

先来看看内部的一些属性所代表的含义

属性

 
   
   
 
  1. /*

  2. */

  3. private final static int ADDRESS_BITS_PER_WORD = 6;

  4. // 1算数左移6位,即1 × 2^6 = 64  即 01000000

  5. private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;

  6. // 1 x 2^6 - 1 = 63 即 00111111

  7. private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;

  8. /* 用于向左或向右移动部分word的掩码 */

  9. private static final long WORD_MASK = 0xffffffffffffffffL;

至于为什么选择long这种数据类型,注释的解析是基于性能的原因,现在64位CPU已经非常普及,可以一次把一个64bit长度的long放进寄存器作计算。

 
   
   
 
  1. /**

  2. * 对应于serialField “bits” 的内部字段。

  3. */

  4. private long[] words;

  5. /**

  6. * BitSet中words的实际使用长度

  7. */

  8. private transient int wordsInUse = 0;

  9. /**

  10. * words的大小是不是由用户指定的,如果是我们假设知道用户在做什么,并尽力保存它

  11. */

  12. private transient boolean sizeIsSticky = false;

属性words即为实际存储数据的地方。

构造函数

 
   
   
 
  1. /**

  2. * 初始化words长度为1,所有bit的初始化false

  3. */

  4. public BitSet() {

  5.    initWords(BITS_PER_WORD);

  6.    sizeIsSticky = false;

  7. }

  8. /**

  9. * 创建一个初始大小足够大的位集,以便明确地表示索引在范围在 0 到 nbits-1 范围内的位。

  10. * 所有bit初始化都是false

  11. */

  12. public BitSet(int nbits) {

  13.    // nbits不能为负数,可以为0

  14.    if (nbits < 0)

  15.        throw new NegativeArraySizeException("nbits < 0: " + nbits);

  16.    initWords(nbits);

  17.    sizeIsSticky = true;

  18. }

  19. /**

  20. * 初始化words,数组长度为 (nbits-1)/64 + 1

  21. */

  22. private void initWords(int nbits) {

  23.    words = new long[wordIndex(nbits-1) + 1];

  24. }

  25. /**

  26. * 算出words的index

  27. * 返回 bitIndex / 64

  28. */

  29. private static int wordIndex(int bitIndex) {

  30.    return bitIndex >> ADDRESS_BITS_PER_WORD;

  31. }

  32. /**

  33. * 内部访问

  34. * 使用传入的words做为初始化words

  35. * words的最后一个word不能为0

  36. */

  37. private BitSet(long[] words) {

  38.    this.words = words;

  39.    this.wordsInUse = words.length;

  40.    checkInvariants();

  41. }

用户如果知道长度的情况下,最好指定一个长度,一开始就初始化好,避免后面进行扩容操作。

set方法

 
   
   
 
  1. /**

  2. * 在指定的index设置bit

  3. */

  4. public void set(int bitIndex) {

  5.    if (bitIndex < 0)

  6.        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

  7.    // 定位以及检查是否需要扩容

  8.    int wordIndex = wordIndex(bitIndex);

  9.    expandTo(wordIndex);

  10.    // 使用或操作设置bit值

  11.    words[wordIndex] |= (1L << bitIndex); // Restores invariants

  12.    checkInvariants();

  13. }

  14. /**

  15. * 在指定的index根据value做操作

  16. * value=true 设置值, value=false 清除值

  17. */

  18. public void set(int bitIndex, boolean value) {

  19.    if (value)

  20.        set(bitIndex);

  21.    else

  22.        clear(bitIndex);

  23. }

set方法首先根据wordIndex定位long数组的位置,然后通过expandTo检查是否需要扩容。最后使用或操作设置对应槽位的bit值。

 
   
   
 
  1. /**

  2. * 确保BitSet可以容纳给定的wordIndex,暂时违反不变量原则。

  3. * 调用者必须在返回给用户之前恢复不变式,可能使用recalculateWordsInUse()。

  4. * @param wordIndex 计算出放在words里面的数组下标index

  5. */

  6. private void expandTo(int wordIndex) {

  7.    // 需要的words数组长度

  8.    int wordsRequired = wordIndex+1;

  9.    if (wordsInUse < wordsRequired) {

  10.        // 扩容

  11.        ensureCapacity(wordsRequired);

  12.        wordsInUse = wordsRequired;

  13.    }

  14. }

  15. /**

  16. * 确保BitSet能够存放足够的words

  17. * @param wordsRequired words需要的数组长度

  18. */

  19. private void ensureCapacity(int wordsRequired) {

  20.    if (words.length < wordsRequired) {

  21.        // 扩容机制:2倍words的长度 和 wordsRequired比较,谁大选谁

  22.        int request = Math.max(2 * words.length, wordsRequired);

  23.        // 数组copy

  24.        words = Arrays.copyOf(words, request);

  25.        sizeIsSticky = false;

  26.    }

  27. }

上面两个set方法都只是对单个槽位进行set操作,BitSet还提供了对连续的一串值进行set操作。

 
   
   
 
  1. /**

  2. * 设置 [fromIndex, toIndex) 范围的值为1

  3. */

  4. public void set(int fromIndex, int toIndex) {

  5.    checkRange(fromIndex, toIndex);

  6.    if (fromIndex == toIndex)

  7.        return;

  8.    // Increase capacity if necessary

  9.    int startWordIndex = wordIndex(fromIndex);

  10.    int endWordIndex   = wordIndex(toIndex - 1);

  11.    expandTo(endWordIndex);

  12.    // 左移fromIndex个位置,右边空位以0补齐

  13.    long firstWordMask = WORD_MASK << fromIndex;

  14.    // 右移(64-toIndex)个位置,也就是从右边起往左toIndex个位置是1,其他位置都是0

  15.    long lastWordMask  = WORD_MASK >>> -toIndex;

  16.    if (startWordIndex == endWordIndex) {

  17.        // Case 1: 同一个word 取firstWordMask和lastWordMask相交的为1的部分

  18.        words[startWordIndex] |= (firstWordMask & lastWordMask);

  19.    } else {

  20.        // Case 2: 多个words

  21.        // 处理第一个word

  22.        words[startWordIndex] |= firstWordMask;

  23.        // 如果有中间words,处理它

  24.        for (int i = startWordIndex+1; i < endWordIndex; i++)

  25.            words[i] = WORD_MASK;

  26.        // 处理最后一个word

  27.        words[endWordIndex] |= lastWordMask;

  28.    }

  29.    checkInvariants();

  30. }

  31. /**

  32. * 在指定的范围[fromIndex, toIndex)根据value做操作

  33. * value=true 设置值, value=false 清除值

  34. */

  35. public void set(int fromIndex, int toIndex, boolean value) {

  36.    if (value)

  37.        set(fromIndex, toIndex);

  38.    else

  39.        clear(fromIndex, toIndex);

  40. }

set(int fromIndex, int toIndex)的思路就是先定位到long数组words的哪几个位置,如果fromIndex和toIndex在同一个word里,就直接把他们之间的数都设为1。如果fromIndex和toIndex不在同一个word里,就依次设置不同的word的值。

get方法

 
   
   
 
  1. /**

  2. * 返回指定的bitIndex位的bit是不是1,是1返回true,否则返回false

  3. */

  4. public boolean get(int bitIndex) {

  5.    if (bitIndex < 0)

  6.        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

  7.    checkInvariants();

  8.    int wordIndex = wordIndex(bitIndex);

  9.    return (wordIndex < wordsInUse)

  10.        && ((words[wordIndex] & (1L << bitIndex)) != 0);

  11. }

  12. /**

  13. * 返回[fromIndex, toIndex)的值的一个BitSet

  14. */

  15. public BitSet get(int fromIndex, int toIndex) {

  16.    checkRange(fromIndex, toIndex);

  17.    checkInvariants();

  18.    int len = length();

  19.    // If no set bits in range return empty bitset

  20.    if (len <= fromIndex || fromIndex == toIndex)

  21.        return new BitSet(0);

  22.    // An optimization

  23.    if (toIndex > len)

  24.        toIndex = len;

  25.    BitSet result = new BitSet(toIndex - fromIndex);

  26.    int targetWords = wordIndex(toIndex - fromIndex - 1) + 1;

  27.    int sourceIndex = wordIndex(fromIndex);

  28.    boolean wordAligned = ((fromIndex & BIT_INDEX_MASK) == 0);

  29.    // Process all words but the last word

  30.    for (int i = 0; i < targetWords - 1; i++, sourceIndex++)

  31.        result.words[i] = wordAligned ? words[sourceIndex] :

  32.            (words[sourceIndex] >>> fromIndex) |

  33.            (words[sourceIndex+1] << -fromIndex);

  34.    // Process the last word

  35.    long lastWordMask = WORD_MASK >>> -toIndex;

  36.    result.words[targetWords - 1] =

  37.        ((toIndex-1) & BIT_INDEX_MASK) < (fromIndex & BIT_INDEX_MASK)

  38.        ? /* straddles source words */

  39.        ((words[sourceIndex] >>> fromIndex) |

  40.         (words[sourceIndex+1] & lastWordMask) << -fromIndex)

  41.        :

  42.        ((words[sourceIndex] & lastWordMask) >>> fromIndex);

  43.    // Set wordsInUse correctly

  44.    result.wordsInUse = targetWords;

  45.    result.recalculateWordsInUse();

  46.    result.checkInvariants();

  47.    return result;

  48. }

清空BitSet

 
   
   
 
  1. /**

  2. * 设置指定的index位为0

  3. */

  4. public void clear(int bitIndex) {

  5.    if (bitIndex < 0)

  6.        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

  7.    int wordIndex = wordIndex(bitIndex);

  8.    if (wordIndex >= wordsInUse)

  9.        return;

  10.    words[wordIndex] &= ~(1L << bitIndex);

  11.    recalculateWordsInUse();

  12.    checkInvariants();

  13. }

  14. /**

  15. * 清除范围[fromIndex, toIndex)的bit为0

  16. */

  17. public void clear(int fromIndex, int toIndex) {

  18.    checkRange(fromIndex, toIndex);

  19.    if (fromIndex == toIndex)

  20.        return;

  21.    int startWordIndex = wordIndex(fromIndex);

  22.    if (startWordIndex >= wordsInUse)

  23.        return;

  24.    int endWordIndex = wordIndex(toIndex - 1);

  25.    if (endWordIndex >= wordsInUse) {

  26.        toIndex = length();

  27.        endWordIndex = wordsInUse - 1;

  28.    }

  29.    long firstWordMask = WORD_MASK << fromIndex;

  30.    long lastWordMask  = WORD_MASK >>> -toIndex;

  31.    if (startWordIndex == endWordIndex) {

  32.        // Case 1: One word

  33.        words[startWordIndex] &= ~(firstWordMask & lastWordMask);

  34.    } else {

  35.        // Case 2: Multiple words

  36.        // Handle first word

  37.        words[startWordIndex] &= ~firstWordMask;

  38.        // Handle intermediate words, if any

  39.        for (int i = startWordIndex+1; i < endWordIndex; i++)

  40.            words[i] = 0;

  41.        // Handle last word

  42.        words[endWordIndex] &= ~lastWordMask;

  43.    }

  44.    recalculateWordsInUse();

  45.    checkInvariants();

  46. }

  47. /**

  48. * 设置所有的BitSet为0

  49. */

  50. public void clear() {

  51.    while (wordsInUse > 0)

  52.        words[--wordsInUse] = 0;

  53. }

反转某一位

 
   
   
 
  1. /**

  2. * 反转指定的bitIndex位的数

  3. */

  4. public void flip(int bitIndex) {

  5.    if (bitIndex < 0)

  6.        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

  7.    int wordIndex = wordIndex(bitIndex);

  8.    expandTo(wordIndex);

  9.    words[wordIndex] ^= (1L << bitIndex);

  10.    recalculateWordsInUse();

  11.    checkInvariants();

  12. }

  13. /**

  14. * 反转指定范围[fromIndex, toIndex)位的数

  15. */

  16. public void flip(int fromIndex, int toIndex) {

  17.    checkRange(fromIndex, toIndex);

  18.    if (fromIndex == toIndex)

  19.        return;

  20.    int startWordIndex = wordIndex(fromIndex);

  21.    int endWordIndex   = wordIndex(toIndex - 1);

  22.    expandTo(endWordIndex);

  23.    long firstWordMask = WORD_MASK << fromIndex;

  24.    long lastWordMask  = WORD_MASK >>> -toIndex;

  25.    if (startWordIndex == endWordIndex) {

  26.        // Case 1: One word

  27.        words[startWordIndex] ^= (firstWordMask & lastWordMask);

  28.    } else {

  29.        // Case 2: Multiple words

  30.        // Handle first word

  31.        words[startWordIndex] ^= firstWordMask;

  32.        // Handle intermediate words, if any

  33.        for (int i = startWordIndex+1; i < endWordIndex; i++)

  34.            words[i] ^= WORD_MASK;

  35.        // Handle last word

  36.        words[endWordIndex] ^= lastWordMask;

  37.    }

  38.    recalculateWordsInUse();

  39.    checkInvariants();

  40. }

反转的原理就是把某一位变为它的相反数,使用的异或1的操作。如果bit是1,1^1=0,如果bit是0,0^1=1,这样就能够进行反转了。

几个静态函数

 
   
   
 
  1. /**

  2. * 返回一个包含longs数组的新bit set集合

  3. *

  4. * 更确切的说

  5. * BitSet.valueOf(longs).get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)

  6. * 上面的 n < 64 * longs.length

  7. *

  8. * 这个方法相当于 BitSet.valueOf(LongBuffer.wrap(longs))

  9. */

  10. public static BitSet valueOf(long[] longs) {

  11.    int n;

  12.    for (n = longs.length; n > 0 && longs[n - 1] == 0; n--)

  13.        ;

  14.    return new BitSet(Arrays.copyOf(longs, n));

  15. }

  16. /**

  17. * 返回一个新的BitSet,它包含position和limit之间的给定long缓冲区中的所有bit。

  18. */

  19. public static BitSet valueOf(LongBuffer lb) {

  20.    lb = lb.slice();

  21.    int n;

  22.    for (n = lb.remaining(); n > 0 && lb.get(n - 1) == 0; n--)

  23.        ;

  24.    long[] words = new long[n];

  25.    lb.get(words);

  26.    return new BitSet(words);

  27. }

  28. /**

  29. * 返回一个包含bytes数组的新bit set集合

  30. *

  31. * 更确切的说

  32. * BitSet.valueOf(bytes).get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)

  33. * 上面的 n <  8 * bytes.length

  34. *

  35. * 这个方法相当于 BitSet.valueOf(ByteBuffer.wrap(bytes))

  36. */

  37. public static BitSet valueOf(byte[] bytes) {

  38.    return BitSet.valueOf(ByteBuffer.wrap(bytes));

  39. }

  40. /**

  41. * 返回一个新的BitSet,它包含position和limit之间的给定byte缓冲区中的所有bit。

  42. */

  43. public static BitSet valueOf(ByteBuffer bb) {

  44.    bb = bb.slice().order(ByteOrder.LITTLE_ENDIAN);

  45.    int n;

  46.    for (n = bb.remaining(); n > 0 && bb.get(n - 1) == 0; n--)

  47.        ;

  48.    long[] words = new long[(n + 7) / 8];

  49.    bb.limit(n);

  50.    int i = 0;

  51.    while (bb.remaining() >= 8)

  52.        words[i++] = bb.getLong();

  53.    for (int remaining = bb.remaining(), j = 0; j < remaining; j++)

  54.        words[i] |= (bb.get() & 0xffL) << (8 * j);

  55.    return new BitSet(words);

  56. }

其他方法

 
   
   
 
  1. /**

  2. * 返回指定起始索引处或之后出现的第一个设置为1的bit的索引。

  3. * 如果不存在这样的bit,则返回{@code -1}。

  4. *

  5. * 要遍历BitSet中的{true}位,请使用以下循环:

  6. *

  7. *  <pre> {@code

  8. * for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {

  9. *     // operate on index i here

  10. *     if (i == Integer.MAX_VALUE) {

  11. *         break; // or (i+1) would overflow

  12. *     }

  13. * }}</pre>

  14. */

  15. public int nextSetBit(int fromIndex) {

  16.    if (fromIndex < 0)

  17.        throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);

  18.    checkInvariants();

  19.    int u = wordIndex(fromIndex);

  20.    if (u >= wordsInUse)

  21.        return -1;

  22.    // 首先定位到fromIndex所在的word,并且把低位到fromIndex的bit设置为0

  23.    long word = words[u] & (WORD_MASK << fromIndex);

  24.    /**

  25.     * 如果word != 0,返回低位到不为0的数的index

  26.     * 注:Long.numberOfTrailingZeros(word)表示在word的补码基础上返回

  27.     *  最低位的数到第一个为1的数的index长度。

  28.     *  比如:Long.numberOfTrailingZeros(0xFFFFFFFFFFFFFFF4l) == 2

  29.     */

  30.    while (true) {

  31.        if (word != 0)

  32.            return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);

  33.        if (++u == wordsInUse)

  34.            return -1;

  35.        word = words[u];

  36.    }

  37. }

  38. /**

  39. * 返回指定起始索引处或之后出现的第一个设置为0的bit的索引。

  40.    * 如果不存在这样的bit,则返回{@code -1}。

  41. *  和nextSetBit(int fromIndex) 类似的原理

  42. */

  43. public int nextClearBit(int fromIndex) {

  44.    // Neither spec nor implementation handle bitsets of maximal length.

  45.    // See 4816253.

  46.    if (fromIndex < 0)

  47.        throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);

  48.    checkInvariants();

  49.    int u = wordIndex(fromIndex);

  50.    if (u >= wordsInUse)

  51.        return fromIndex;

  52.    long word = ~words[u] & (WORD_MASK << fromIndex);

  53.    while (true) {

  54.        if (word != 0)

  55.            return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);

  56.        if (++u == wordsInUse)

  57.            return wordsInUse * BITS_PER_WORD;

  58.        word = ~words[u];

  59.    }

  60. }

  61. /**

  62. * 如果传入的BitSet和当前的BitSet有交集为1的话,返回true

  63. */

  64. public boolean intersects(BitSet set) {

  65.    for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)

  66.        if ((words[i] & set.words[i]) != 0)

  67.            return true;

  68.    return false;

  69. }

  70. /**

  71. * 返回words中设置了1的总bit数

  72. * 比如

  73. *  BitSet bitSet = new BitSet(128);

  74. *  bitSet.set(77);

  75. *  bitSet.set(80);

  76. *  bitSet.set(2);

  77. * 返回3

  78. */

  79. public int cardinality() {

  80.    int sum = 0;

  81.    for (int i = 0; i < wordsInUse; i++)

  82.        sum += Long.bitCount(words[i]);

  83.    return sum;

  84. }

  85. /**

  86. * 对传入的BitSet和当前的BitSet的所有bit位进行与操作。

  87. */

  88. public void and(BitSet set) {

  89.    if (this == set)

  90.        return;

  91.    while (wordsInUse > set.wordsInUse)

  92.        words[--wordsInUse] = 0;

  93.    // Perform logical AND on words in common

  94.    for (int i = 0; i < wordsInUse; i++)

  95.        words[i] &= set.words[i];

  96.    recalculateWordsInUse();

  97.    checkInvariants();

  98. }

4、实战

前一段时间在网上看到这样一道面试题:

有个老的手机短信程序,由于当时的手机CPU,内存都很烂。所以这个短信程序只能记住256条短信,多了就删了。每个短信有个唯一的ID,在0到255之间。当然用户可能自己删短信.现在要求设计实现一个功能: 当收到了一个新短信啥,如果手机短信容量还没"用完"(用完即已经存储256条),请分配给它一个可用的ID。由于手机很破,我要求你的程序尽量快,并少用内存。

审题

通读一遍题目,可以大概知道题目并不需要我们实现手机短信内容的存储,也就是不用管短信内容以什么形式存、存在哪里等问题。需要关心的地方应该是如何快速找到还没被占用的ID(0 ~ 255),整理一下需求,如下:

  • 手机最多存储256条短信,短信ID范围是[0,255];

  • 用户可以手动删除短信,删除哪些短信是由用户决定的;

  • 当收到一条新短信时,只需要分配一个还没被占用的ID即可,不需要是可用ID中最小的ID;

  • 题目没说明在手机短信容量已满的情况下,也就是无法找到可用ID时需要怎么办,这里约定在这种情况下程序返回一个错误码即可;

理清需求之后,其实需要做的事情就很清楚了:

  • 设计一个数据结构来存储已被占用的或没被占用的短信ID;

  • 实现一个函数,返回一个可用的ID,当无法找到可用ID时,返回-1;

  • 在实现以上两点的前提下,尽量在程序执行速度和内存占用量上做优化。

解题

线性查找

这应该是最简(无)单(脑)一个办法。如果想用一个数据结构保存已占用的ID,由于这是一个变长无序的集合,而数组(Array)这种结构是定长的,并且原生并未提供删除数组元素的功能,所以应该很容想到用Java类库提供的List作为容器。那么寻找一个可用ID的方法就很简单:只要多次遍历这个List,第一次遍历时查找0是否在这个List中,如果没找到,着返回0,否则进行下一趟遍历查找1,直到255,这个过程可以用一个2重循环来实现:

 
   
   
 
  1. /**

  2. * 线性查找

  3. * 时间复杂度: O(n^2)

  4. * @param busyIDs 被占用的ID

  5. * @return

  6. */

  7. public int search(List<Integer> busyIDs) {

  8.    for(int i = 0; i < 255; i++) {

  9.        if(busyIDs.indexOf(i) == -1) return i;

  10.    }

  11.    return -1;        

  12. }

但是这种实现方式的问题不少,其中最严重的就是时间复杂度问题。由于List.indexOf(Object)函数的实现方式是顺序遍历整个数据结构(无论是ArrayList还是LinkedList都是如此,ArrayList由于底层用数组实现,遍历操作在连续的内存空间上进行,比LinkedList要快一些),再套上外层的循环,导致时间复杂度为O(2^n)。

另外一个问题是空间复杂度。先不论List这个类内部包含的各种元数据(ArrayList或LinkedList类的一些私有属性),由于List中存储的元素必须为Java Object,所以上面的代码的List中实际上存放的事Integer类。我们知道这种封装类型要比对应的基本数据类型(Primitive Types)占用更多的内存空间,以Integer为例,在64bit JVM(关闭压缩指针)下,一个Integer对象占用的内存空间为24Byte = 8Byte mark_header + 8Byte Klass 指针 + 4Byte int(用于存储数值)+ 4Byte(Padding,Java对象必须以8Byte为界对齐)。 而一个int变量只需要4Byte!另外即使把Integer替换成Short,情况也是一样。也就是说,当手机保存了256条短信时,存储被占用ID总共需要的空间为:256 × 24Byte = 6KB! 而且还不包括List本身的元数据!

最后还有个问题就是List在删除元素时的效率问题。ArrayList由于底层用数组实现,所以当删除一个元素后,被删除元素后面的所有元素都要往前移动一个位置(用System.arraycopy()实现);而LinkedList由于用双向链表存储数据,所以删除元素比较简单,但正是由于其采用双向链表,所以每个元素要额外多占用2个指针的空间(指向前一个和后一个元素)。

Hash表

由于2.1中内层循环采用顺序查找的方式导致时间复杂度为O(2^n),一个很容易想到的改进就是把已经被占用的ID存放在一个Hash表中,由于Hash表对查找操作的时间复杂度为O(C)(实际上并不一定,对于用链表法解决冲突的Hash表,查找一个元素的时间跟链表的平均长度有关,也就是O(n)。但这里简单认为时间复杂度就是常数),所以查找一个可用ID的时间复杂度为O(n)。代码如下:

 
   
   
 
  1. /**

  2. * Hash表查找

  3. * 时间复杂度: O(n)

  4. * @param busyIDs 被占用的ID

  5. * @return

  6. */

  7. public int search(HashSet<Integer> busyIDs) {

  8.    for(int i = 0; i < 255; i++) {

  9.        if(!busyIDs.contains(i)) return i;

  10.    }

  11.    return -1;        

  12. }

这种实现方式相对2.1在时间上有了改进,但是空间占用问题却更严重了:Java类库中的HashSet其实是用HashMap来实现的,这里不考虑任何元数据,只考虑HashMap本身,用于HashMap本身有一个load factor(默认是0.75,即是HashMap中保存的元素个数不能超过HashMap容量的75%,否则要Re-hash);另外对于HashMap中的每一个元素Entry ,即是我们用的是HashSet,只占用 中的K,但是V也要占用一个指针的位置(其值为null)。

boolean数组

这种实现方式与上面2种比较一个根本的不同是:不存储具体被占用的ID的值,而是存储所有ID的状态(就2种状态,可用与被占用)。由于对于一个ID来说,总共只有2种状态,所以可以用boolean代表一个ID的状态,然后用一个长度为256的boolean数组表示所有ID的状态(假定false=可用,true=被占用)。

当需要查找可用ID时,只需要遍历这个数组,找到第一个值为false的boolean,返回其索引即可。用于现代CPU每次读内存时都可以一次性读取1个Cache Line(一般是64Byte)的内容,而一个boolean只占1Byte,所以达到很高的遍历速度。

另外做删除操作时,只需要把数组中ID对应索引的那个boolean设为false即可。

不过这种方案只适用与定长数据(比如题中注明最多256条短信)。代码如下:

 
   
   
 
  1. /**

  2. * boolean数组

  3. * 时间复杂度: O(n)

  4. * @param busyIDs 被占用的ID

  5. * @return

  6. */

  7. public int search(boolean[] busyIDs) {

  8.    for(int i = 0, len = busyIDs.length; i < len; i++) {

  9.        if(busyIDs[i] == false) return i;

  10.    }

  11.    return -1;        

  12. }

这种方案对比前面2种,在空间复杂度上有非常大的优化:只占用256Byte内存。并且在查找上也可以达到不错的速度。

使用BitSet

这种方案是对2.3的一个优化。由于一个boolean值在JVM中占用1Byte,而1Byte=8bit,8个bit可以表示的状态为2^8 = 256种(0000 0000 ~ 1111 1111),而我们的短信ID状态只有2种!所以用一个boolean表示1个状态是非常大的浪费,实际上1个bit就足够,其余7个bit都浪费了。这就给我们提供了一个思路:能不能用一个bit表示一个短信ID?如果可以的话,空间复杂度相对2.3有可以下降7/8!我们可以利用刚刚讲过的BitSet来实现:

 
   
   
 
  1. public class BitSetTest {

  2.    public static void main(String[] args) {

  3.        BitSet bitSet = new BitSet(256);

  4.        bitSet.set(0);

  5.        bitSet.set(1);

  6.        bitSet.set(2);

  7.        bitSet.set(65);

  8.        // 返回第一个不是1的bit index

  9.        System.out.println(bitSet.nextClearBit(0));

  10.    }

  11. }



版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《BitSet的原理以及应用》的版权归原作者「蹲厕所的熊」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

举报