In this paper we use linear algebraic methods to analyze the performance of several classes of hash functions, including the class H2 presented by Carter and Wegman. Suppose H is a suitable class, the hash functions in H map A to B, S is any subset of A whose size is equal to that of B, and x is any element of A. We show that the probability of choosing a function from H which maps x to the same value as more than t other elements of S is no greater than min (1/t2, 11/t4). Consider a database storage and retrieval system implemented using hashing and a linked list collision resolution strategy. A corollary of the main result is that the probability that the system would perform more than t times more slowly than expected is no greater than ...