Toeplitz Hash Algorithm

The Toeplitz Hash Algorithm describes hash functions that compute hash values through matrix multiplication of the key with a suitable Toeplitz matrix. 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=\left(\begin{array}{cccc}1& 1& 0& 1\\ 0& 1& 1& 0\\ 1& 0& 1& 1\end{array}\right)\cdot \left(\begin{array}{c}1\\ 1\\ 0\\ 0\end{array}\right)=\left(\begin{array}{c}0\\ 1\\ 1\end{array}\right)$

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