Of Stack

Java source analysis of HashMap usage

  • 2020-12-13 18:57:58
  • OfStack

- HashMap -

Advantages: Super fast query speed, time complexity can reach O (1) data structure only HashMap. Dynamic variable length storage of data (as opposed to arrays).

Disadvantages: Extra hash value needs to be calculated once, which can take up extra space if not handled properly.

-- How to use HashMap --

We usually 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 types. Basic data types are not accepted here to do K,V

If you write it this way, you have a problem: 


Map<int,double> maps=new HashMap<int,double>();

Why do we use it this way? 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 dynamic variable length data structure --

When using HashMap, in order to improve the efficiency of execution, we usually set HashMap initialization capacity: 


Map<String,String> rm=new HashMap<String,String>(2)

Or use guava's utility class Maps, which makes it easy to create a collection with the appropriate size initialization values. 


Map<String, Object> map = Maps.newHashMapWithExpectedSize(7);

So why use it this way? Let's look at their source code constructors.

Unreferenced constructor: 


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); 
  }

Noun explanation: 


DEFAULT_LOAD_FACTOR  // Default load factor, if not specified 0.75  
DEFAULT_INITIAL_CAPACITY // Default initializes capacity, default is 16  
threshold // Threshold ( yu ) value   According to the load factor and initialization capacity calculation   . <span style="color: rgb(54, 46, 43); font-family: "microsoft yahei";">threshold Said when HashMap the size Is greater than threshold When performing resize Operation.

So we know that if we call the no-argument constructor, we're going to get a 16-size array.

So the question is: What if the initial capacity isn't enough?

Array is a fixed length, how to use a fixed length data to represent a variable length data, the answer is to find a longer, but in resize is very inefficient. Therefore, we recommend that HashMap be initialized to a reliable capacity.

-- HashMap's Put method -- 


public V put(K key, V value) {  
    if (key == null) // If the key is empty, HashMap and HashTable the 1 A difference between   
      return putForNullKey(value);  
    int hash = hash(key.hashCode()); // According to the key hashCode Calculate the hash value   
    int i = indexFor(hash, table.length); // According to the hash Value to figure out which index to put into the array   
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {// The whole for The loop implements if it exists K So let's substitute 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 more data is inserted than the current capacity, it is executed 


addEntry(hash, key, value, i);

Map<int,double> maps=new HashMap<int,double>();
0

It shows if the current size++ > threshold would have extended resize (2* table.length) twice as much as the current size, so how did they extend? 


Map<int,double> maps=new HashMap<int,double>();
1

How is transfer transferred for the transfer array? 


Map<int,double> maps=new HashMap<int,double>();
2

-- hashmap expansion additional execution times --

So if we were to add 1 hashMap with 1000 elements, how many extra computes would we need if we were to use the default

When greater than 16*0.75=12, the calculation needs to be redone 12 times

When greater than 16*2*0.75=24, an additional 24 calculations are required

...

When greater than 16*n*0.75=768, an additional 768 calculations are required

So in total we counted 12+24+48+ during the expansion... + 768 times

Therefore, it is strongly recommended that we manually specify the initial size in the project if we know the scope, as follows: 


Map<Integer,String> maps=new HashMap<Integer,String>(1000);

Summary: This is why the efficiency of hashmap is severely reduced when the initial capacity is exceeded.

Above is the Java source Angle analysis of HashMap usage of the whole content, I hope to help you. Interested friends can continue to refer to other related topics in this site, if there is any deficiency, welcome to comment out. Thank you for your support!

Related articles: