What is HashMap and Map? |HashMap in java

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.

No comments:

Post a Comment

Please Provide your feedback here