n is the number of characters in the string in this case. If you had a function that could turn a string into a hash key in O(1) then you could look that key up

n is the number of characters in the string in this case. If you had a function that could turn a string into a hash key in O(1) then you could look that key up in a hash in O(1). However, you need to go through the string one character at a time[1] so you can’t. This is exactly why tries/prefix trees exist (although they aren’t only relevant for strings). [1] This seems to me to be a practical limitation rather than theoretical given strings and numbers are really equivalent - it’s just that the space is mindbogglingly huge so if you wanted to do a general purpose O(1) string to number conversion it would require uncountably infinite space.