0
\$\begingroup\$

I have this method in one of the java classes I'm working on (an implementation of a counting bloom filter):

private int[] hash(V v){
    Random r=new Random(v.hashCode());
    int l=r.nextInt(size);
    int[] keys=new int[size];
    for(int i=0;i<bpe;i++){
        keys[(r.nextInt(size)+l)%size]=1;
    }
    return keys;
}

Where:

  • V is one of the type parameters for the enclosing generic class
  • size is a field set on initialization, defaults to 64 unless specified otherwise from the constructor
  • bpe is also a field, set on initialization to Math.max(5, Math.min(size/8,(int)Math.sqrt(size)))

Is there a better way to do this?

\$\endgroup\$
1
\$\begingroup\$

Wasting space?

I don't know if there's a better way of generating your hashed bits, but you are using 32x the amount of space that you need to. I would suggest using all the bits in your keys array rather than just 1 bit per int.

What is l for?

One thing I don't understand about your hash is the use of l. You are already using random numbers to generate your hash, so why do you need to add two random numbers together? Is it supposed to generate more randomness? I don't think it does.

An example of packing the bits

// Only allocate one int for every 32 bits.
keys = new int[(size+31)/32];
for(int i=0;i<bpe;i++){
    int bitNum = (r.nextInt(size)+l)%size;
    keys[bitNum >> 5] |= (1 << (bitNum & 31));
}

To retrieve the bit, previously, you would do:

isBitSet = keys[bitNum] != 0;

Now you would do:

isBitSet = (keys[bitNum >> 5] & (1 << (bitNum & 31))) != 0;
\$\endgroup\$
  • \$\begingroup\$ The requirement is that it be a sparse array, but I think you're right about the l part. \$\endgroup\$ – SuperJedi224 May 8 '15 at 10:51
  • \$\begingroup\$ @SuperJedi224 Does that mean use the SparseArray class? The SparseArray class saves memory by not allocating the full array. I can't imagine that allocating a full array of ints would qualify as a "sparse" array. \$\endgroup\$ – JS1 May 8 '15 at 17:09
  • \$\begingroup\$ If you mean to reduce space, I could do this by storing the indices of the ones in a smaller array of length bpe, but that would require restructuring all the other methods that call this. \$\endgroup\$ – SuperJedi224 May 8 '15 at 18:23
  • \$\begingroup\$ @SuperJedi224 I don't understand the requirements of this hash function. You mention that you are using this for a bloom filter. But if you are doing so, you would want to use the least amount of space possible, which would mean packing the bits together instead of using one int per bit. Maybe if you showed how the bloom filter was going to use the keys array it would help. I'll show an example of how to pack the bits. \$\endgroup\$ – JS1 May 8 '15 at 18:39
  • \$\begingroup\$ The current version of the full code can be seen here: pastebin.com/9QNz9arR \$\endgroup\$ – SuperJedi224 May 8 '15 at 23:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.