Not sure if BitSet is a good choice here. Although _most_ code uses tags starting near zero, I've definitely written code that creates a tag at at 2,000,000 or so. BitSets aren't sparse like that.