That should about do it! Let's try it out.
Complexity for Final Solution
The hash map data structure grows linearly to hold n
elements for O(n)
linear space complexity. Assuming a good hash function (one that minimizes collisions!) we usually have O(1)
constant get/set complexity. Otherwise, in the worst case where all n
entries hash to the same bucket we traverse through for an unfortunate O(n)
linear get/set complexity.