What is Java Map Interface
The Java Map interface is a part of Java Collection framework, but it is not a subtype of the Collection interface. So it behaves in a different way compared to, say, Lists, or other collection Objects. Each element of Map<Key, Value> represents a key-value pair. Both Key and value are some objects. All keys in a particular map are unique, while values are not, so they can be duplicated. You may think of Map in Java such as a kind of dictionary or online-shop catalog, where you can find any item using its unique index. The key is a unique identifier of the value in a Map. For example in Map<String, Item> String is an ID of some Item from the online shop. According to documentations Map has the next Subinterfaces:ConcurrentMap<K,V>
;ConcurrentNavigableMap<K,V>
;LogicalMessageContext
;MessageContext
;NavigableMap<K,V>
;SOAPMessageContext
;SortedMap<K,V>
.
Bindings
;
AbstractMap
Attributes
AuthProvider
ConcurrentHashMap
ConcurrentSkipListMap
EnumMap
HashMap
Hashtable
IdentityHashMap
LinkedHashMap
PrinterStateReasons
Properties
Provider
RenderingHints
SimpleBindings
TabularDataSupport
TreeMap
UIDefaults
WeakHashMap
- Java
AbstractMap
is an abstract class that implements most of the Map interface. - Java
HashMap
is a data structure for storing key-value pairs using a hash table. - Java
TreeMap
is a data structure to use a tree, i.e. display with sorted keys. WeakHashMap
to use a hash table with weak keys, display with values that can be deleted by the garbage collector if they are no longer used.LinkedHashMap
is a map with the order of adding elements, allows iteration in the insertion order.EnumMap
extends theAbstractMap
class for use with enum keys.
IdentityHashMap
uses referential equivalence checking when comparing documents, mapping with keys compared using ==
operation instead of equals()
methodMap methods
The main operations of any Map are insertion, remove, and search of elements.public Object put(Object key, Object value)
inserts an element into the map.public void putAll(Map map)
inserts the specified map inside the map.public Object remove(Object key)
deletes an entry according to the specified key.public Object get(Object key)
returns the value for the specified key.public boolean containsKey(Object key)
searches the specified key from this mappublic Set keySet()
returns a Set view that contains all the keyspublic Set entrySet()
returns a Set view with all the keys and values.
What is HashMap
What is HashMap? It is the most popular implementation of Map<Key,Value> interface. This data structure is based on the hashing principle.The main principle of HashMap work: hashing
To understand what is a hashmap and how it works, let’s talk about hashing and hash functions first. A hash function is just a function in a mathematical sense. So there is some input value (an object, a piece of data) and function converts it using a proper rule into output value - a hash. Pretty often hash is a hexadecimal number of a proper length. Rules of converting processes could be different, but they are subject to the following principles:- A particular input (object) has a particular hash code.
- If two objects are equal, their hash codes are equal as well. The reverse is not true.
- If the hash codes are different, the objects are definitely not equal.
- Sometimes different objects can have the same hash code. It is a very unlikely event, named “collision” and a good quality hash function should minimize the probability of collisions.
HashMap: how it works
So Class HashMap<K,V> as every Map implementation consists of keys and values. It stores keys using hashing principles. Inside the HashMap Key-value pairs are stored in "buckets", these buckets together construct a "table", an internal array of linked lists and itsinitial size is 16
. HashMap in Java uses the key’s hashcode to determine a bucket where the key/value pair should map:
The tricky feature of HashMap is that each cell (bucket) of the table [] keeps not only one pair but several. They are not stored as an explicit object (like LinkedList), but as an implicit chain. The chain is created due to the fact that each pair stores a link to the next pair. That is, all HashMap pairs are scattered across 16 chains. When you put a new pair into the table, the hash of the key is considered. This hash is not a hashcode function built into the key object. It is considered to be in the range of 0-15. The pair is added to the chain of pairs stored in the bucket with the hash index.
This approach gives us search acceleration. While searching for a pair by key, there is no need to go through the entire table. The hash of the key is considered and only the chain that is stored in the cell with the hash index is checked. If there are too many pairs in the HashMap, the chains become too long. Then the size of the array increases, the hash of all stored objects is recalculated, and they are scattered along new chains.
HashMap Declaration
If you go to the class HashMap code you will find the next declaration:Where
K
is the type of keys maintained by this map and V
- the type of mapped values. This is an example of HashMap declaration with Integer key and String value in your code:
HashMap methods
Here is the list of HashMap methods.Object get(Object key)
returns the value for the specified key;Object put(Key k, Value v)
inserts key value mapping into the map;Object remove(Object key)
removes the mapping for the specified key from this map if present;void clear()
removes all the key-value pairs from the HashMap;Object clone()
returns a shallow copy of this HashMap instance without cloning the keys and values;boolean containsKey(Object key)
returns true if the specified key is found in the map, false if isn’t;boolean containsValue(Object Value)
returns true if the specified key is found in the map, false if isn’t;boolean isEmpty()
returns true if the map is empty, false if isn’t;Set keySet()
returns the Set of the keys fetched from the map;int size()
returns the quantity of key-value mapping;Collection values()
returns a collection of the map’s values;Object remove(Object key)
removes the key-value pair for the specified key;void putAll(Map m)
copies all elements of the map to the other map.
Java HashMap Example
Let’s create a program with Java HashMap Example to demonstrate how it works:The result of running the program:
TreeMap
TreeMap in Java also implements Map<Key,Value> interface, but it is based on Red-Black tree data structure. A Tree consists of "nodes" and lines that connect nodes - branches". The "root" node is at the top of the tree. From the root, there can be branches and nodes. It is a hierarchical structure, you may think of these nodes as "children" of the root. Child node can have its own children - lower nodes. Nodes without children are called "end-nodes" or "leaves". A binary tree is a tree, where every node has zero, one, or two children. The binary search tree is a structure, where every internal node stores a key, and sometimes an associated value, and has two distinguished sub-trees ("left" and "right"). A self-balancing binary search tree is a node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions. A red-black tree is a balanced binary tree with the properties:- Every node is either red or black
- The root is always black
- Every leaf is a NIL (kind of empty, null) node and it is black
- If a node is red, its children are definitely black.
- Every simple path from a node to a descendant leaf contains the same number of black nodes.
A TreeMap features
A TreeMap uses a tree data structure to store the keys as the nodes and sorts the keys using the Red-Black Tree algorithm. So, TreeMap keeps its entries sorted according to the natural ordering of its keys. For numbers natural is ascending order, for strings — alphabetical order. You can use a comparator if you need to change the logic of ordering. Sorting objects in a natural way is a big advantage of TreeMap, as well as finding some objects using different filters and conditions.TreeMap methods
Object get(Object key)
returns the value of the corresponding key;Object put(Object key, Object value)
inserts a mapping into a map;Object remove(Object key)
removes the mapping for this key from if the TreeMap contains it;boolean containsKey(Object key)
returns true if this map contains a mapping for the specified key;boolean containsValue(Object value)
returns true if the TreeMap maps one or more keys to the specified value;Object firstKey()
returns the first key currently in the sorted map;Object lastKey()
returns the last key currently in the sorted map;void putAll(Map map)
copies all mappings from the specified map to the map;Set entrySet()
returns a set view of the mappingsint size()
returns the quantity of key-value mappingsCollection values()
returns a collection view of the valuesObject clone()
returns a shallow copy of the TreeMapvoid clear()
removes all mappings from the TreeMapSortedMap headMap(Object key_value)
returns a view of the portion of the map less than the parameter key_valueSet keySet()
returns a Set view of the keys contained in the treemapSortedMap subMap(K fromKey, K toKey)
returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusiveObject firstKey()
returns the first key from the TreeMap.
TreeMap example
The result of running the program:LinkedHashMap
LinkedHashMap is a data structure that combines linked lists and hash maps. Indeed, LinkedHashMap extends the HashMap class and implements the Map interface, but what is it about linked lists? The declaration of LinkedHashMap:This new linkedHashMap inherits properties from HashMap (such as table, loadFactor, threshold, size, entrySet), also gets two special properties:
- header is the head of a doubly linked list. During the initialization, it indicates itself
- accessOrder indicates how to get access to elements using iterator. If true, in the order of the last access. If false, access will be in the order the elements were inserted.
LinkedHashMap Methods
Object get(Object key)
returns the value to which the specified key is mapped, or null if this map contains no mapping for the keyvoid clear()
removes all the mappings from the map.boolean containsKey(Object key)
returns true if the specified element is mapped by one or more keysboolean removeEldestEntry(Map.Entry eldest)
returns true if the map removes its eldest entry from the mapSet<Map.Entry7lt;K,V>> entrySet()
returns a Set view of the mappings contained in this mapvoid forEach(BiConsumer<? super K,? super V> action)
performs the given action for each entry in this map until all entries have been processed or the action throws an exception.Object getOrDefault(Object key, V defaultValue)
returns the value to which the specified key is mapped. If the map doesn’t contain a mapping for the key returns defaultValue.Set<K> keySet()
returns a Set view of the keys contained in the mapboolean removeEldestEntry(Map.Entry<K,V> eldest)
returns true if this map should remove its eldest entryvoid replaceAll(BiFunction<? super K,? super V,? extends V> function)
replaces each entry value with the result of invoking the given function on that entry until all entries have been processed or the function throws an exception.Collection<v>values()
returns a Collection view of the values contained in the map
LinkedHashMap example
Here we create a new LinkedHashMap, adding five elements, then print it out using iterator and in a classical way. As you can see, LinkedHashMap maintains the insertion order. After it we delete an element from our Map, then add the new one and later - one more element with the key, that is already on the map. It replaces the old value mapped to this key. The result of running program:HashMap, TreeMap, LinkedHashMap Comparison
HashMap, TreeMap, and LinkedHashMap are the implementations of Map interfaces. HashMap and LinkedHashMap are data structures that hashes keys. TreeMap uses the natural order of its keys to organizing a search tree. Order:- HashMap doesn’t maintain any order.
- TreeMap sorts the entries in ascending order of keys.
- LinkedHashMap maintains the insertion order.
- HashMap and LinkedHashMap allows having one null key.
- LinkedHashMap doesn’t allow null keys in case of the keys use natural ordering or Comparator doesn’t support comparison on null leys.
Here is the result of running this program:
As we can see, the order of elements in HashMap is not obvious, in treeMap it depends on keys, in LinkedHashMap it is about insertion order. If we try to put null key into linkedHashMap, we’ll get NullPointerException, but in linkedHashMap1, where keys are String, we can do it. A hash map is the best general-purpose map implementation. It provides maximum search speed, fast storage, and retrieval operations, but you should remember about its chaotic ordering. A linked hash map inherits HashMap advantages and gets an order for the keys. However, it contains linkedList, which is relatively costly in terms of memory. it is slower than HashMap in searching and a little bit slower for add/remove because of maintaining linked list. A tree map stores keys sorted in ascending order. However, it offers worse general performance than HashMap and LinkedHashMap.
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.