static final int DEFAULT_INITIAL_CAPACITY = 16; // The default length of the main array is 16
static final float DEFAULT_LOAD_FACTOR = 0.75f; // Default load factor is 0.75
transient Entry<K,V>[] table; // Main array. Each element is of type Entry
transient int size; // The number of elements in the interface defaults to 0
int threshold;// The threshold value is 16*0.75=12
final float loadFactor;// The variable used to receive the load factor
Copy the codeLook at the hashMap no-parameter constructor
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); / / this (16,0.75 f)
}
Copy the codeHashmap parameter constructor: initializes some values
public HashMap(int initialCapacity, float loadFactor) {
Capacity must be greater than the minimum NTH power of 2 of initialCapacity that you passed in
int capacity = 1;
while (capacity < initialCapacity) // The while loop breaks. Capacity is 16
capacity <<= 1;
// To assign loadFactor, assign the loadFactor 0.75 to loadFactor
this.loadFactor = loadFactor;
// The threshold of array expansion is 12
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// Assign to the table array, initialize the array length to 16
table = new Entry[capacity];
}
Copy the codeThe put method:
public V put(K key, V value) {
// The hashMap key can be null
if (key == null)
return putForNullKey(value);
// Call the hash method to get the hash code
int hash = hash(key);
// Get the position of the key in the array
int i = indexFor(hash, table.length);
// If the element you put in has no value at that position in the main array, e==null then the following loop does not work
// When an element is placed in the same place, e! = null indicates that there are already elements (that is, hash collisions)
for(Entry<K,V> e = table[i]; e ! =null; e = e.next) {
Object k;
// the hash value is the same (k = e.key) == key
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
// Get the old value
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
/ / return oldValue
return oldValue;
}
}
modCount++;
// go to addEntry to add this node:
addEntry(hash, key, value, i);
return null;
}
Copy the code// The hash method returns the corresponding hash value of the key.
final int hash(Object k) {
int h = 0;
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
// k.hashcode () calls the hash function of the key type,
// Since different objects may have the same hashCode(), hashCode() needs to be hashed again to reduce the sameness rate.
h ^= k.hashCode();
/* The next series of and operations and xOR operations are called "perturbation function". The core idea of perturbation is to increase the uncertainty of the calculated value while retaining the original related characteristics, so as to reduce the probability of conflict. Different versions implement it differently, but the underlying idea is the same. The purpose of moving to the right is to take advantage of the high position of H and reduce kazakh conflict */
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
Copy the code// Return the coordinates of an array of type int (get the position of the key in the corresponding array)
static int indexFor(int h, int length) {
// This algorithm is the same as h%length
return h & (length-1);
}
Copy the code/ / call addEntry
void addEntry(int hash, K key, V value, int bucketIndex) {
// if the size is greater than 16*0.75=12, for example, if you want to place the 13th element where there is no element
if ((size >= threshold) && (null! = table[bucketIndex])) {// The main array is doubled
resize(2 * table.length);
// Rehash the hash code of the current element
hash = (null! = key) ? hash(key) :0;
// Recalculate the element position
bucketIndex = indexFor(hash, table.length);
}
/ / the hash key, value, bucketIndex position Packaging for an Entry object:
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
// Get the bucketIndex element to e
Entry<K,V> e = table[bucketIndex];
// Wrap hash, key, and value as an object, and set the next element to e.
// Place the new Entry in table[bucketIndex]
table[bucketIndex] = new Entry<>(hash, key, value, e);
// Add an element size+1 to the set
size++;
}
Copy the codeSummary of basic working principles of HashMap (1.7) :
In a Hashmap, the underlying main array is an Entry[] array, with a length of 16 and a default load factor of 0.75 (if the loading factor is 1, then the array is full and then expanded to achieve maximum space utilization). However, this is an ideal state, since elements cannot be completely evenly distributed, it is likely that hash collisions will generate linked lists. It takes a long time to generate linked lists. (If it is 0.5, it will waste space, but if it can be expanded to 0.5, then hashi collisions will be less, and no linked list will be generated. Therefore, the median value between space and time is 0.75, The limit value of array expansion is 16 x 0.75 = 12. During the PUT method, the hash code is first obtained through the hash method (The hash method returns the hash value corresponding to the key, which is internally hashed twice to ensure that different keys get different hash codes. Moreover, different objects may have the same Hashcode, so the hashcode needs to be hashed again to reduce the sameness rate, and internally uses a string of and and xOR operations (also known as the perturbation function, To obtain the position of the key in the corresponding array (internally achieved by bit operation), then add elements to the set, see the above for details of the process of adding elements (there are detailed instructions)!
Why is the length of the main array a multiple of 2?
The length of the key will affect the position of the key.
An integer multiple of 2:
If not an integer multiple of 2:
If it is not an integer multiple of 2, then the probability of hash collision is greatly increased