Hashing via finite field

In order to produce full length probe sequences, the table size m for many existing open addressing hash functions, for example, the widely used double hashing, must be prime, i.e., m = p where p is prime. In this paper, we propose a new and efficient open addressing technique, called hashing via finite field, to construct a new class of hash functions with table size m = pn, where p is prime and n ⩾ 1. It is clear that it includes prime m as a special case when n = 1. We show that the new class of hash functions constructed via finite field produces full length probe sequences on all table elements. Also, some theoretic analysis is provided along with concrete examples.