objective-ciosframeworksperfect-hash

What is the better way to implement a perfect hash function for an iOS app?


I need to create a perfect hash for a list of string identifiers, so before to begin with this implementation (i have never did it before) i want to know if there is any good framework or good tutorial that could be useful?

Thanks!


Solution

  • I use the MurmurHash written by Austin Appleby:

    unsigned int Hash (const char* buffer, size_t size, unsigned seed)
    {
        const unsigned int m = 0x5bd1e995;
        const int r = 2;
        unsigned int h = seed ^ (unsigned int)size;
        const unsigned char* data = (const unsigned char*)buffer;
    
        while(size >= 4)
        {
            unsigned int k;
    
            k = data[0];
            k |= data[1] << 8;
            k |= data[2] << 16;
            k |= data[3] << 24;
    
            k *= m;
            k ^= k >> r;
            k *= m;
    
            h *= m;
            h ^= k;
    
            data += 4;
            size -= 4;
        }
    
        switch(size)
        {
        case 3:         h ^= data[2] << 16;
        case 2:         h ^= data[1] << 8;
        case 1:         h ^= data[0];
            h *= m;
        }
    
        h ^= h >> 13;
        h *= m;
        h ^= h >> 15;
    
        return h;
    }
    

    But ultimately your choice of hashing function depends on the trade-off between quality and speed.