HashMap
1 HashMap
1.1 There are some important points about HashMap in Java:
1.1.1Java HashMap allows null key and null values.
note: As we know that HashMap also allows null, though there can only be one null key in HashMap. While storing the Entry object HashMap implementation checks if the key is null, in case key is null, it always map to bucket 0, as hash is not calculated for null keys.
1.1.2HashMap is not an ordered collection. You can iterate over HashMap entries through keys set but they are not guaranteed to be in the order of their addition to the HashMap.
1.1.3HashMap is almost similar to Hashtable except that it’s unsynchronized and allows null key and values.
1.1.4HashMap uses it’s inner class Node<K,V> for storing map entries.
1.1.5HashMap stores entries into multiple singly linked lists, called buckets or bins. Default number of bins is 16 and it’s always power of 2.
1.1.6HashMap uses hashCode() and equals() methods on keys for get and put operations. So HashMap key object should provide good implementation of these methods. This is the reason immutable classes are better suitable for keys, for example String and Interger.
1.1.7 Java HashMap is not thread safe, for multithreaded environment you should use ConcurrentHashMap class or get synchronized map usingCollections.synchronizedMap()method.
1.1.8 With in a bucket values are stored as Entry objects which contain both key and value.
1.1.9 Hashing collision means more than one key having the same hash value, in that case Entry objects are stored as a linked-list with in a same bucket.
1.2 Java HashMap Constructors:
1.2.1 public HashMap(): Most commonly used HashMap constructor. This constructor will create an empty HashMap with default initial capacity 16 and load factor 0.75
1.2.2 public HashMap(int initialCapacity)
: This HashMap constructor is used to specify the initial capacity and 0.75 load factor. This is useful in avoiding rehashing if you know the number of mappings to be stored in the HashMap.
1.2.3 public HashMap(int initialCapacity, float loadFactor)
: This HashMap constructor will create an empty HashMap with specified initial capacity and load factor. You can use this if you know the maximum number of mappings to be stored in HashMap. In common scenarios you should avoid this because load factor 0.75 offers a good tradeoff between space and time cost.
1.2.4 public HashMap(Map<? extends K, ? extends V> m):
Creates a Map having same mappings as the specified map and with load factor 0.75.
note:The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.
1.3. Java HashMap Method
1.3.1 public void clear(): This HashMap method will remove all the mappings and HashMap will become empty.
1.3.2 public boolean containsKey(Object key)
: This method returns ‘true’ if the key exists otherwise it will return ‘false’.
1.3.3 public boolean containsValue(Object value)
: This HashMap method returns true if the value exists otherwise false.
1.3.4 public Set<Map.Entry<K,V>>entrySet()
: This method returns a Set view of the HashMap mappings. This set is backed by the map, so changes to the map are reflected in the set, and vice-versa.
1.3.5 public V get(Object key)
: Returns the value mapped to the specified key, or null if there is no mapping for the key.
1.3.6 public boolean isEmpty()
: A utility method returning true if no key-value mappings are present.
1.3.7 public Set<K>keySet()
: Returns a Set view of the keys contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa.
1.3.8 public V put(K key, V value)
: Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced.
1.3.9 public void putAll(Map<? extends K, ? extends V>m)
: Copies all of the mappings from the specified map to this map. These mappings will replace any mappings that this map had for any of the keys currently in the specified map.
1.3.10 public V remove(Object key)
: Removes the mapping for the specified key from this map if present.
1.3.11 public int size()
: Returns the number of key-value mappings in this map.
1.3.12 public Collection<V> values()
: Returns a Collection view of the values contained in this map. The collection is backed by the map, so changes to the map are reflected in the collection, and vice-versa.
2. HashMap implement
JavaHashMap use its inner class Node<K, V> for string mappings. HashMap works on hashing algorithm and used hashCode() and equals() method on key for get and put operations.
HashMap use singly linked list to store elements, these are called bins or buckets. When we call put method, hashCode of key is used to determine the bucket that will be used to store the mapping.
Once bucket is identified, hashCode is used to check if there is already a key with same hashCode or not. If there is an existing key with same hashCode, then equals() method is used on key. If equals returns true, then value is overwitten, otherwise a new mapping is made to this singly linked list bucket. If there is no key with same hashCode then mapping is inserted into the bucket.
For HashMap get operation, again key hashCode is used to determine the bucket to look for the value. After bucket is identified, entries are traversed to find out the Entry using hashCode and equals method. If match is found, value is returned otherwise null is returned.
3. HashMap changes in Java 8
Though HashMap implementation provides constant time performance O(1) for get() and put() method but that is in the ideal case when the Hash function distributes the objects evenly among the buckets.
But the performance may worsen in the case hashCode()used is not proper and there are lots of hash collisions. As we know now that in case of hash collision entry objects are stored as a node in a linked-list and equals()method is used to compare keys. That comparison to find the correct key with in a linked-list is a linear operation so in a worst case scenario the complexity becomes O(n).(Hashing collision means more than one key having the same hash value, in that case Entry objects are stored as a linked-list with in a same bucket.)
To address this issue in Java 8 hash elements use balanced trees instead of linked lists after a certain threshold is reached. Which means HashMap starts with storing Entry objects in linked list but after the number of items in a hash becomes larger than a certain threshold, the hash will change from using a linked list to a balanced tree, this will improve the worst case performance from O(n) to O(log n).
4. ConcurrenctHashMap, How the ConcurrentHashMap implement?
Concurrence HashMap performs better than HashTable and synchronized Map because it only locks a portion of Map, instead of whole Map, which is the case with HashTable and synchronized Map.
ConcurrentHashMap:It allows concurrent access to the map. Part of the map called _Segment (internal data structure)_is only getting locked while adding or updating the map. So ConcurrentHashMap allows concurrent threads to read the value without locking at all. This data structure was introduced to improve performance.
Concurrency-Level: Defines the number which is an estimated number of concurrently updating threads. The implementation performs internal sizing to try to accommodate this many threads.
Load-Factor: It's a threshold, used to control resizing.
Initial Capacity: The implementation performs internal sizing to accommodate these many elements.
ConcurrentHashMap is introduced as an alternative of Hashtable and provided all functions supported by Hashtable with an additional feature called "concurrency level", which allows
ConcurrentHashMap to partition Map. ConcurrentHashMap allows multiple readers to read concurrently without any
Read more:
5. HashTable
Last updated
Was this helpful?
