hash - Double Hashing vs Linear Hashing -

i'm writing double hash table takes integer.

unsigned int doublehashtable::hashfunction1(unsigned int const data) {    return (data % gettablesize()); }  unsigned int doublehashtable::hashfunction2(unsigned int const data, unsigned int count) {    return ((hashfunction1(data) + count * (5 - (data % 5)) % gettablesize())); } 

and trying insert data table setdata()

void doublehashtable::setdata(unsigned int const data) {    unsigned int probe = hashfunction1(data);     if (m_table[probe].getstatus())    {       unsigned int count = 1;       while (m_table[probe].getstatus() && count <= gettablesize())       {          probe = hashfunction2(data, count);          count++;       }    }     m_table[probe].insert(data); } 

after put 100 of integer items table size of 100, table shows me of indexes left blank. know, takes o(n) worst case. question is, item should inserted table no empty space takes worst case of search time, right? can't find problem of functions.

additional question. there well-known algorithms hash , purpose of double hashing makes less collision as possible, h2(t) backup h1(t). but, if well-known hashing algorithm (like md5, sha , other, i'm not talking security, well-known algorithm) faster , well-distribute, why need double hashing?

thanks!

when testing hash functions, there may high collisions pathological inputs (=those break hash function). these inputs can discovered reversing hash function can lead attacks (this real concern internet routers have limited space hash tables). no adversary, time of such hash table after inputs can grow , become linear in worst case.

double hashing method of resolving hash collisions try solve problem of linear growth on pathological inputs. linear probing or open addressing popular choices. however, number of inputs must lower table size in these cases, unless hash table can grow dynamically.

to answer second question (now have fixed code on own), in nutshell, double hashing better-suited small hash tables, , single hashing better-suited large hash tables.