automatically universal, and any universal hashing scheme can be converted into a 2-independent scheme by storing a random number x as part of the initialization phase of the algorithm and adding x to each hash value. Thus, universality is essentially the same as 2-independence. However, k-independence for larger values of k is a stronger property, held by fewer hashing algorithms. As observe, tabulation hashing is 3-independent but not 4-independent. For any single key x, T[x0,0] is equally likely to take on any hash value, and the exclusive or of T[x0,0] with the remaining table values does not change this property. For any two keys x and y, x is equally likely to be mapped to any hash value as before, and there is at least one position i where xi ≠ yi; the table value T[yi,i] is used in the calculation of h(y) but not in the calculation of h(x), so even after the value of h(x) has been determined, h(y) is equally likely to be any valid hash value. Similarly, for any three keys x, y, and z, at least one of the three keys has a position i where its value zi differs from the other two, so that even after the values of h(x) and h(y) are determined, h(z) is equally likely to be any valid hash value. However, this reasoning breaks down for four keys because there are sets of keys w, x, y, and z where none of the four has a byte value that it does not share with at least one of the other keys. For instance, if the keys have two bytes each, and w, x, y, and z are the four keys that have either zero or one as their byte values, then each byte value in each position is shared by exactly two of the four keys. For these four keys, the hash values computed by tabulation hashing will always satisfy the equation , whereas for a 4-independent hashing scheme the same equation would only be satisfied with probability 1/m. Therefore, tabulation hashing is not 4-independent. Application Because tabulation hashing is a universal hashing scheme, it can be used in any hashing-based algorithm in which universality is sufficient. For instance, in hash chaining, the expected time per operation is proportional to the sum of collision probabilities, which is the same for any universal scheme as it would be for truly