Omit the red-black tree version of the simple HashMap
Some basic parameters of a handwritten HashMap
The initial capacity of a HashMap is 16, which is a rule of thumb and is related to the fact that it requires a power of 2 to expand.
- Initial capacity
- The maximum capacity
- Default load factor
- The load factor
- The size size
- An array of elements
Why is HashMap expansion a power of two?
A simple implementation of the hash algorithm is that the key and the length of the array are complementary to find the location of the current element. But mod performance is very poor. So the source code is how to do it, is by bit and bit operation (table.length-1) & hash, we know that the speed of bit operation is far higher than the remainder operation. So the result of this bitwise sum is where the element should be in the array. The power of 2 has only one power of 1, and the rest is 0, minus one power of 0, and the rest is 1.
Why is the maximum capacity 2 to the 30th and not 2 to the 31st?
Since the length of an int is four bytes (32 bits), it should be possible to move it 31 bits to the left (2 ^ 31). But in fact, since the highest and leftmost bits of the binary digit are the sign bits, used to indicate the difference between positive and negative (0 is positive and 1 is negative), you can only move 30 bits to the left, not the sign bits that are everywhere in the highest bits.
// The initial capacity
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// Maximum capacity
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75 f;
final float loadFactor;
int initialCapacity;
transient int entrySize;
transient Entry<K,V>[] table = null;
Copy the codeThe Map interface
We need a Map interface to define behaviors that provide basic GET, PUT, and Remove
interface Map_<K.V>{
int size(a);
V get(Object key);
V put(K key, V value);
V remove(Object key);
interface Entry<K.V>{
K getKey(a);
V getValue(a); }}Copy the codeInitialize the
When we create a map, we need to perform constructors to set the capacity or load factor we set, so we need multiple constructors to support these operations.
public HashMap_(a) {
this(DEFAULT_INITIAL_CAPACITY,DEFAULT_INITIAL_CAPACITY);
}
public HashMap_(int initialCapacity){
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap_(int initialCapacity, float loadFactor) {
If the capacity is less than 0, throw an exception
if (initialCapacity < 0) {throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
}
// Also, the capacity cannot exceed the maximum limit
if (initialCapacity > MAXIMUM_CAPACITY){
this.initialCapacity = MAXIMUM_CAPACITY;
}
// Check the load factor
if (loadFactor <= 0 || Float.isNaN(loadFactor)){
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
}
// Initialization of other attributes
this.loadFactor = loadFactor;
this.initialCapacity = initialCapacity;
table = new Entry[initialCapacity];
}
Copy the codeThree basic constructors are provided, supporting no-parameter construction, capacity setting, and capacity and load factor setting. In addition, the definition of the Entry array can be modeled after the source code of the entire static inner class.
Entry array
static class Entry<K.V> implements Map_.Entry<K.V>{
final K key;
V value;
Entry<K,V> next;
public Entry(K key, V value, Entry<K, V> next) {
this.key = key;
this.value = value;
this.next = next;
}
@Override
public K getKey(a) {
return this.key;
}
@Override
public V getValue(a) {
return this.value; }}Copy the codeThe hash function
There’s nothing to say. This is a copy of XD
static final int hash(Object key) {
int h;
return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
}
Copy the codecapacity
@Override
public int size(a) {
return entrySize;
}
Copy the codeAccess to elements
When we get the element, we need to hash out the index position. If not, seek to find it in the linked list. This is not modulo operation, but operation and operation of binary bits, and we all know that shift operation is infinitely better than modulo operation. A power of two in binary is one at the beginning followed by zeros, minus one becomes all ones. And that will give us our index index position.
@Override
public V get(Object key) {
// Use the previous hash function to calculate the position in the array
int index = hash(key) & (initialCapacity - 1);
Entry<K,V> entry = table[index];
while(entry ! =null) {if (entry.getKey() == key || entry.getKey().equals(key)){
return entry.value;
}
entry = entry.next;
}
return null;
}
Copy the codecapacity
When putting elements, we need to perform capacity verification. Therefore, we cannot mindlessly put elements. Therefore, the pre-conditions of PUT expansion are given here. To expand, we need to create a new and larger array, entrySize is 0 (the new empty array), and then rehash to reposition the elements in the array.
private void resize(int newSize){
Entry[] newtable = new Entry[newSize];
entrySize = 0;
initialCapacity = newSize;
rehash(newtable);
}
private void rehash(Entry<K,V>[] newtable){
// Put the old entry into the collection for temporary storage
List<Entry<K,V>> entryList = new ArrayList<>();
for (Entry<K,V> entry : table){
while(entry ! =null){ entryList.add(entry); entry = entry.next; }}// Overwrite the old table with the new empty newtable
if (newtable.length > 0){
table = newtable;
}
// Rehash -> re-put entry into hashMap
for(Entry<K,V> entry : entryList){ put(entry.getKey(), entry.getValue()); }}Copy the codePlace the elements
We need to take that into account when we place elements
- Returns the old value
- Whether to expand capacity by 2 times
- Calculate the subscript
- Whether you want to put it in a linked list or whether you want to put it in a linked list or whether you want to overwrite it or whether you want to append it, those are all things you have to think about
The insertion of the linked list uses the simple header method of version 1.7 (easy version after all).
@Override
public V put(K key, V value) {
// Return the old value
V oldValue = null;
// Whether to expand the capacity
if(entrySize > this.loadFactor * initialCapacity){
resize(2 * initialCapacity);
}
// Calculate the position in the array, as in and
int index = hash(key) & (initialCapacity - 1);
// Empty indicates that there is no element in the current position
if (table[index] == null){
table[index] = new Entry<>(key,value,null);
} else {
// Same hash, inserted into the linked list
// We need to traverse the single linked list to find that value
Entry<K,V> head = table[index];
Entry<K,V> curr = head;
while(curr ! =null) {/ / the same key
if (curr.getKey() == key || curr.getKey().equals(key)){
oldValue = current.getValue();
// Replace the new value
curr.value = value;
// Be sure to return to avoid executing the following code
return oldValue;
}
// Different keys have the same hash
curr = curr.next;
}
// Insert into the header
table[index] = new Entry<>(key, value, head);
}
/ / to increase the size
++entrySize;
return oldValue;
}
Copy the codeRemove elements
Removing the element still returns the oldValue, so oldValue is defined ahead of time, and the index index is still hashed. Remember to reduce the size by 1, otherwise the size() method will return the wrong result, which is based on entrySize.
@Override public V remove(Object key) { V oldValue = null; Int index = hash(key) & (initialCapacity - 1); Entry<K,V> prev = table[index]; Entry<K,V> curr = prev; while (curr ! = null){ Entry<K,V> next = curr.next; if (curr.getKey() == key || curr.getKey().equals(key)){ oldValue = curr.getValue(); // Remember to reduce the capacity by 1 --entrySize; Table [index] table[index] = next; prev == curr; prev == curr; } else {// The previous node points to the next node of the current node. Next = next; } return oldValue; } prev = curr; curr = next; } return oldValue; }Copy the codetest
Finally, let’s do a test.
Map_<String,String> map = new HashMap_();
map.put("a"."aa");
map.put("b"."bb");
String put = map.put("a"."aaa");
System.out.println(put);
System.out.println(map.size());
System.out.println(map.get("a"));
System.out.println(map.get("b"));
String a = map.remove("a");
System.out.println(a);
System.out.println(map.size());
System.out.println(map.get("a")); Output: aa2
aaa
bb
aaa
1
null
Copy the code