Linear Probing with Constant Independence

Details Linear Probing with Constant Independence Linear Probing with Constant Independence

2006-12-08

arxiv.org/abs/cs/0612055v1

Computer Science

Data Structures and Algorithms

13 pages

Scientific paper

Hashing with linear probing dates back to the 1950s, and is among the most studied algorithms. In recent years it has become one of the most important hash table organizations since it uses the cache of modern computers very well. Unfortunately, previous analysis rely either on complicated and space consuming hash functions, or on the unrealistic assumption of free access to a truly random hash function. Already Carter and Wegman, in their seminal paper on universal hashing, raised the question of extending their analysis to linear probing. However, we show in this paper that linear probing using a pairwise independent family may have expected {\em logarithmic} cost per operation. On the positive side, we show that 5-wise independence is enough to ensure constant expected time per operation. This resolves the question of finding a space and time efficient hash function that provably ensures good performance for linear probing.

Affiliated with

Also associated with

No associations

Rating

Linear Probing with Constant Independence does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Linear Probing with Constant Independence, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linear Probing with Constant Independence will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-440432