Menu
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.
478
In hashing, all the above operations can be performed in O(1) i.e. constant time. It is important to understand that the worst case time complexity for hashing remains O(n) but the average case time complexity is O(1).
Insertion and Deletion The hash key is calculated in O(1) time complexity as always, and the required location is accessed in O(1). Insertion: In the best case, the key indicates a vacant location and the element is directly inserted into the hash table. So, overall complexity is O(1).
Each resizing operation takes O(n) time where n is the size of the hash table being resized. Therefore the O(1) performance of the hash table operations no longer holds in the case of add : its worst-case performance is O(n).
Furthermore, the average complexity to search, insert, and delete data in a hash table is O(1) — a constant time. It means that, on average, a single hash table lookup is sufficient to find the desired memory bucket regardless of the aimed operation.
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.
189
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
