Java integer hash set micro-benchmark

setbench.java

import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashSet;
import com.stumbleupon.mr.HashIntSet;  // OpenJDK's HashSet hacked to use built-in `int'
import gnu.trove.set.hash.TIntHashSet;

import com.google.caliper.Param;
import com.google.caliper.SimpleBenchmark;

final class setbench {

  public static class HashSetBench extends SimpleBenchmark {
    private HashSet<Integer> hs;

    @Param int size;

    @Override protected void setUp() {
      hs = new HashSet<Integer>(size);
      for (int i = 0; i < size; i++) {
        hs.add(i);
      }
    }

    public int timeContains(final int n) {
      int dummy = 0;
      for (int i = 0; i < n; i++) {
        if (hs.contains(i)) {
          dummy++;
        }
      }
      return dummy;
    }
  }

  public static class HashIntSetBench extends SimpleBenchmark {
    private HashIntSet hs;

    @Param int size;

    @Override protected void setUp() {
      hs = new HashIntSet(size);
      for (int i = 0; i < size; i++) {
        hs.add(i);
      }
    }

    public int timeContains(final int n) {
      int dummy = 0;
      for (int i = 0; i < n; i++) {
        if (hs.contains(i)) {
          dummy++;
        }
      }
      return dummy;
    }
  }

  public static class TIntHashSetBench extends SimpleBenchmark {
    private TIntHashSet hs;

    @Param int size;

    @Override protected void setUp() {
      hs = new TIntHashSet(size);
      for (int i = 0; i < size; i++) {
        hs.add(i);
      }
    }

    public int timeContains(final int n) {
      int dummy = 0;
      for (int i = 0; i < n; i++) {
        if (hs.contains(i)) {
          dummy++;
        }
      }
      return dummy;
    }
  }

}

contains() speed

HashSet<Integer>

 size   ns linear runtime
  100 10.2 ============================
 1000 10.7 =============================
10000 11.0 ==============================

HashIntSet

 size   ns linear runtime
  100 5.19 ============================
 1000 5.26 ============================
10000 5.52 ==============================

TIntHashSet

 size   ns linear runtime
  100 11.2 ======================
 1000 15.0 ==============================
10000 11.3 ======================

Memory footprint

• HashSet: 48 bytes per item (32 bytes for HashMap$Entry + 16 bytes for Integer)
• HashIntSet: 24 bytes per HashIntMap$Entry
• TIntHashSet: 5 bytes per entry (one int in an array and one byte in another array).