Java集包含所有性能

Question

我正在尝试在java中比较两个哈希集，它们都包含多个字符，但是我需要执行很多次(10^5~8)，所以我正在尝试提高性能。 具体来说，我想比较的是集合A是否包含B或集合B包含A以及它们的大小差<= 2。这是我想出的两种方法，

1. 使用 set containsall 方法，
2. 由于集合只能包含26个字母，所以我不再使用哈希集，我使用位运算，如果虚拟集合有'a'，那么我给1；如果它有'b'，我给出1<<1，即2；如果它有“c”，我给出 1<<2，即 4，然后将所有值加在一起作为该集合的值。然后我进行异或并计算结果中 1 的数量。

哪种方法会更好？

Answer 1

如果我理解正确的话，应该使用第二种方法。

我会这样做:

public class IntBitSet {

  private int set = 0;
  private final int firstChar = (byte) 'a';
  private final int lastChar = (byte) 'z';

  public int size() {
    return Integer.bitCount(set);
  }

  public boolean isEmpty() {
    return set == 0;
  }

  public boolean contains(char c) {
    assert c <= lastChar && c >= firstChar : c + " is not a valid value.";

    return ((set >>> (c - firstChar) ) & 1) != 0;
  }

  public void add(char c) {
    assert c <= lastChar && c >= firstChar : c + " is not a valid value.";

    set = set | (1 << (c - firstChar));
  }

  public void remove(char c) {
    assert c <= lastChar && c >= firstChar : c + " is not a valid value.";

    set = set & ~(1 << (c - firstChar));
  }

  public boolean containsAll(IntBitSet c) {
    return (this.set & c.set) == c.set;
  }

  public void clear() {
    set = 0;
  }
}

和单元测试。

  import org.junit.Test;
  import static org.junit.Assert.*;

  public class IntBitSetTest {

    public IntBitSetTest() {
    }

    @Test
    public void testSize() {
      System.out.println("size");
      IntBitSet instance = new IntBitSet();

      int count = 0;
      for(char c = 'a'; c <= 'z'; c+=3) {
        instance.add(c);
        count++;
      }

      assertEquals(count, instance.size());

    }

    @Test
    public void testIsEmpty() {
      System.out.println("isEmpty");
      IntBitSet instance = new IntBitSet();

      assertTrue(instance.isEmpty());

      instance.add('g');
      assertFalse(instance.isEmpty());

    }

    @Test
    public void testContains() {
      System.out.println("contains");
      IntBitSet instance = new IntBitSet();

      for(char c = 'a'; c <= 'z'; c++) {
        instance.add(c);
      }

      instance.remove('o');
      instance.remove('u');
      instance.remove('s');

      assertTrue(instance.contains('a'));
      assertTrue(instance.contains('d'));
      assertTrue(instance.contains('i'));

      assertFalse(instance.contains('o'));
      assertFalse(instance.contains('u'));
      assertFalse(instance.contains('s'));
    }

    @Test
    public void testAdd() {
      System.out.println("add");
      IntBitSet instance = new IntBitSet();
      instance.add('b');
      assertFalse(instance.contains('a'));
      assertTrue(instance.contains('b'));
      assertFalse(instance.contains('c'));
      assertFalse(instance.contains('d'));
      assertFalse(instance.contains('e'));
      assertFalse(instance.contains('f'));
      assertFalse(instance.contains('g'));
      assertFalse(instance.contains('h'));
      assertFalse(instance.contains('i'));
      assertFalse(instance.contains('j'));
      assertFalse(instance.contains('k'));
      assertFalse(instance.contains('l'));
      assertFalse(instance.contains('m'));
      assertFalse(instance.contains('n'));
      assertFalse(instance.contains('p'));
      assertFalse(instance.contains('q'));
      assertFalse(instance.contains('r'));
      assertFalse(instance.contains('s'));
      assertFalse(instance.contains('t'));
      assertFalse(instance.contains('u'));
      assertFalse(instance.contains('v'));
      assertFalse(instance.contains('w'));
      assertFalse(instance.contains('x'));
      assertFalse(instance.contains('y'));
      assertFalse(instance.contains('z'));
    }

    @Test
    public void testRemove() {
      System.out.println("remove");

      IntBitSet instance = new IntBitSet();

      for(char c = 'a'; c <= 'z'; c++) {
        instance.add(c);
      }

      instance.remove('e');

      assertTrue(instance.contains('a'));
      assertTrue(instance.contains('b'));
      assertTrue(instance.contains('c'));
      assertTrue(instance.contains('d'));
      assertFalse(instance.contains('e'));
      assertTrue(instance.contains('f'));
      assertTrue(instance.contains('g'));
      assertTrue(instance.contains('h'));
      assertTrue(instance.contains('i'));
      assertTrue(instance.contains('j'));
      assertTrue(instance.contains('k'));
      assertTrue(instance.contains('l'));
      assertTrue(instance.contains('m'));
      assertTrue(instance.contains('n'));
      assertTrue(instance.contains('p'));
      assertTrue(instance.contains('q'));
      assertTrue(instance.contains('r'));
      assertTrue(instance.contains('s'));
      assertTrue(instance.contains('t'));
      assertTrue(instance.contains('u'));
      assertTrue(instance.contains('v'));
      assertTrue(instance.contains('w'));
      assertTrue(instance.contains('x'));
      assertTrue(instance.contains('y'));
      assertTrue(instance.contains('z'));
    }

    @Test
    public void testContainsAll() {
      System.out.println("containsAll");

      IntBitSet instance1 = new IntBitSet();
      IntBitSet instance2 = new IntBitSet();
      IntBitSet instance3 = new IntBitSet();

      for(char c = 'a'; c <= 'z'; c+=3) {
        instance1.add(c);
        instance2.add(c);
        if(c % 2 == 0)
          instance3.add(c);
      }

      assertTrue(instance1.containsAll(instance2));
      assertTrue(instance1.containsAll(instance3));
      assertFalse(instance3.containsAll(instance1));
    }

    @Test
    public void testClear() {
      System.out.println("clear");
      IntBitSet instance = new IntBitSet();

      instance.add('z');

      instance.clear();
      assertTrue(instance.size() == 0);
      assertTrue(instance.isEmpty());

    }
  }