What is the difference between a HashMap and a TreeMap?
TreeMap
is an example of a SortedMap
, which means that the order of the keys can be sorted, and when iterating over the keys, you can expect that they will be in order.
HashMap
on the other hand, makes no such guarantee. Therefore, when iterating over the keys of a HashMap
, you can't be sure what order they will be in.
HashMap
will be more efficient in general, so use it whenever you don't care about the order of the keys.
Difference between HashMap, LinkedHashMap and TreeMap
All three classes implement the Map
interface and offer mostly the same functionality. The most important difference is the order in which iteration through the entries will happen:
HashMap
makes absolutely no guarantees about the iteration order. It can (and will) even change completely when new elements are added.TreeMap
will iterate according to the "natural ordering" of the keys according to theircompareTo()
method (or an externally suppliedComparator
). Additionally, it implements theSortedMap
interface, which contains methods that depend on this sort order.LinkedHashMap
will iterate in the order in which the entries were put into the map
"Hashtable" is the generic name for hash-based maps. In the context of the Java API,Hashtable
is an obsolete class from the days of Java 1.1 before the collections framework existed. It should not be used anymore, because its API is cluttered with obsolete methods that duplicate functionality, and its methods are synchronized (which can decrease performance and is generally useless). Use ConcurrentHashMap instead of Hashtable.
TreeMap or HashMap?
Hashtables (usually) perform search operations (look up) bounded within the complexity of O(n)<=T(n)<=O(1)
, with an average case complexity of O(1 + n/k)
; however, binary search trees, (BST's), perform search operations (lookup) bounded within the complexity of O(n)<=T(n)<=O(log_2(n))
, with an average case complexity of O(log_2(n))
. The implementation for each (and every) data structure should be known (by you), to understand the advantages, drawbacks, time complexity of operations, and code complexity.
For example, the number of entries in a hashtable often have some fixed number of entries (some part of which may not be filled at all) with lists of collisions. Trees, on the other hand, usually have two pointers (references) per node, but this can be more if the implementation allows more than two child nodes per node, and this allows the tree to grow as nodes are added, but may not allow duplicates. (The default implementation of a Java TreeMap does not allow for duplicates)
There are special cases to consider as well, for example, what if the number of elements in a particular data structure increases without bound or approaches the limit of an underlying part of the data structure? What about amortized operations that perform some rebalancing or cleanup operation?
For example, in a hashtable, when the number of elements in the table become sufficiently large, and arbitrary number of collisions can occur. On the other hand, trees usually require come re-balancing procedure after an insertion (or deletion).
So, if you have something like a cache (Ex. the number of elements in bounded, or size is known) then a hashtable is probably your best bet; however, if you have something more like a dictionary (Ex. populated once and looked up many times) then I'd use a tree.
This is only in the general case, however, (no information was given). You have to understand process that happen how they happen to make the right choice in deciding which data structure to use.
When I need a multi-map (ranged lookup) or sorted flattening of a collection, then it can't be a hashtable.
Difference between Tree and Hash(Sets-Maps) in Java
TreeMaps and TreeSets are similar to HashMaps and HashSets in almost every aspect except that the Tree versions keep the data in a sorted order (unlike the Hash versions in which the order is unspecified).
With TreeMap and TreeSet you can choose to use the 'natural' order of the content (assuming the content implements the Comparable interface), or alternatively you can supply your own Comparator to do the sorting for you.
One difference that catches people by suprise is that you can store null
in HashMap and HashSet, but not (necessarily) in TreeSet or as a key in TreeMap.
What is the difference between the HashMap and Map objects in Java?
There is no difference between the objects; you have a HashMap<String, Object>
in both cases. There is a difference in the interface you have to the object. In the first case, the interface is HashMap<String, Object>
, whereas in the second it's Map<String, Object>
. But the underlying object is the same.
The advantage to using Map<String, Object>
is that you can change the underlying object to be a different kind of map without breaking your contract with any code that's using it. If you declare it as HashMap<String, Object>
, you have to change your contract if you want to change the underlying implementation.
Example: Let's say I write this class:
class Foo {
private HashMap<String, Object> things;
private HashMap<String, Object> moreThings;
protected HashMap<String, Object> getThings() {
return this.things;
}
protected HashMap<String, Object> getMoreThings() {
return this.moreThings;
}
public Foo() {
this.things = new HashMap<String, Object>();
this.moreThings = new HashMap<String, Object>();
}
// ...more...
}
The class has a couple of internal maps of string->object which it shares (via accessor methods) with subclasses. Let's say I write it with HashMap
s to start with because I think that's the appropriate structure to use when writing the class.
Later, Mary writes code subclassing it. She has something she needs to do with both things
and moreThings
, so naturally she puts that in a common method, and she uses the same type I used on getThings
/getMoreThings
when defining her method:
class SpecialFoo extends Foo {
private void doSomething(HashMap<String, Object> t) {
// ...
}
public void whatever() {
this.doSomething(this.getThings());
this.doSomething(this.getMoreThings());
}
// ...more...
}
Later, I decide that actually, it's better if I use TreeMap
instead of HashMap
in Foo
. I update Foo
, changing HashMap
to TreeMap
. Now, SpecialFoo
doesn't compile anymore, because I've broken the contract: Foo
used to say it provided HashMap
s, but now it's providing TreeMaps
instead. So we have to fix SpecialFoo
now (and this kind of thing can ripple through a codebase).
Unless I had a really good reason for sharing that my implementation was using a HashMap
(and that does happen), what I should have done was declare getThings
and getMoreThings
as just returning Map<String, Object>
without being any more specific than that. In fact, barring a good reason to do something else, even within Foo
I should probably declare things
and moreThings
as Map
, not HashMap
/TreeMap
:
class Foo {
private Map<String, Object> things; // <== Changed
private Map<String, Object> moreThings; // <== Changed
protected Map<String, Object> getThings() { // <== Changed
return this.things;
}
protected Map<String, Object> getMoreThings() { // <== Changed
return this.moreThings;
}
public Foo() {
this.things = new HashMap<String, Object>();
this.moreThings = new HashMap<String, Object>();
}
// ...more...
}
Note how I'm now using Map<String, Object>
everywhere I can, only being specific when I create the actual objects.
If I had done that, then Mary would have done this:
class SpecialFoo extends Foo {
private void doSomething(Map<String, Object> t) { // <== Changed
// ...
}
public void whatever() {
this.doSomething(this.getThings());
this.doSomething(this.getMoreThings());
}
}
...and changing Foo
wouldn't have made SpecialFoo
stop compiling.
Interfaces (and base classes) let us reveal only as much as is necessary, keeping our flexibility under the covers to make changes as appropriate. In general, we want to have our references be as basic as possible. If we don't need to know it's a HashMap
, just call it a Map
.
This isn't a blind rule, but in general, coding to the most general interface is going to be less brittle than coding to something more specific. If I'd remembered that, I wouldn't have created a Foo
that set Mary up for failure with SpecialFoo
. If Mary had remembered that, then even though I messed up Foo
, she would have declared her private method with Map
instead of HashMap
and my changing Foo
's contract wouldn't have impacted her code.
Sometimes you can't do that, sometimes you have to be specific. But unless you have a reason to be, err toward the least-specific interface.
Performance of TreeMap, HashMap and LinkedHashMap?
Use a HashMap
unless you have some need for ordering. HashMap
is faster.
That said, you can make it easy to switch by using the generic interface as your declaration:
Map<String,String> M = new HashMap<String,String>();
...use M lots of places...
Then all you have to do is switch one place and your code uses the new map type.
Edit:
A simple timing test:
import java.util.*;
class TimingTest {
public static void main(String[] args) {
Map<String,String> M = new HashMap<String,String>();
long start = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
M.put(Integer.toString(i), "foo");
}
long end = System.currentTimeMillis();
System.out.println(end - start);
}
}
When to use TreeMap instead of HashMap
Of course there exist such use cases. In all read-heavy settings you have the advantage of sorting only once, during insertion. The majority of use cases are read-heavy, contrary to the assumptions of your question.
An even greater advantage is offered by the TreeMap
when you need to extract submaps with an upper or lower bound on the key, find the minimum or maximum keys, or find keys closest to a given key. The interface NavigableMap
is dedicated to these operations.
Related Topics
How to Remove Element from Arraylist by Checking Its Value
Why Does Java Switch on Contiguous Ints Appear to Run Faster with Added Cases
Jtable Getselectedrow Does Not Return the Selected Row Index
Which Loop Has Better Performance? Why
How to Configure Log4J to Log Different Log Levels to Different Files for the Same Logger
How to Convert .Pfx File to Keystore with Private Key
How to Properly Do a Background Thread When Using Spring Data and Hibernate
Capture Generated Dynamic Content at Server Side
How to Find the Source Code for Java's Square Root Function
When to Use an Assertion and When to Use an Exception
How to Use Concurrentlinkedqueue
Why Are Java 8 Lambdas Invoked Using Invokedynamic
In Which Language Are the Java Compiler and Jvm Written
Locally Declared Variables Can Not Be Inspected
Fastest Way to Iterate an Array in Java: Loop Variable VS Enhanced for Statement
Why Did Servlet.Service() for Servlet Jsp Throw This Exception