#6 Use Bloom filters for instanceof

[Attila Szegedi]

Yesterday I read about the Bloom filter on <http://en.
wikipedia.org/wiki/Bloom_filter>, and it strikes me as a
nice way to optimize the negative case of instanceof
operations (that is, when the object is not instance of the
tested class). It could be as quick as a bitwise AND of
two 64-bit ints. Positive cases (when the object is
instance of the tested class) wouldn't benefit from it,
though.

Each class could have an associated 64-bit value (the
bloom hash key) with a certain number of bits set to 1 (i.
e. exactly 3 bits, randomly selected), and another field
with the bitwise OR of bloom keys of all interfaces/
superclasses (the class' is-a hash). Then "obj instanceof
clazz" could first do a bitwise AND of the tested object's
class is-a hash (let it be h) and the clazz's bloom hash
key (let it be k). If (h & k != k), then instanceof can return
false. Otherwise, the conventional check by traversing
the inheritance hierarchy should be made.

I'm not proposing this optimization for checkcast as well
because with checkcast the expectation is that it
succeeds in vast majority of cases.

Just an idea - handle as you see fit :-)