CODEWITHSUNDEEP
c++data-structuresindexinghashmapelement
user1255454
user1255454

Reputation: 699

Hashmap suited for X number of elements?

For what number range of elements is a hash map suited for?

I understand that everything is constant time and that the only problem caused will be a large memory consumption, but I would be interested to know to what extent is too much?

Upvotes: 1

Views: 70

Answers (1)

Bernhard Barker
Bernhard Barker

Reputation: 55589

Any number range.

The only problem is most certainly not memory consumption. Memory consumption is generally linear in the number of elements, which isn't particularly bad.

If there are plenty of hash collisions (elements hashing to the same value), this would be a major problem, as you'd have to search all elements with that hash value to find the correct one. A popular method of storing elements that have the same hash value (called 'separate chaining') is using a linked-list, and searching in a linked-list is slow.

Whether or not a hash table would perform well depends on:

  • The distribution of the hashed elements (which would affect the number of hash collisions), which is dependent on the actual elements and the hash function
  • The load factor of the hash table (how many elements are in the hash table in relation to its size). If this is too high, even with a decent distribution, there will be plenty of hash collisions.

Upvotes: 1

Related Questions