Computer Science – Data Structures and Algorithms
Scientific paper
2004-07-09
Computer Science
Data Structures and Algorithms
Submitted to SODA05
Scientific paper
The study of hashing is closely related to the analysis of balls and bins. It is well-known that instead of using a single hash function if we randomly hash a ball into two bins and place it in the smaller of the two, then this dramatically lowers the maximum load on bins. This leads to the concept of two-way hashing where the largest bucket contains $O(\log\log n)$ balls with high probability. The hash look up will now search in both the buckets an item hashes to. Since an item may be placed in one of two buckets, we could potentially move an item after it has been initially placed to reduce maximum load. with a maximum load of We show that by performing moves during inserts, a maximum load of 2 can be maintained on-line, with high probability, while supporting hash update operations. In fact, with $n$ buckets, even if the space for two items are pre-allocated per bucket, as may be desirable in hardware implementations, more than $n$ items can be stored giving a high memory utilization. We also analyze the trade-off between the number of moves performed during inserts and the maximum load on a bucket. By performing at most $h$ moves, we can maintain a maximum load of $O(\frac{\log \log n}{h \log(\log\log n/h)})$. So, even by performing one move, we achieve a better bound than by performing no moves at all.
No associations
LandOfFree
Efficient Hashing with Lookups in two Memory Accesses 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 Efficient Hashing with Lookups in two Memory Accesses, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Hashing with Lookups in two Memory Accesses will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-164144