4

I have a very specific problem:

I have uniformly random values spread on a 15x50 grid and the sample I want to hash corresponds to a square of 5x5 cells centered around any possible grid position.

The number of samples can thus vary from 25 (away from borders, most cases) to 20, 15 (near a border) down to a minimum of 9 (in a corner).

So even though the cell values are random, the location introduces a deterministic variation in the sequence length.

The hash table size is a small number, typically between 50 and 20.

The function will operate on a large set of randomly generated grids (a few hundreds/thousands), and might be called a few thousands times per grid. The positions on the grid can be considered random.

I would like a function that could spread the 15x50 possible samples as evenly as possible.

I have tried the following pseudo-code:

int32 hash = 0;
int i = 0; // I guess i could take any initial value and even be left uninitialized, but fixing one makes the function deterministic
foreach (value in block)
{
    hash ^= (value << (i%28))
    i++
}
hash %= table_size

but the results, though not grossly imbalanced, do not seem very smooth to me. Maybe it's because the sample is too small, but the circumstances make it difficult to run the code on a bigger sample, and I would rather not have to write a complete test harness if some computer savvy has an answer ready for me :).

I am not sure pairing the values two by two and using a general purpose byte hashing strategy would be the best solution, especially since the number of values might be odd.

I have tought of using a 17th value to represent off-grid cells, but that seems to introduce a bias (the sequences from cells near a border will have a lot of "off grid" values).

I am not sure either what would be the best way to test the efficiency of various solutions (how many grids shall I generate to have an idea of the performances, for instance).

14
  • 2
    If these values really are uniformly distributed (and independent), you don't need a hash. Just take the first (or last, or any) eight 4-bit values, interpret them as a single unsigned 32-bit integer, and reduce modulo the table size. Jan 23, 2015 at 0:47
  • NOTE: i is unintialised. NOTE2: everything goes. But: shift, don't modulo, except at the end. Jan 23, 2015 at 0:52
  • @wildplasser actually i might be random at the start, since it will be constrained to [0..27] by the modulo, but initializing it would make the function deterministic (and I simply forgot to do it :)). As for the modulo, you're right, but I find the modulo a bit more readable. I'm not interested in performances as much as in homogeneity.
    – kuroi neko
    Jan 23, 2015 at 0:56
  • 2
    If you seek a hash function for sequences/_blocks_ of four bit values rather than for each four bit value, please say so in the title and near the beginning of the question. Do randomness tests, if they suggest the sequence of hash values might well come from a uniform random source, that's as good as it gets. There's no getting evenly spread for random input. Please substantiate the results … do not seem very smooth to me.
    – greybeard
    Jan 24, 2015 at 7:47
  • 2
    Perhaps this is what greybeard is getting at, but here's a quick experiment to try. Compute a histogram of uniform random (well, cryptographic quality pseudorandom) numbers between 0 inclusive and the table size exclusive. Is that even enough for you? Jan 24, 2015 at 13:32

2 Answers 2

6

http://www.partow.net/programming/hashfunctions/

Here are few different hash function from experts on various fields. Functions are designed for 8bit values, but I am sure you can extend for your case. I dont know what to suggest, but I think that any of them should work better than your current idea.

Problem with current approach you propose is that values are cyclic in field 2^n and if you make mod 64 at the end for example you lost most values out and only last 3 values remains in final result.

1
  • 1
    That's a neat and useful page you linked there. No answer adressed my particular problem directly, but they were all useful, so the bounty went to the poster with the lowest reputation score. Thanks for your help.
    – kuroi neko
    Jan 30, 2015 at 7:56
1
+100

Despite your scepticism I would just shove them through a standard hash function. If they are well randomised (and relatively independent - you don't say) to begin with you probably don't need to do too much work. Fowler-Noll-Vo (FNV) is a good candidate in these circumstances.

FNV operates on a series of 8-bit input and your input is (logically) 4-bit. I would start without even bothering to pack 'two by two' as you describe. If you feel like trying that, just logically pad odd length series with the message length (reduced to a 4 bit value obviously).

I wouldn't expect that packing to improve the hash. It may save you a tiny number of cycles because it swaps a relatively expensive * with a << and a |.

Try both and report back!

Here are implementations of packed and 'normal' versions of FNV1a in C:

#include <inttypes.h>

static const uint32_t sFNVOffsetBasis=2166136261;
static const uint32_t sFNVPrime= 16777619;

const uint32_t FNV1aPacked4Bit(const uint8_t*const pBytes,const size_t pSize) {
    uint32_t rHash=sFNVOffsetBasis;
    for(size_t i=0;i<pSize;i+=2){
        rHash=rHash^(pBytes[i]|(pBytes[i+1]<<4));
        rHash=rHash*sFNVPrime;
    }
    if(pSize%2){//Length is odd. The loop missed the last element.
        rHash=rHash^(pBytes[pSize-1]|((pSize&0x1E)<<3));
        rHash=rHash*sFNVPrime;

    }
    return rHash;
}

const uint32_t FNV1a(const uint8_t*const pBytes,const size_t pSize) {
    uint32_t rHash=sFNVOffsetBasis;
    for(size_t i=0;i<pSize;++i){
        rHash=(rHash^pBytes[i])*sFNVPrime;
    } 
    return rHash;
}

NB: I've edited it to skip the first bit when adding in the length. Obviously the bottom bit of an odd length is 100% biased to 1. I don't know how length is distributed. It may be wiser to put it in at the start than the end.

3
  • 1
    Or even Fowler-Noll-Vo.
    – greybeard
    Jan 24, 2015 at 10:31
  • 1
    @greybeard. Or that too! I appear to have made a hash of my hash ;).
    – Persixty
    Jan 24, 2015 at 10:33
  • 1
    Though none solved my problem entirely, I reckon all 3 answers are to the point and useful, so I will base bounty attribution on the poster's reputation. Lucky you. And my thanks.
    – kuroi neko
    Jan 30, 2015 at 7:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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