Which java map to use

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

Источник

Overview

In this article, we’ll cover how a map works in Java and explore what’s new in Java 9.

What is a Map?

A map is a data structure that’s designed for fast lookups. Data is stored in key-value pairs with every key being unique. Each key maps to a value hence the name. These pairs are called map entries.

In the JDK, java.util.Map is an interface that includes method signatures for insertion, removal, and retrieval.

Collections Framework

The Map interface is implemented by a number of classes in the Collections Framework. Each class offers different functionality and thread safety. The most common implementation is the HashMap so we’ll be using this for most of our examples.

Map is the only collection that doesn’t extend or implement the Collection interface. It doesn’t fit the same contract since it needs to work with pairs instead of single values.

Create a Map

The keys and values of a map can be any reference type. We can’t use primitive types because of a restriction around the way generics were designed.

A HashMap allows one null key and multiple null values. It doesn’t preserve the order of the elements and doesn’t guarantee the order will remain the same over time.

Let’s create a HashMap with Integer keys and String values:

Since all maps implement the Map interface, the following methods will work for any of the map implementations illustrated above.

Add to a Map

The put() method allows us to insert entries into our map. It requires two parameters: a key and its value.

Now, let’s populate our map with id’s and names:

map.put(1, "Petyr Baelish"); map.put(2, "Sansa Stark"); map.put(3, "Jon Snow"); map.put(4, "Jamie Lannister");

Here’s what our map looks like now:

Sometimes we may want to add multiple entries in bulk or combine two maps. There’s a method that handles this called putAll(). It copies the entry references from another map in order to populate ours.

Duplicate Keys

We mentioned before that duplicate keys aren’t allowed in maps.

Let’s see what happens when we try to insert a key that already exists:

map.put(4, "Daenerys Targaryen");

The method doesn’t complain, but notice how the new value overwrote the previous one:

The put method returns the previous value if we care to use it. If there was no previous value, it returns null.

To check whether a key already exists, we use the containsKey() boolean method:

Similarly, the containsValue() method checks for existence of a value:

boolean check = map.containsValue("Brienne of Tarth"); // false

Retrieve from a Map

The get() method accepts a key and returns the value associated with that key or null if there is no value.

String value = map.get(4); // Daenerys Targaryen

Remove from a Map

The remove() method accepts a key so it can find the entry to remove. It returns the value associated with the removed entry or null if there is no value.

map.remove(3); // removes and returns "Jon Snow" map.remove(3); // removes nothing and returns null

If we want to empty the map, we can call clear(). This is a void method so it does not return anything.

Map Size

The size() method returns number of entries in our map.

The isEmpty() method returns a boolean indicating if the map is empty or not.

boolean isEmpty = map.isEmpty();

Collection Views

The Map interface provides Collection view methods which allow us to view our map in terms of a collection type. These views provide the only mechanism for us to iterate over a map.

• keySet() — returns a Set of keys from the map
• values() — returns a Collection of values from the map
• entrySet() — returns a Set of Map.Entry objects which represent the key-value pairs in the map

It’s important to remember that views are backed by our map. This means any changes we make to the view update the underlying map and vice versa.

The collection views support removal of entries but not insertion.

keySet()

The keySet() method returns a Set view of the keys contained in our map:

Set keys = map.keySet(); // [1, 2, 4]

values()

The values() method returns a Collection of the values contained in our map:

Collection values = map.values(); // [Petyr Baelish, Sansa Stark, Daenerys Targaryen]

Why does it return a Collection instead of a Set? Because the values of a map aren’t guaranteed to be unique so a Set wouldn’t work.

entrySet()

The entrySet() method is used to get a Set view of the entries in our map. The Set will contain Map.Entry objects. A Map.Entry object is simply a key-value pair. We can call getKey() or getValue() on this object.

The most common usage of the entrySet is for looping which we’ll cover in the next section.

Iterating over a Map

There are many ways of iterating over a map. Let’s go over some common approaches.

Keep in mind that loops will throw a NullPointerException if we try to iterate over a map that is null.

Using foreach and Map.Entry

This is the most common method and is preferable in most cases. We get access to both keys and values in the loop.

for (Map.Entry entry : map.entrySet()) < System.out.println( entry.getKey() + " ->" + entry.getValue() ); >

Источник