The Toeplitz Hash Algorithm describes

hash function A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called ''hash values'', ''hash codes'', ''digests'', or simply ''hashes''. The values are usually ...

s that compute hash values through

matrix multiplication In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the ...

of the key with a suitable

Toeplitz matrix In linear algebra, a Toeplitz matrix or diagonal-constant matrix, named after Otto Toeplitz, is a matrix in which each descending diagonal from left to right is constant. For instance, the following matrix is a Toeplitz matrix: :\qquad\begin a & b ...

. The Toeplitz Hash Algorithm is used in many network interface controllers for receive side scaling. As an example, with the Toeplitz matrix

T

the key

k

results in a hash

h

as follows: :

h = T\cdot k
= \begin1 & 1 & 0 & 1 \\0 & 1 & 1 & 0 \\1 & 0 & 1 & 1 \\\end
\cdot \begin1\\1\\0\\0\\\end
= \begin0 \\1 \\1 \\\end

where the entries are bits and all operations are modulo 2. In implementations the highly redundant matrix is not necessarily explicitly stored.

References

Hash functions {{compu-prog-stub