current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 0 down vote favorite

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?

share|improve this question
    
Please see what you may and may not do after receiving answers. –  Simon Forsberg♦ May 8 at 12:15

1 Answer 1

up vote 1 down vote

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;
share|improve this answer
    
The requirement is that it be a sparse array, but I think you're right about the l part. –  SuperJedi224 May 8 at 10:51
    
@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. –  JS1 May 8 at 17:09
    
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. –  SuperJedi224 May 8 at 18:23
    
@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. –  JS1 May 8 at 18:39
    
The current version of the full code can be seen here: pastebin.com/9QNz9arR –  SuperJedi224 May 8 at 23:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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