Probabilistic behavior of hash tables

Details Probabilistic behavior of hash tables Probabilistic behavior of hash tables

2003-03-21

arxiv.org/abs/cs/0303022v1

Computer Science

Data Structures and Algorithms

Scientific paper

We extend a result of Goldreich and Ron about estimating the collision probability of a hash function. Their estimate has a polynomial tail. We prove that when the load factor is greater than a certain constant, the estimator has a gaussian tail. As an application we find an estimate of an upper bound for the average search time in hashing with chaining, for a particular user (we allow the overall key distribution to be different from the key distribution of a particular user). The estimator has a gaussian tail.

Affiliated with

Also associated with

No associations

Rating

Probabilistic behavior of hash tables 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 Probabilistic behavior of hash tables, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Probabilistic behavior of hash tables will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-153289