We present three explicit constructions of hash functions, which exhibit a trade-off between the size of the family (and hence the number of random bits needed to generate a member of the family),and the quality (or error parameter) of the pseudo-random property itachieves. Unlike previous constructions, most notably universal hashing, the size of our families is essentiallyindependent of the size of the domain on which the functions operate.

The first construction is for the {\em mixing} property -- mapping a proportional part of any subset of the domain to any other subset. The othertwo are for the {\em extraction } property -- mapping any subsetof the domain almost uniformly into a range smaller than it. The secondand third constructions handle (respectively) the extreme situations whenthe range is very large or very small.

We provide lower bounds showing our constructions are nearly optimal,and mention some applications of the new constructions.}