Geek Answers Handbook

Good hash function for an uneven sequence of uniformly distributed bit values?

I have a very specific problem:

I have uniformly random values ​​scattered across a 15x50 grid, and the pattern I want to use corresponds to a 5x5 square of cells centered around any possible grid position.

Thus, the number of samples can vary from 25 (far from the borders, in most cases) to 20, 15 (near the border) to a minimum of 9 (in the corner).

So, although the cell values ​​are random, the location introduces a deterministic change in the length of the sequence.

The size of the hash table is a small number, usually from 50 to 20.

The function will work with a large set of randomly generated grids (several hundred / thousand) and can be called several thousand times for each grid. The positions on the grid can be considered random.

I need a function that could distribute possible 15x50 samples as evenly as possible.

I 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, although not very unbalanced, do not seem to me very smooth. Maybe because the sample is too small, but circumstances make it difficult to run the code on a larger sample, and I would prefer not to write a full test harness if some kind of computer approach has an answer ready for me :).

I'm not sure that pairing values ​​two by one and using a general purpose byte hashing strategy would be the best solution, especially since the number of values ​​may be odd.

17- , , , ( " " ).

, (, , ).

+4
2

, -. ( - ), , , . -- (FNV) .

FNV 8- , () 4-. , " ", . , , (, 4- ).

, . , * << |.

!

"" FNV1a 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: , . , 100% 1. , . , .

+1

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

- . 8- , , . , , , , .

, , , 2 ^ n, mod 64 , , , 3 .

+5

More articles:


All Articles