4 ms·
I have a question about time complexity for hash maps. What is considered the complexity of inserting an initially unknown number n of items into the map? My l
by dzdt 4y ago
I have a question about time complexity for hash maps. What is considered the complexity of inserting an initially unknown number n of items into the map?
My longstanding belief was that this complexity should be O(n log n) because a particular hash size will be chosen and then have to be repeatedly grown as the density of the map's population overwhelms the current size of the structure. An exponentially increasing size gives growth steps every log n items, and the growth step will require O(n) time.
Now everyone seems to believe that hash maps insertion is O(1) time with the only exception being degenerate coincidence between hash function and hashed data that puts large number of items into the same bucket.
Do current hash maps avoid O(n) complexity when growth is required? How?
- throw827474737 4y agoSizing the hash map appropriately is one of the tuning knobs to usually achieve the O(1) desired complexity, in theory you are right, but tuning away from that in practice this does not or rare enough happens is the goal why you actually chose a hash map for hopefully close to O(1)?
- joaquintides 4y agoComplexity is still O(n) because sizes grow exponentially, so the cost of amortizing rehashes over the number of inserted elements is a constant. Here's a theoretical analysis of this: https://www.cs.cornell.edu/courses/cs3110/2011sp/Lectures/lec20-amortized/amortized.htm https://www.cs.cornell.edu/courses/cs3110/2011sp/Lectures/le...