let us say the length of the string is L. When we are inserting this into a hash table (let us say we are using separate chaining), first of all the hash for the string is computed. How is the insertion into the hash table O(1), should'nt it be O(L) as time for computing the hash of a string grows with string size?
after the hash is computed, then the string is stored in the hash table. Won't this copying also take O(L)?
when the string is looked up in the hash table, how can it be a constant operation? Because again, the hash for the string is computed, and then at the computed bucket the string is compared which should also be O(L) in the worst case.
Please, can someone explain this? What am I missing?
I tried asking ChatGPT, and also looked for solutions on the websites, but they were conflicting. ChatGPT says it will be O(L), but some websites say it will be O(1).
The C++ standard has this to say:
[container.requirements.general]/2 All of the complexity requirements in this Clause are stated solely in terms of the number of operations on the contained objects. [Example: The copy constructor of type
vector<vector<int>>has linear complexity, even though the complexity of copying each containedvector<int>is itself linear. —end example]
Similarly, hash(string of length L) is treated as one operation on the contained object for purposes of discussing the complexity of operations on hash-based containers, even though actually computing the hash may take the amount of wall time proportional to L.