principleMinor
What is the advantage of seperate chaining over open addressing?
Viewed 0 times
seperatetheaddressingwhatopenchainingadvantageover
Problem
Hash tables resolve collisions through two mechanisms,
Though the first method uses lists (or other fancier data structure) in hash table to maintain more than one entry having same hash values, the other uses complex ways of skipping n elements on collsion.
Since, while searching, both mechanisms requires looking up for more entries on collision and Seperate chaining may require lesser number of searches to find the match.
What kind of advantages does it have over separate chaining?
- separate chaining or open hashing and
- open addressing or closed hashing.
Though the first method uses lists (or other fancier data structure) in hash table to maintain more than one entry having same hash values, the other uses complex ways of skipping n elements on collsion.
Since, while searching, both mechanisms requires looking up for more entries on collision and Seperate chaining may require lesser number of searches to find the match.
What kind of advantages does it have over separate chaining?
Solution
Suppose that you have a very large number of sufficiently uniform elements, $n$, that you want to hash. We want to minimize lookup time, obviously.
If we use separate chaining with $m$ linked lists, our lookup time will be, on average, $O(n/m)$ since we have $n$ elements and $m$ buckets. The actual lookup time depends on whether our input set is sufficiently uniform or not, but for the sake of simplicity we can assume that it is. What are the downsides of this? Linked lists and most other data structures that we would use to do this make heavy use of pointers. A single query takes $O(n)$ pointer dereferences.
Now consider two typical methods of open addressing: linear probing and quadratic probing. Linear probing traverses the space allot for open addressing and places the element that it is hashing at the first available memory location (at the $i^\text{th}$ step, we look at index $i$ to see if it is free). Quadratic probing traverses by incrementing the index by $i^2$ on each step. This can lead to immense speed-up due to its cache-friendliness (as mentioned in the first comment, this is called spatial locality -- I'd suggest reading this if you're unfamiliar).
If we use separate chaining with $m$ linked lists, our lookup time will be, on average, $O(n/m)$ since we have $n$ elements and $m$ buckets. The actual lookup time depends on whether our input set is sufficiently uniform or not, but for the sake of simplicity we can assume that it is. What are the downsides of this? Linked lists and most other data structures that we would use to do this make heavy use of pointers. A single query takes $O(n)$ pointer dereferences.
Now consider two typical methods of open addressing: linear probing and quadratic probing. Linear probing traverses the space allot for open addressing and places the element that it is hashing at the first available memory location (at the $i^\text{th}$ step, we look at index $i$ to see if it is free). Quadratic probing traverses by incrementing the index by $i^2$ on each step. This can lead to immense speed-up due to its cache-friendliness (as mentioned in the first comment, this is called spatial locality -- I'd suggest reading this if you're unfamiliar).
Context
StackExchange Computer Science Q#43319, answer score: 4
Revisions (0)
No revisions yet.