hash table

our next topic is hash table,a technique that used to store,search and get information in O(1) time;
as a instruction,I thought I should show a definition first,what is hash table?here we go,hash table is a dictionary in which keys(or information) are mapped into array positions by hash function.
what is the scheme when we come across a hash table problem?
first,we need to choose a proper hash function to tackle the key;
then,decide how to deal with the value returned from hash function,since there is a hitch called collision,that is,two absolutely different key value will get the same mapped value with the corresponding hash function;

we will open with how to resolve the collision;
there are two methods,one is chaining,the other is open-addressing;
in chaining,we can place all elements in a linked list which hash to the same slot,whose fundamentle operations are easy to be implemented,such as insert,search,delete...etc;

about hash function;
there are three schemes for devising a suitable hash fucntion;
ps.in what follows,we interpret keys as natural numbers;
one is division method,one is multiplication method,the last is universal hashing;
for the division method we have model likes h(n)=n mod m,for which we get the rmainder of the natural number n divided by m,whos optimal value may be a prime not too close to a power of 2.

to be continued...
with candy heart.