1. If a hash table contains tablesize positions and n records currently occupy the table, the load factor lf is defined as n/tablesize. Suppose a hash function uniformly distributes n keys over the tablesize positions of the table and lf is the load factor of the table. Show that upon insertion, (n-1)* lf/2 of the keys in the table collide with a previously entered key.
2. Assume that n random positions of a tablesize- element hash table are occupied, using hash and rehash functions that are equally likely to produce any index in the table. Show that the average number of comparisons needed to insert a new element is (tablesize + 1)/(tablesize-n+1). Explain why linear probing does not satisfy this condition.
