3 ms·
Why does a dictionary require O(n) lookup for strings. Is there some CS knowledge I’m missing here?
by sashank_1509 4y ago
Why does a dictionary require O(n) lookup for strings. Is there some CS knowledge I’m missing here?
- behdad 4y agoAssuming that the dictionary is arbitrary as well, just comparing the string to the strings in the dictionary (or hashing it) it takes O(n), regardless of the data-structure you use.
- fenomas 4y agoIs that relevant to real-world use? You mention Python in TFA - I'm no expert but I believe it does string interning, and caches the results of string hashes, which would suggest real-world performance should be constant over time in both cases.
- seanhunter 4y agon 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.