Hash Tables

1)What is the expected time to search for an element in a hash table?

2)What is the worst case time for searching a element using hash table.

3)Demonstrate the insertion of the keys 5,28,19,15,20,33,12,17,10 into a hash table with collisions resolved by chaining.Let the table have 9 slots,and let the hash function be h(k)=k mod 9.

4)Suppose we use a hash function to hash m distinct keys into an array T of length m.Assuming simple uniform hashing,what is the expected number of collisions?

5)Suggest how storage for elements can be allocated and deallocated within the hash table itself by linking all unused slots into a free list.Assume that one slot can store a flag and either one element plus a pointer or two pointers.Does the free list need to be doublt linked,or does a singly linked free list suffice?

6)Suppose we wish to search a linked list of length n,where each element contains a key k along with a hash value h(k).Each key is a long character string.How might we take advantage of the hash values when searching the list for an element with a given key?