An Open Source Hashtable

xiaoxiao2021-04-04  230

First Let's See What Data Struction HE.

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 (* k) (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

IF (Primes [PINDEX]> MINSIZE) {size = primes [pindex];

}

H = (struct hashtable *) malloc (Struct Hashtable);

IF (null == h) return null; / * oom * /

H-> Table = (struct entry **) malloc (Struct Entry *) * size;

IF (null == h-> Table) {free (h); return null;} / * oom * /

MEMSET (H-> Table, 0, Size * SizeOf (struct entry *));

H-> TABLENGTH = Size;

H-> primeIndex = pindex;

H-> entrycount = 0;

H-> hashfn = hashf;

H-> EQFN = EQF;

H-> loadLimit = (unsigned int) CEIL (size * max_load_factor); returnh;

}

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 *);

转载请注明原文地址:https://www.9cbs.com/read-131968.html

New Post(0)