I have a question about hashmaps. If you have this hashmap with m slots, and need to map n items to it, and n > m. There will be collisions for sure. But assuming there is simple uniform hashing assumption, this means that the maximum amount of collisions in any spot is the load factor right? The load factor is n/m. But the load factor is probably going to be a decimal, does this mean its a ceiling of the n/m? So if n=6 and m=5, then load factor is 1.2, and the ceiling is 2, so that means the maximum collisions in one spot is 2. Is this right?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
No, the maximum number of collisions is the number of hash elements to be put into the hash.
From the wikipedia link on Simple Uniform Hashing Assumption:
The key word is "probability" - it is possible for all of them to hash to the same spot, and thus the maximum collisions is the size. It is also possible for them to hash evenly, in which case it would be the ceiling of the load factor.
Particularlly relevant to this is:
Continuing to read the article, one will note phrases such as "on average" used regularly - this is about the probability of an uniform hash - not the guarantee of such.
An example of such a hash algorithm would be
However, if one was to hash into this size 5 hash the numbers: