> computing the hash of a string key is typically an O(n) operation.

When strings are immutable, the hash values can be cached so the computation is amortized (this is how it works in Java)