A map will traverse a tree to find a match. ie log complexity A hash map will create a hash of the string, and use that hash to index an array, giving constant lookup. note: collision detection is required because a hash of a string can produce the same index as the hash of another string. Therefore complexity is added to manage collisions.
- log traverse complexity
- string comparison at each node
- hash creation (might be linear complexity to string size depending on algorithm to create hash)
- constant lookup with hash
- with consideration to collision. which might add linear complexity to number of collisions for the same hash.