  For an integer $q\ge 2$, a perfect $q$-hash code $C$ is a block code over
$[q]:=\{1,\ldots,q\}$ of length $n$ in which every subset
$\{\mathbf{c}_1,\mathbf{c}_2,\dots,\mathbf{c}_q\}$ of $q$ elements is
separated, i.e., there exists $i\in[n]$ such that
$\{\mathrm{proj}_i(\mathbf{c}_1),\dots,\mathrm{proj}_i(\mathbf{c}_q)\}=[q]$,
where $\mathrm{proj}_i(\mathbf{c}_j)$ denotes the $i$th position of
$\mathbf{c}_j$. Finding the maximum size $M(n,q)$ of perfect $q$-hash codes of
length $n$, for given $q$ and $n$, is a fundamental problem in combinatorics,
information theory, and computer science. In this paper, we are interested in
asymptotic behavior of this problem. Precisely speaking, we will focus on the
quantity $R_q:=\limsup_{n\rightarrow\infty}\frac{\log_2 M(n,q)}n$.
  A well-known probabilistic argument shows an existence lower bound on $R_q$,
namely $R_q\ge\frac1{q-1}\log_2\left(\frac1{1-q!/q^q}\right)$ \cite{FK,K86}.
This is still the best-known lower bound till now except for the case $q=3$
\cite{KM}. The improved lower bound of $R_3$ was discovered in 1988 and there
has been no progress on the lower bound of $R_q$ for more than $30$ years. In
this paper we show that this probabilistic lower bound can be improved for $q$
from $4$ to $15$ and all odd integers between $17$ and $25$, and \emph{all
sufficiently large} $q$.
