O(n) in the size of the string not the hash map.

Also, if the key space is known before hand, it is possible to build a perfect minimal hash table with 1.3n total keys (n is the size of the keyspace)