TY - GEN

T1 - Exponential hashing in finite fields

AU - Luo, Wenbin

AU - Heileman, Gregory

PY - 2008

Y1 - 2008

N2 - Hash functions are widely used in computing. Hashing applications are abundant. For example, in computer security, a hash function is used to produce a "fingerprint" of a file, password, message, or other block of data for integrity verification and message authentication etc. Computer compilers use hash tables, known as symbol tables, to keep track of declared variables in source codes. Hash functions are also used very commonly in on-line spelling checkers and in programs that play games. Design of efficient hash functions is crucial for lots of real world applications. Many existing open addressing hash functions, for example, the widely used double hashing, require that the table size m be prime, in order to produce full length probe sequences. In this paper, a new and efficient technique, called exponential hashing in finite fields, is proposed to construct a new hash function with table size m = pn, where p is prime and n ≥ 1. It is clear that the table size m = pn includes prime m as a special case when n = 1. We show that the proposed new hash function has the ability to spread table elements more randomly than the widely used double hashing, and at the same time produces full length probe sequences on all table elements. We demonstrate experimentally that the new hash function performs significantly better than double hashing for clustered data. Also, several properties of the proposed new hash function are presented along with experimental results.

AB - Hash functions are widely used in computing. Hashing applications are abundant. For example, in computer security, a hash function is used to produce a "fingerprint" of a file, password, message, or other block of data for integrity verification and message authentication etc. Computer compilers use hash tables, known as symbol tables, to keep track of declared variables in source codes. Hash functions are also used very commonly in on-line spelling checkers and in programs that play games. Design of efficient hash functions is crucial for lots of real world applications. Many existing open addressing hash functions, for example, the widely used double hashing, require that the table size m be prime, in order to produce full length probe sequences. In this paper, a new and efficient technique, called exponential hashing in finite fields, is proposed to construct a new hash function with table size m = pn, where p is prime and n ≥ 1. It is clear that the table size m = pn includes prime m as a special case when n = 1. We show that the proposed new hash function has the ability to spread table elements more randomly than the widely used double hashing, and at the same time produces full length probe sequences on all table elements. We demonstrate experimentally that the new hash function performs significantly better than double hashing for clustered data. Also, several properties of the proposed new hash function are presented along with experimental results.

UR - http://www.scopus.com/inward/record.url?scp=63149166639&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=63149166639&partnerID=8YFLogxK

U2 - 10.1109/EUC.2008.55

DO - 10.1109/EUC.2008.55

M3 - Conference contribution

AN - SCOPUS:63149166639

SN - 9780769534923

T3 - Proceedings of The 5th International Conference on Embedded and Ubiquitous Computing, EUC 2008

SP - 333

EP - 338

BT - Proceedings of The 5th International Conference on Embedded and Ubiquitous Computing, EUC 2008

T2 - 5th International Conference on Embedded and Ubiquitous Computing, EUC 2008

Y2 - 17 December 2008 through 20 December 2008

ER -