c++hashmurmurhash

is it possible for MurmurHash3 to produce a 64 bit hash where the upper 32 bits are all 0?


Looking at https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp I don't think so but I wanted to check.

The situation is this, if I have a key of 1,2,3 or 4 bytes, is it reliable to simply take the numeric value of those bytes instead of hashing to 8 bytes, or will those cause a collision for keys greater than 4 bytes that were hashed with murmur3?


Solution

  • Such property is a bad property for a hash function. It effectively shrinks function co-domain, increasing collision chance, so it seems very unlikely.

    Moreover, this blog post provides an inversion function for MurmurHash:

    uint64 murmur_hash_64(const void * key, int len, uint64 seed)
    {
        const uint64 m = 0xc6a4a7935bd1e995ULL;
        const int r = 47;
    
        uint64 h = seed ^ (len * m);
    
        const uint64 * data = (const uint64 *)key;
        const uint64 * end = data + (len / 8);
    
        while (data != end)
        {
    #ifdef PLATFORM_BIG_ENDIAN
            uint64 k = *data++;
            char *p = (char *)&k;
            char c;
            c = p[0]; p[0] = p[7]; p[7] = c;
            c = p[1]; p[1] = p[6]; p[6] = c;
            c = p[2]; p[2] = p[5]; p[5] = c;
            c = p[3]; p[3] = p[4]; p[4] = c;
    #else
            uint64 k = *data++;
    #endif
    
            k *= m;
            k ^= k >> r;
            k *= m;
    
            h ^= k;
            h *= m;
        }
    
        const unsigned char * data2 = (const unsigned char*)data;
    
        switch (len & 7)
        {
        case 7: h ^= uint64(data2[6]) << 48;
        case 6: h ^= uint64(data2[5]) << 40;
        case 5: h ^= uint64(data2[4]) << 32;
        case 4: h ^= uint64(data2[3]) << 24;
        case 3: h ^= uint64(data2[2]) << 16;
        case 2: h ^= uint64(data2[1]) << 8;
        case 1: h ^= uint64(data2[0]);
            h *= m;
        };
    
        h ^= h >> r;
        h *= m;
        h ^= h >> r;
    
        return h;
    }
    
    uint64 murmur_hash_64_inverse(uint64 h, uint64 seed)
    {
        const uint64 m = 0xc6a4a7935bd1e995ULL;
        const uint64 minv = 0x5f7a0ea7e59b19bdULL; // Multiplicative inverse of m under % 2^64
        const int r = 47;
    
        h ^= h >> r;
        h *= minv;
        h ^= h >> r;
        h *= minv;
    
        uint64 hforward = seed ^ (((uint64)8) * m);
        uint64 k = h ^ hforward;
    
        k *= minv;
        k ^= k >> r;
        k *= minv;
    
    #ifdef PLATFORM_BIG_ENDIAN
        char *p = (char *)&k;
        char c;
        c = p[0]; p[0] = p[7]; p[7] = c;
        c = p[1]; p[1] = p[6]; p[6] = c;
        c = p[2]; p[2] = p[5]; p[5] = c;
        c = p[3]; p[3] = p[4]; p[4] = c;
    #endif
    
        return k;
    }
    

    You can find as many inputs with hash values <2^32 as you want.

    Your question about reliability doesn't make much sense: you always must be ready to handle collisions properly. From my practice, I do not recommend to use plain integers or pointer values as a hash, as they can produce undesired patterns.