Issue
It’s usually said that inserting and finding a string in a hash table is O(1). But how is hash key of a string made? Why it’s not considered O(L), length of string?
It is clear to me that why for integers it is O(1), but not for strings.
I do understand why in general, inserting into a hash table is O(1), but I am confused about the step before inserting the hash into table: making the hash value.
Also is there any difference between how hash keys for strings are generated in java and unordered_map in C++?
Thanks.
Solution
Inserting etc. in a hashtable is O(1) in the sense that it is constant (or more precisely, bounded) in regard to the number of elements in the table.
The "O(1)" in this context makes no claim about how fast you can compute your hashes. If the effort for this grows in some way, that is the way it is. However, I find it unlikely that the complexity of a decent (i.e. "fit for this application") hash function will ever be worse than linear in the "size" (i.e. the length in our string-example) of the object being hashed.
Answered By – Baum mit Augen
Answer Checked By – Terry (BugsFixing Volunteer)