somewhere i read the HashMap.get(object) is faster than TreeMap.get(object). but my question is why he is faster even both of will work on hashing function while retrieving object.
Asked
Active
Viewed 830 times
2
Bhatu Jayesh
- 77
- 10
-
3`TreeMap` doesn't use hashing. – Kayaman Dec 19 '17 at 09:38
-
1Maybe look at: https://stackoverflow.com/questions/7057430/treemap-or-hashmap-faster – Pwnstar Dec 19 '17 at 09:51
2 Answers
8
TreeMap is a binary search tree implementation of the Map interface. Therefore any lookup operation requires O(logN) time.
On the other hand, HashMap uses the hashCode() of the key to locate the bin that contains the key in constant time. Since each bin has an expected number of entries bound by a small constant, lookup requires O(1) time, which is faster than O(logN).
Eran
- 387,369
- 54
- 702
- 768
2
As simple as, HashMap put / get method uses the hashCode() and equals() method, whereas TreeMap use the some comparison mechanism using Comparable or Comparator.
One more point,
HashMap is more time-efficient. A TreeMap is more space-efficient.
Arvind Katte
- 995
- 2
- 10
- 20