[the8472]

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

The n in operation time on data structures usually refers to the number of members in the data structure. String length would be a different variable.

For example worst case for finding a string member in a linked list would be O(n * k) where n is the elements in the linked list and k is the string length. I.e. the worst case here assumes lots of members with shared prefixes.

So the O(1) in hash tables actually is O(1 * k).

This distinction often is important because the length of strings and the number of members are independent variables.

And for many use-cases (e.g. member names in classes or text-protocol keywords) k is essentially fixed, e.g. a maximum member name length of 255 characters or a similar limitation. And for big O notation that means O(1 * 1), since it's a constant.