The Toeplitz Hash Algorithm describes

hash function A hash function is any Function (mathematics), function that can be used to map data (computing), data of arbitrary size to fixed-size values, though there are some hash functions that support variable-length output. The values returned by a ...

s that compute hash values through

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

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 & ...

. 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