オブジェクトがそのハッシュセットに配置されているかどうかを記憶させることができます。ハッシュセットに追加された場合は、ブールフィールドを保存するだけです。次に、HashSet で contains を呼び出す必要はありませんが、オブジェクトのフィールド値を読み取るだけです。このメソッドは、オブジェクトがブール フィールドをチェックする 1 つのハッシュセットに配置されている場合にのみ機能します。
java.util.BitSetアルゴリズムが開始する前にハッシュセットの数がわかっている場合、すべてのハッシュセットを一意の整数で識別できるハッシュセットに含まれるオブジェクトを使用して、一定数のハッシュセットに拡張することができます。
頻繁に呼び出していると言っているのでcontains、新しく生成されたオブジェクトを同等の既存のオブジェクト (オブジェクト プーリング) に置き換えることは理にかなっています。
リクエストに応じて、サンプル コードをいくつか示します。特別なセットの実装は、私のマシンの通常のハッシュ セットよりも約 4 倍高速です。ただし、問題は、このコードがユースケースをどの程度反映しているかです。
public class FastSetContains {
public static class SetContainedAwareObject {
private final int state;
private boolean contained;
public SetContainedAwareObject(int state) {
this.state = state;
}
public void markAsContained() {
contained = true;
}
public boolean isContained() {
return contained;
}
public void markAsRemoved() {
contained = false;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + state;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
SetContainedAwareObject other = (SetContainedAwareObject) obj;
if (state != other.state)
return false;
return true;
}
}
public static class FastContainsSet extends
HashSet<SetContainedAwareObject> {
@Override
public boolean contains(Object o) {
SetContainedAwareObject obj = (SetContainedAwareObject) o;
if (obj.isContained()) {
return true;
}
return super.contains(o);
}
@Override
public boolean add(SetContainedAwareObject e) {
boolean add = super.add(e);
e.markAsContained();
return add;
}
@Override
public boolean addAll(Collection<? extends SetContainedAwareObject> c) {
boolean addAll = super.addAll(c);
for (SetContainedAwareObject o : c) {
o.markAsContained();
}
return addAll;
}
@Override
public boolean remove(Object o) {
boolean remove = super.remove(o);
((SetContainedAwareObject) o).markAsRemoved();
return remove;
}
@Override
public boolean removeAll(Collection<?> c) {
boolean removeAll = super.removeAll(c);
for (Object o : c) {
((SetContainedAwareObject) o).markAsRemoved();
}
return removeAll;
}
}
private static final Random random = new Random(1234L);
private static final int additionalObjectsPerIteration = 10;
private static final int iterations = 100000;
private static final int differentObjectCount = 100;
private static final int containsCountPerIteration = 50;
private static long nanosSpentForContains;
public static void main(String[] args) {
Map<SetContainedAwareObject, SetContainedAwareObject> objectPool = new HashMap<>();
// switch comment use different Set implementaiton
//Set<SetContainedAwareObject> set = new FastContainsSet();
Set<SetContainedAwareObject> set = new HashSet<>();
//warm up
for (int i = 0; i < 100; i++) {
addAdditionalObjects(objectPool, set);
callSetContainsForSomeObjects(set);
}
objectPool.clear();
set.clear();
nanosSpentForContains = 0L;
for (int i = 0; i < iterations; i++) {
addAdditionalObjects(objectPool, set);
callSetContainsForSomeObjects(set);
}
System.out.println("nanos spent for contains: " + nanosSpentForContains);
}
private static void callSetContainsForSomeObjects(
Set<SetContainedAwareObject> set) {
int containsCount = set.size() > containsCountPerIteration ? set.size()
: containsCountPerIteration;
int[] indexes = new int[containsCount];
for (int i = 0; i < containsCount; i++) {
indexes[i] = random.nextInt(set.size());
}
Object[] elements = set.toArray();
long start = System.nanoTime();
for (int index : indexes) {
set.contains(elements[index]);
}
long end = System.nanoTime();
nanosSpentForContains += (end - start);
}
private static void addAdditionalObjects(
Map<SetContainedAwareObject, SetContainedAwareObject> objectPool,
Set<SetContainedAwareObject> set) {
for (int i = 0; i < additionalObjectsPerIteration; i++) {
SetContainedAwareObject object = new SetContainedAwareObject(
random.nextInt(differentObjectCount));
SetContainedAwareObject pooled = objectPool.get(object);
if (pooled == null) {
objectPool.put(object, object);
pooled = object;
}
set.add(pooled);
}
}
}
別の編集：
以下を Set.contains 実装として使用すると、通常のハッシュセットよりも約 8 倍高速になります。
@Override
public boolean contains(Object o) {
SetContainedAwareObject obj = (SetContainedAwareObject) o;
return obj.isContained();
}
編集:
この手法には、OpenJPA のクラス拡張と共通点があります。OpenJPA の機能拡張により、エンティティー・マネージャーによって使用される永続状態をクラスが追跡できるようになりました。提案された方法では、オブジェクト自体がアルゴリズムによって使用されるセットに含まれているかどうかを追跡できます。