Saving on array initialization
This is a very general trick, which can be used for other purposes than hashing. Below I give an implementation (in pseudo-code).

Let three uninitialized vectors $A$, $P$ and $V$ of size $n$ each. We will use these to do the operations requested by our data structure. We also maintain a variable $pos$. The operations are implemented as following:

init:
  pos &lt;- 0

set(i,x):
if not(V[i] &lt; pos and P[V[i]] = i) 
  V[i] &lt;- pos, P[pos] &lt;- i, pos &lt;- pos + 1
A[i] &lt;- x

get(i):
if (V[i] &lt; pos and P[V[i]] = i) 
  return A[i] 
else 
  return empty 


The array $A$ simply stores the values that are passed through the $set$ procedure. The arrays $V$ and $P$ work as certificates that can tell if a given position in $A$ has been initialized.

Note that at every moment the elements in $P$ ranging from $0$ to $pos-1$ are initialized. We can therefore safely use these values as a certificate for the initialized values in $A$.
For every position $i$ in $A$ that is initialized, there is a corresponding element in the vector $P$ whose value is equal to $i$. This is pointed by $V[i]$. Therefore, if we look at the corresponding element, $P[V[i]]$ and its value is $i$, we know that $A[i]$ has been initialized (since $P$ never lies, because all the elements that we're considering are initialized). Similarly, if $A[i]$ is not initialized, then $V[i]$ may point either to a position in $P$ outside the range $0..pos-1$, when we know for sure that it's not initialized, or may point to a position within that range. But this particular $P[j]$ corresponds to a different position in $A$, and therefore $P[j] \neq i$, so we know that $A[i]$ has not been initialized. 

It's easy to see that all these operations are done in constant time. Also, the space used is $O(n)$ for each of the vectors, and $O(1)$ for the variable $pos$, therefore $O(n)$ in total.