Tell me more ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 1 down vote favorite
1

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?

share|improve this question

1 Answer

up vote 4 down vote accepted

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:

Moreover, each item to be hashed has an equal probability of being placed into a slot, regardless of the other elements already placed.

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:

Collision chain length Under the assumption of uniform hashing, the load factor A and the average chain length of a hash table of size m with n elements will be A = n/m

Where n is the number of elements and m is the size of the hash. Key phrase again is the average chain length - not the maximum chain length.

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 mod hashSize on integers. If the hash size was 5 hash(x) = x % 5 would be a hash that fits this requirement - that each value hashed has an equal probability of being placed into a given slot.

However, if one was to hash into this size 5 hash the numbers: 5, 10, 15, 20, 25, 30 one would then have everything hash to the same location.

share|improve this answer
So the average length of the linked lists is the ceiling of the load factor? – omega Mar 6 at 3:05
@omega no ceiling call is necessary. The average chain length in the example is 1.2. – MichaelT Mar 6 at 3:06
So if you have a set of x numbers, call it D, and are storing each number of D in a hash map with m slots (using the mod function, which makes it SUHA), how do you get the probability of a number already being in the hashmap, when you are storing it? – omega Mar 6 at 3:14
My math skills aren't quite up to that at this hour and a bit more than I can fit in comments reasonably. It would likely be a good question to ask on math.SE. – MichaelT Mar 6 at 3:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.