Efficient universal hashing method

摘要

An efficient hashing technique uses $\frac{w^2+w}{2}$ operations to hash a string "w" words long rather than the w² operations of the prior art. This efficiency is achieved by squaring the sum of the key and the string to be hashed rather than forming a product of the key and the string to be hashed h(m)=((m+a)² mod p)mod 2¹.