Think of operator modulus % as a way to distribute uniformly a set of numbers through reducingthem over a smaller range. The set of numbers are, of corse, the hashcodes of input keys. The small range is the capacity of the table.
This is a useful technique when you want to assign an index in a small table to store a high number.
The inverse operation sounds quite weird (and useless): Taking in account that the hash codes are high numbers and n is small, n % hash would return always n, so it has no interest at all.
Java choses indexes through hash & (length-1), indeed, which is not aritmetically equivalent to hash % length, but it is an alternative -and cheaper than modulus- formula to reduce and distribute (credits to @Zabuza).
manpreet![Tuteehub forum best answer]()
Best Answer
2 years ago
In many books, syllabus, tutorials I've seen that a good option to find a proper cell of an item is to calculate a number of the cell:
item.hash()%(n-1) = # of the bucket.But why is this certain expression is mentioned?
How does the inverse one
(n-1)%item.hash() = # of the bucketdiffers from it?P.S. I know that Java HashMap uses
(n - 1) & hash, I would like only to catch the difference in sparsing key between these two approaches.