Map hashmap treemap java

Learning Java: How to Use Maps HashMap vs. TreeMap(SortedMap) vs. LinkedHashMap vs. Hashtable

The structure of key-value pair map is important in programming. Java provides a basic interface Map and several classes such as HashMap, TreeMap and LinkedHashMap that implement the interface. I will mainly compare these classes, HashMap, LinkedHashMap and TreeMap.

Inheritance Review

The Map interface has many implementing classes. And some of these classes also have sub-classes.

Interface Map All Known Subinterfaces: Bindings, ConcurrentMap, ConcurrentNavigableMap, LogicalMessageContext, MessageContext, NavigableMap, SOAPMessageContext, SortedMap All Known Implementing Classes: AbstractMap, Attributes, AuthProvider, ConcurrentHashMap, ConcurrentSkipListMap, EnumMap, HashMap, Hashtable, IdentityHashMap, LinkedHashMap, PrinterStateReasons, Properties, Provider, RenderingHints, SimpleBindings, TabularDataSupport, TreeMap, UIDefaults, WeakHashMap 

Class HashMap extends AbstractMap implements Map, Cloneable, Serializable 

class TreeMap extends AbstractMap implements NavigableMap, Cloneable, Serializable 

class AbstractMap extends Object implements Map

interface SortedMap extends Map

class Hashtable extends Dictionary implements Map, Cloneable, Serializable 

class LinkedHashMap extends HashMap implements Map

Understanding Classes

An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value. The Map interface provides three collection views, which allow a map’s contents to be viewed as a set of keys, collection of values, or set of key-value mappings.

Basically, these classes that implement Map are like:

• HashMap is implemented based on a hash table.
• LinkedHashMap is like a HashMap, but in insertion order or in least-recently-used (LRU) order.
• TreeMap is implemented based on a red-black tree.
• WeakHashMap is a map of weak keys that allow objects referred to by the map to be released.
• ConcurrentHashMap is a thread-safe map which does not involve synchronization locking.
• IdentityHashMap is a hash map that uses == instead of equals() to compare keys.

HashMap

Hash table based implementation of the Map interface. The HashMap class is roughly equivalent to Hashtable.

HashMap offers O(1) lookup and insertion. If you iterate through the keys, though, the ordering of the keys is essentially arbitrary. It is implemented by an array of linked lists.

• A HashMap contains values based on the key.
• It contains only unique elements.
• It may have one null key and multiple null values.
• It makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.
• It provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the “capacity” of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it’s very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.
• It is not synchronized. If multiple threads access a hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally.

LinkedHashMap

LinkedHashMap is a subclass of HashMap.

LinkedHashMap offers O(1) lookup and insertion. Keys are ordered by their insertion order. It is implemented by doubly-linked buckets.

• A LinkedHashMap contains values based on the key.
• It contains only unique elements.
• It may have one null key and multiple null values.
• It maintains insertion order or LRU order. If you want to use LRU order, you need to change one parameter.
• Different from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). Note that insertion order is not affected if a key is re-inserted into the map.
• Same with HashMap, it is not synchronized, either.

TreeMap

TreeMap is implemented NavigableMap whose super interface are SortedMap and Map.

TreeMap offers O(log N) lookup and insertion. Keys are ordered, so if you need to iterate through the keys in sorted order, you can. This means that keys must implement the Comparable interface.

• A TreeMap contains values based on the key. It implements the NavigableMap interface and extends AbstractMap class.
• It contains only unique elements.
• It cannot have null key but can have multiple null values.
• It is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
• It is not synchronized.

Hashtable

The basic Hashtable is very similar to the HashMap.

• A Hashtable is an array of list. Each list is known as a bucket. The position of bucket is identified by calling the hashcode() method. A Hashtable contains values based on the key.
• It contains only unique elements.
• Any non-null object can be used as a key or as a value.

According to Java API, Hashtable is synchronized, unlike the new collection implementations. If a thread-safe implementation is not needed, it is recommended to use HashMap in place of Hashtable. If a thread-safe highly-concurrent implementation is desired, then it is recommended to use ConcurrentHashMap in place of Hashtable.

Comparison

Property	HashMap	LinkedHashMap	TreeMap
Time complexity	O(1)	O(1)	O(log N)
Iteration order	random	in insertion order or LRU order	in sorted order by key
Null keys	allowed	allowed	not allowed
Synchronization	none	none	none
Data structure	list of buckets	doubly linked list of buckets	red-black implementation of binary tree
Requirements for keys	equals() and hashCode()	equals() and hashCode()	Comparable needs to be implemented

A simple testing example for insertion:

import java.util.HashMap; import java.util.LinkedHashMap; import java.util.TreeMap; public class SimpleTest  private int[] integers =  1, -2, 0, 3, -4 >; public void testHashMap()  HashMapInteger, String> map = new HashMapInteger, String>(); for (int i : integers)  map.put(i, Integer.toString(i)); > System.out.print("HashMap oder: "); System.out.println(map); > public void testLinkedHashMap()  LinkedHashMapInteger, String> map = new LinkedHashMapInteger, String>(0, 0.75f, true); for (int i : integers)  map.put(i, Integer.toString(i)); > System.out.print("LinkedHashMap oder: "); System.out.println(map); map.get(integers[2]); System.out.print("LinkedHashMap oder after accessing: "); System.out.println(map); > public void testTreeMap()  TreeMapInteger, String> map = new TreeMapInteger, String>(); for (int i : integers)  map.put(i, Integer.toString(i)); > System.out.print("TreeMap oder: "); System.out.println(map); > public static void main(String. strings)  SimpleTest st = new SimpleTest(); st.testHashMap(); st.testHashMap(); st.testLinkedHashMap(); st.testTreeMap(); > > /* Output: HashMap oder: HashMap oder: LinkedHashMap oder: LinkedHashMap oder after accessing: TreeMap oder: */ 

Summary

In a conclusion, you could use HashMap if there are no special requirements, because it is faster and requires less overhead. If insertion order is important, use LinkedHashMap. If the order of key is important, use TreeMap.

References

Источник

HashMap and TreeMap in Java

HashMap and TreeMap are part of collection framework. HashMapjava.util.HashMap class is a Hashing based implementation. In HashMap, we have a key and a value pair.

HashMap hmap = new HashMap();

Let us consider below example where we have to count occurrences of each integer in given array of integers.

Input: arr[] = ; Output: Frequency of 10 is 3 Frequency of 3 is 2 Frequency of 5 is 2

Java

Frequency of 34 is 1 Frequency of 3 is 1 Frequency of 5 is 2 Frequency of 10 is 3

• HashMap does not maintain any order neither based on key nor on basis of value, If we want the keys to be maintained in a sorted order, we need to use TreeMap.
• Complexity: get/put/containsKey() operations are O(1) in average case but we can’t guarantee that since it all depends on how much time does it take to compute the hash.

Application: HashMap is basically an implementation of hashing. So wherever we need hashing with key value pairs, we can use HashMap. For example, in Web Applications username is stored as a key and user data is stored as a value in the HashMap, for faster retrieval of user data corresponding to a username.

TreeMapTreeMap can be a bit handy when we only need to store unique elements in a sorted order. Java.util.TreeMap uses a red-black tree in the background which makes sure that there are no duplicates; additionally it also maintains the elements in a sorted order.

TreeMap hmap = new TreeMap();

Below is TreeMap based implementation of same problem. This solution has more time complexity O(nLogn) compared to previous one which has O(n). The advantage of this method is, we get elements in sorted order.

Java

Frequency of 3 is 1 Frequency of 5 is 2 Frequency of 10 is 3 Frequency of 34 is 1

• For operations like add, remove, containsKey, time complexity is O(log n where n is number of elements present in TreeMap.
• TreeMap always keeps the elements in a sorted(increasing) order, while the elements in a HashMap have no order. TreeMap also provides some cool methods for first, last, floor and ceiling of keys.

Difference between HashMap and TreeMap:

HashMap	TreeMap
1.	It does not provide any order for elements.	It provides orders for elements.
2.	It’s speed is fast.	It’s speed is slow.
3.	It allows one key as null and also allows multiple values.	It does not allow key as null but it allows multiple null values.
4.	It consumes more memory space.	It consumes less memory space.
5.	It has only basic features.	It has advanced features.
6.	For comparing keys, equals() is used.	For comparing keys, compare or compareTo() is used.
7.	It’s complexity is O(1).	It’s complexity is O(log n).

1. HashMap implements Map interface while TreeMap implements SortedMap interface. A Sorted Map interface is a child of Map.
2. HashMap implements Hashing, while TreeMap implements Red-Black Tree(a Self Balancing Binary Search Tree). Therefore all differences between Hashing and Balanced Binary Search Tree apply here.
3. Both HashMap and TreeMap have their counterparts HashSet and TreeSet. HashSet and TreeSet implement Set interface. In HashSet and TreeSet, we have only key, no value, these are mainly used to see presence/absence in a set. For the above problem, we can’t use HashSet (or TreeSet) as we can’t store counts. An example problem where we would prefer HashSet (or TreeSet) over HashMap (or TreeMap) is to print all distinct elements in an array.

Related Articles

This article is contributed by Chirag Agrawal. If you like GeeksforGeeks and would like to contribute, you can also write an article and mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

Источник