This week's book giveaway is in the OO, Patterns, UML and Refactoring forum. We're giving away four copies of Refactoring for Software Design Smells: Managing Technical Debt and have Girish Suryanarayana, Ganesh Samarthyam & Tushar Sharma on-line! See this thread for details.
even we can use a Custom Object[key,value fields] or two dimensional array to key|value fair[instead of Map]. so why we go for Map?. because of hashing function. what is the efficient than other data structure.
Its like why we use ArrayList when we can use array for the same thing, but as per my knowledge the data structure has some important things for me.
1. List/Map size increased as you go on inserting new element, so when you don't have a fixed number of element we can use list/map class.
2. You have better control on elements, like get first, get last element, etc methods.
3. Generics, you can't declare generic array but you can have generic list, maps.
If you use a List you need to loop through the entire List until you get a match (linear searching). With a HashMap, the access is nearly instantaneous - using the hash code a very small subset of entries (called buckets, ideally only one element) is retrieved and that is searched like a List. This is in the end a lot faster than a List.
With TreeMap the access is a bit slower but still faster than linear. The elements are spread out like a binary tree. Each node (also non-leaf nodes) has an element and at most two children. Lookup is determined by starting at the root using this algorithm:
- if the element's match then stop at that element
- if the element is larger than check the left sub tree
- if the element is smaller than check the right sub tree
All in all, for a simple lookup a List is O(n) (linear), a HashMap is O(1) (constant) and a TreeMap is O(log(n)) (logarithmic).