作者：yyaadet

First let's see what data struction he used.

struct entry

{

    void *k, *v;

    unsigned int h;

    struct entry *next;

};

struct hashtable {

    unsigned int tablelength;

    struct entry **table;

    unsigned int entrycount;

    unsigned int loadlimit;

    unsigned int primeindex;

    unsigned int (*hashfn) (void *k);

    int (*eqfn) (void *k1, void *k2);

};

static const unsigned int primes[] = {

53, 97, 193, 389,

769, 1543, 3079, 6151,

12289, 24593, 49157, 98317,

196613, 393241, 786433, 1572869,

3145739, 6291469, 12582917, 25165843,

50331653, 100663319, 201326611, 402653189,

805306457, 1610612741

};

const unsigned int prime_table_length = sizeof(primes)/sizeof(primes[0]);

const float max_load_factor = 0.65;

The import function is creat_hashtable here.

struct hashtable *create_hashtable(unsigned int minsize,

                 unsigned int (*hashf) (void*),

                 int (*eqf) (void*,void*))

{

    struct hashtable *h;

    unsigned int pindex, size = primes[0];

    /* Check requested hashtable isn't too large */

    if (minsize > (1u << 30)) return NULL;

    /* Enforce size as prime */

    for (pindex=0; pindex < prime_table_length; pindex++) {

        if (primes[pindex] > minsize) { size = primes[pindex]; break; }

    }

    h = (struct hashtable *)malloc(sizeof(struct hashtable));

    if (NULL == h) return NULL; /*oom*/

    h->table = (struct entry **)malloc(sizeof(struct entry*) * size);

    if (NULL == h->table) { free(h); return NULL; } /*oom*/

    memset(h->table, 0, size * sizeof(struct entry *));

    h->tablelength  = size;

    h->primeindex   = pindex;

    h->entrycount   = 0;

    h->hashfn       = hashf;

    h->eqfn         = eqf;

    h->loadlimit    = (unsigned int) ceil(size * max_load_factor);

    return h;

}

We can find that "creat_hashtable" is initialing some data.

unsigned int hash(struct hashtable *h, void *k)

{

    /* Aim to protect against poor hash functions by adding logic here

     * - logic taken from java 1.4 hashtable source */

    unsigned int i = h->hashfn(k);

    i += ~(i << 9);

    i ^=  ((i >> 14) | (i << 18)); /* >>> */

    i +=  (i << 4);

    i ^=  ((i >> 10) | (i << 22)); /* >>> */

    return i;

}

I have not understood hash(struct hashtable,void *);