―HashMap―
Advantages: Super fast query speed and data structures that can reach O(1) time complexity is HashMap. Dynamic variable-length storage data (relative to arrays).
Disadvantages: The hash value needs to be calculated extra, and if it is not handled properly, it will take up extra space.
―How to use HashMap―
Usually we use hashmap as follows
Map<Integer,String> maps=new HashMap<Integer,String>(); maps.put(1, "a"); maps.put(2, "b");
The above code creates a new HashMap and inserts two data. The basic data types are not accepted here to do K and V.
If you write this, there will be problems:
Map<int,double> maps=new HashMap<int,double>();
Why do we use this way? Please see the source code:
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
This is the definition of the HashMap implementation class.
―HashMap is a dynamically variable-length data structure―
When using HashMap, in order to improve execution efficiency, we often set the HashMap initialization capacity:
Map<String,String> rm=new HashMap<String,String>(2)
Or use guava's tool class Maps to easily create a collection and initialize the value with the appropriate size.
Map<String, Object> map = Maps.newHashMapWithExpectedSize(7);
So why use it like this? Let's look at their source constructor.
Constructor without parameters:
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); } public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
/** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and the default load factor (0.75). * * @param initialCapacity the initial capacity. * @throws IllegalArgumentException if the initial capacity is negative. */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }Explanation of nouns:
DEFAULT_LOAD_FACTOR //Default loading factor, 0.75 if not specified. DEFAULT_INITIAL_CAPACITY //Default initialization capacity, default is 16 threshold //The threshold (yu) value is calculated based on the load factor and initialization capacity. <span style="color: rgb(54, 46, 43); font-family: "microsoft yahei";">threshold means that when the size of HashMap is greater than threshold, the resize operation will be performed.
So we know that if we call the parameterless constructor, we will get an array of 16 capacity.
So the question is: What if the initial capacity is not enough?
Arrays are fixed-length, how to use fixed-length data to represent uncertain-length data? The answer is to find a longer one, but it reduces efficiency when resizes. So we recommend that HashMap be given a reliable capacity when initializing.
―HashMap Put method―
public V put(K key, V value) { if (key == null) //If the key is empty, a difference between HashMap and HashTable returns putForNullKey(value); int hash = hash(key.hashCode()); //Frame the hash value based on the hashCode of the key int i = indexFor(hash, table.length); //Frame the array subscript to put into based on the hash value for (Entry<K,V> e = table[i]; e != null; e = e.next) {//The entire for loop implements that if K exists, then replace V Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++;//Counter addEntry(hash, key, value, i); //Add to array return null; }If the inserted data exceeds the existing capacity, it will be executed
addEntry(hash, key, value, i);
void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); if (size++ >= threshold) <span style="color:#ff0000;"><strong> resize(2 * table.length);}Here, if the current size++ >threshold is displayed, then the current size will be expanded twice and resize (2*table.length) will be executed. So how do they expand?
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; <span style="color: rgb(51, 51, 51); font-family: Arial;">new A new array, </span> <strong> <span style="color:#ff0000;">transfer(newTable);</span> </strong> //Transfer the array to a new array table = newTable; threshold = (int)(newCapacity * loadFactor); //Recalculate the capacity}How is the transfer array transfer transferred?
void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { src[j] = null; do { Entry<K,V> next = e.next; int i = <strong><span style="color:#ff0000;">indexFor(e.hash, newCapacity); //Recalculate the index based on the hash value capacity</span></strong> e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } }―The number of additional executions of hashmap expansion-
So if we want to add a hashMap of 1000 elements, if we use the default value, how many additional calculations do I need to calculate?
When it is greater than 16*0.75=12, it needs to be recalculated 12 times
When it is greater than 16*2*0.75=24, an additional 24 calculations are required.
...
When it is greater than 16*n*0.75=768, an additional 768 calculations are required.
So we calculated 12+24+48+…+768 times in the expansion process
Therefore, it is strongly recommended that we should manually specify the initial size if we know the scope in the project like this:
Map<Integer,String> maps=new HashMap<Integer,String>(1000);
Summary: This is why the execution efficiency of hashmap is severely reduced if it exceeds the initial capacity during use.
The above is all about the use of HashMap in this article about Java source code analysis, I hope it will be helpful to everyone. Interested friends can continue to refer to other related topics on this site. If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!