Description
why load factor is this

Suppose that we use hash chaining for a hash table with n keys, but with a hash table that is too small, so that the load factor is 3 log n. (This will cause operations on the hash table to take logarithmic time rather than constant time.) Use the Cherno bound and linearity of expectation to prove that, for a random hash function and for this load factor, the expected number of hash chains that are at most twice
their expected size is o(1).

In Python, there is a function hash() built into the language that can map most types of object to
an integer. For an integer x, the value of hash(x) is just x mod 2^{31} 1, so for all integers smaller than 2^{31} 1, the hash of x is just x itself. Other types of objects have lesspredictable hash values. The hash value, computed in this way, is used as the hash function for dictionaries by taking the result modulo the dictionary size. Python uses open addressing, but not linear probing, for its dictionaries.
Suppose you are given a hash table of xed size s, initially empty, and that (unlike Python) you are going to use linear probing for this table, using the Python hash() function. Describe a sequence of s=2 integers such that, when inserted in that sequence into the table, the average time per insertion is (s).

Suppose that we insert n keys into an initiallyempty cuckoo hash table, all of them successfully. Suppose also that, of the two hash functions h1 and h2 used for this insertion, h1 is bad and returns the same hash value for all n of the keys. In this scenario, how many pairs of keys can have equal values of h2? Use the case analysis from the lecture notes to prove that, in this scenario, all insertions take worstcase time O(1).

The algebraic method for constructing a 2independent hash function from the lecture notes chooses a large nonrandom prime number p and two random numbers a_{0} and a_{1} mod p, and de nes the hash value for x to be (a_{1}x + a_{0}) mod p mod N. Suppose we try to simplify this by skipping the \mod p” part. Instead, we choose two random numbers a_{0} and a_{1} mod N de ning the hash value to be (a_{1}x + a_{0}) mod N. Find a value of N for which this is not 2independent, and explain why not.
1