Database Reference
In-Depth Information
for(int i=0;i<outputs.length;i++) {
hashes[i].reset();
try {
outputs[i].writeObject(arg0);
outputs[i].flush();
bits.set(hashes[i].hash() % m);
} catch(IOException e) { }
}
return true;
}
return false;
}
Part of the preceding implementation includes a check for the element using
contains
so that the method correctly returns whether this is considered
to be a new element. An element can only be considered to be in the set if
all the registers indicated by the k hash functions are set to 1. You can easily
check this with the following implementation:
public boolean contains(Object arg0) {
for(int i=0;i<outputs.length;i++) {
try {
hashes[i].reset();
outputs[i].writeObject(arg0);
outputs[i].flush();
if(!bits.get(hashes[i].hash() % m)) return false;
} catch(IOException e) { }
}
return true;
}
It is easy to see how this implementation can lead to false positives. As
more and more elements are added to the set, it is more and more likely
that at least one of the elements will map to each of the registers of this
new item to enter into the set. When that happens, the implementation of
contains()
returns
true
for the item even when it hasn't been entered.
