CompSci 261, Winter 261, Homework 2

  1. Let $N$ be the number of cells in a given hash table. Define a hash function by choosing two random coefficients $a$ and $b$, and defining the hash value of any key $x$ to be $h(x)=(ax+b)\bmod N$. Then as we saw in class, when $N$ is a prime number, this hash function is $2$-independent: each pair of distinct keys is equally likely to be mapped to any hash value. Is it still $2$-independent for $N=6$? Explain why or why not.

  2. Suppose that $S$ is a set of 32-bit keys, to be used in tabulation hashing by partitioning each key into four bytes, looking up the table values $T[i][b]$ where $i$ is the position of a byte in its key and $b$ is the value of that byte, and combining the results of the lookups by a bitwise exclusive or operation.

    1. Prove that, if $S$ is a nonempty set of three or fewer distinct keys, then there exists a key $k$ in $S$, and a byte position $i$ and byte value $b$ in key $k$, such that $k$ is the only key to use $T[i][b]$ as part of its hash value calculation.

    2. Find a set $S$ of four distinct keys such that every table value $T[i][b]$ that is used to calculate the hash values of these keys is used by more than one of the keys.

  3. Consider a "cuckoo" version of linear probing, as follows. In normal linear probing, we calculate the hash value $h(k)$ of each newly-inserted key $k$ and place $k$ into the first free cell on or after $h(k)$. Instead, in the cuckoo linear probing algorithm, we always place $k$ into cell $h(k)$; then, if there was already a key-value pair at cell $h(k)$, we move it to $h(k)+1$, and if there was already another pair at $h(k)+1$, we move that other pair to $h(k)+2$, etc. Prove that, if $X$ is a sequence of insertions of key-value pairs (with distinct keys) into a cuckoo linear probing hash table, then there exists a different ordering $Y$ for inserting the same key-value pairs into a normal linear probing hash table of the same size (with the same hash function), such that the cuckoo table after $X$ and the normal linear probing table after $Y$ have all keys in the same positions as each other.