CODEWITHSUNDEEP
javahash
user2372074
user2372074

Reputation: 861

space complexity using hashmap. Should take the key size into account?

In java, we commonly think the space complexity of using hashtable is O(n). Should we also take key size into account, what if the key is very large?

Upvotes: 1

Views: 300

Answers (1)

Eran
Eran

Reputation: 394026

That depends on the relation between the size of the key and the number of elements you store in the hash table (which is n). If the size of the key is a function of n, you'll have to consider the size of the key when computing the space complexity. The same is true for the value of the hash table.

I think, however, it is safe to assume that in most cases the size of the key (no matter how large) is a constant and not a function of n.

Upvotes: 4

Related Questions