- [free] exclusive: this is a very valuable collection of Android knowledge system!!
| type | describe | when |
|---|---|---|
| Topic selection | silencezwm | 0.1 hours |
| Time to write | December 3, 2017 | 5 hours |
| reviewing | silencezwm | 0.5 hours |
| Check online | silencezwm | 0.1 hours |
Tips:4 links, 5.7 hours of careful polishing to complete the online.
In our daily development process, HashMap usage is still very high. This paper will first give a brief introduction to the basic attributes and methods of the Map interface, and then discuss the initialization and data addition of HashMap.
Through the learning of this article, you can learn:
A brief introduction to Map interfaces
Initialization of HashMap
The process of adding data to HashMap
A brief introduction to Map interfaces
We can see the Map source code, Map is key-value(key-value pair) in the form of interface, derived from it is quite a number of interfaces and classes, such as today’s main character HashMap, TreeMap, Hashtable, SortedMap and so on.
Its common methods and descriptions are as follows:
| methods | describe |
|---|---|
| V put(K key, V value) | Stores a key-value pair into the Map and returns a Value |
| void putAll (Map<? extends K, ? extends V> map) | Store a Map data to a Map |
| V remove (Object key) | Delete the data based on the key and return the Value |
| void clear () | Clear existing Map data |
| V get (Object key) | Query the corresponding Value based on the key |
| boolean isEmpty () | Check whether the Map is empty |
| int size () | Returns the number of data stored in the Map |
| boolean containsKey (Object key) | Check whether the Map contains the key |
| boolean containsValue (Object value) | Check whether the Map contains the value |
For more information about Map, see the Api documentation
Initialization of HashMap
Let’s take a look at the inheritance and interface implementation of HashMap:
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
Copy the codeAbstractMap also implements the Map interface. Therefore, there is no doubt that a HashMap has all the characteristics of a Map. And the static inner class HashMap HashMapEntry<K,V> also implements the map. Entry<K,V> interface, as follows:
static class HashMapEntry<K,V> implements Map.Entry<K,V> { final K key; V value; HashMapEntry<K,V> next; int hash; HashMapEntry(int h, K k, V v, HashMapEntry<K,V> n) { value = v; next = n; key = k; hash = h; }... }Copy the codeEach data stored in a HashMap table is an object of HashMapEntry<K,V>, which contains the key, value, the reference object next to the next object, and the hash code value generated by that key.
Let’s start by looking at a few important global variables of HashMap
Static final int DEFAULT_INITIAL_CAPACITY = 4; Static final int MAXIMUM_CAPACITY = 1 << 30; Static final float DEFAULT_LOAD_FACTOR = 0.75f; Static final HashMapEntry<? ,? >[] EMPTY_TABLE = {}; [] TABLE = (HashMapEntry<K,V>[]) EMPTY_TABLE; // This deserialized array table is used when HashMap needs to adjust capacity. // HashMap transient int size; // This value is used when the HashMap needs to adjust the capacity using int threshold; // loadFactor, default is 0.75f final float loadFactor = DEFAULT_LOAD_FACTOR; // counter TRANSIENT int modCount;Copy the codeA HashMap can be constructed by:
| methods | describe |
|---|---|
| HashMap() | Get a new empty HashMap instance |
| HashMap(int capacity) | Instantiate the empty HashMap based on the incoming capacity |
| HashMap(int capacity, float loadFactor) | Instantiate the empty HashMap based on the incoming capacity, load factor |
| HashMap(Map<? extends K, ? extends V> map) | Pass in an existing Map object to instantiate the new HashMap |
We’ll explore the first constructor, which looks like this:
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) {
initialCapacity = MAXIMUM_CAPACITY;
} else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
initialCapacity = DEFAULT_INITIAL_CAPACITY;
}
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
threshold = initialCapacity;
init();
}
Copy the codeAs you can see from the default constructor, there are two parameters initialCapacity and loadFactor. Since we didn’t pass these two parameters in through any other constructor, the default values will be used.
The constructor is shown as follows using a flow chart:
Therefore, the whole initialization process is just to judge the rationality of parameters and determine the initial values of several variables.
The process of adding data to HashMap
Now that we have an instance of a HashMap, we can store data in it using the following methods:
public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null) return =; int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key); int i = indexFor(hash, table.length); for (HashMapEntry<K,V> e = table[i]; e ! = null; e = e.next) { 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++; addEntry(hash, key, value, i); return null; }Copy the codeThe entire process of the PUT method is resolved as follows:
InflateTable initialization: In the constructor, we did not initialize the table, so the inflateTable method will be executed.
private void inflateTable(int toSize) {
int capacity = roundUpToPowerOf2(toSize);
float thresholdFloat = capacity * loadFactor;
if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
thresholdFloat = MAXIMUM_CAPACITY + 1;
}
threshold = (int) thresholdFloat;
table = new HashMapEntry[capacity];
}
private static int roundUpToPowerOf2(int number) {
int rounded = number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (rounded = Integer.highestOneBit(number)) != 0
? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
: 1;
return rounded;
}
Copy the codeRoundUpToPowerOf2 (roundUpToPowerOf2) roundUpToPowerOf2 (roundUpToPowerOf2) roundUpToPowerOf2 (roundUpToPowerOf2) roundUpToPowerOf2 (roundUpToPowerOf2)
2. Store data by key: There are two handling cases: Key is null and key is not null.
Case 1: The key is null
In this case, the putForNullKey method is called,
private V putForNullKey(V value) { for (HashMapEntry<K,V> e = table[0]; e ! = null; e = e.next) { if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(0, null, value, 0); return null; }Copy the codeThe array table is iterated from beginning to end. When a null key is found, the old value is replaced by the new value and the old value is returned. Otherwise, the counter modCount is incremented by 1, the addEntry method is called, and null is returned.
Case 2: The key is not null
In this case, the table is searched for the value of the same bucketIndex based on the bucketIndex generated by indexFor(hash, table.length). If yes, the old value is replaced with the new value and the old value is returned. Otherwise, the counter modCount is incremented by 1, the addEntry method is called, and null is returned.
Both cases end up pointing to the addEntry method. Let’s see how it is implemented:
void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null ! = table[bucketIndex])) { resize(2 * table.length); hash = (null ! = key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); }Copy the codeIn this method, check whether the table needs to be expanded. If you need to expand the table, run the resize method and enter twice the length of the existing table.
void resize(int newCapacity) {
HashMapEntry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
HashMapEntry[] newTable = new HashMapEntry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
Copy the codeThe resize method returns integer.max_value if the table has reached its maximum size. Otherwise, create a new table based on the new capacity value and perform the data migration method transfer.
void transfer(HashMapEntry[] newTable) { int newCapacity = newTable.length; for (HashMapEntry<K,V> e : table) { while(null ! = e) { HashMapEntry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; }}}Copy the codeThe transfer method migrates all data from the old table to the new table.
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry<K,V> e = table[bucketIndex];
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
size++;
}
Copy the codeFinally, add the data to the bucketIndex position of the table and add size by 1.
Now, two small diagrams represent the two states of the PUT process, as follows:
The bucketIndex location is determined by the key and the length of the table. It can be calculated in addEntry method:
bucketIndex = indexFor(hash, table.length);
Copy the codeTherefore, it is possible to have the same bucketIndex, also known as a bucketIndex collision. When a collision occurs, the values of the same bucketIndex will be linked together in a single chain. In this case, the next in HashMapEntry<K,V> will point to the next element. Which proves the following statement:
If hashCode is different, equals must be false; Equals is not set to true if hashCode is the same.
Finally, I wish you a happy study!
- [free] exclusive: this is a very valuable collection of Android knowledge system!!