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.^[1] The Toeplitz Hash Algorithm is used in many network interface controllers for receive side scaling.^{[2] [3]}

As an example, with the Toeplitz matrix ${\displaystyle T}${\displaystyle T} the key ${\displaystyle k}${\displaystyle k} results in a hash ${\displaystyle h}${\displaystyle h} as follows:

${\displaystyle h=T\cdot k={\begin{pmatrix}1&1&0&1\0円&1&1&0\1円&0&1&1\\\end{pmatrix}}\cdot {\begin{pmatrix}1\1円\0円\0円\\\end{pmatrix}}={\begin{pmatrix}0\1円\1円\\\end{pmatrix}}}${\displaystyle h=T\cdot k={\begin{pmatrix}1&1&0&1\0円&1&1&0\1円&0&1&1\\\end{pmatrix}}\cdot {\begin{pmatrix}1\1円\0円\0円\\\end{pmatrix}}={\begin{pmatrix}0\1円\1円\\\end{pmatrix}}}

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

• Hash functions
• Computer programming stubs

• All stub articles