O(nm) insertion in hash table under "an application of hash table" section?

#1

Page# 207 in ebook under an application of hash table" section, it says

“there are n insertions into the hash table”
"the insertions add a time complexity of O(nm), yielding O(nm logm) time complexity in total.

Shouldn’t insertions be only O(n) as it’s O(1) per insertion on average?

Page 203 has code:
hash_code ^= hash<string()(name)

Can someone point to how one could figure out what this means?
If it means operator () on the “template< class Key > struct hash” then shouldn’t it be:

hash(name) as the argument to operator () is a string. Why is empty brackets () correct?

0 Likes

#2

Hi @googlejob,

For the insertions, there are n strings, and we “copy” those strings into the hash table. Copy a string of length m is not O(1) operation.

You might want to take a look of http://en.cppreference.com/w/cpp/utility/hash for more about what std::hash can do. It is a very convenient function that can help us produce hashcode without our implementations.

0 Likes

#3

Is the O(nm) runtime still applicable for java code? We’re just passing in a reference to the hash table right?

0 Likes

#4

Hi @fondant,

This is an interesting question for sure, and I am also wondering how the memory model in Java works in this situation.

Do you want to check this and let us know?

0 Likes