outline
In this chapter, we learn about HashMap.
We first have an overall understanding of HashMap, then learn its source code, and finally learn to use HashMap through examples.
Part 1 Introduction to HashMap
Introduction to HashMap
HashMap is a hash table that stores key value mappings.
HashMap inherits from AbstractMap and implements Map, Cloneable and Java io. Serializable interface.
The implementation of HashMap is not synchronous, which means that it is not thread safe. Its key and value can be null. In addition, the mappings in HashMap are not ordered.
The instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table. The initial capacity is only the capacity of the hash table when it is created. Load factor is a measure of how full a hash table can be before its capacity automatically increases. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, rehash the hash table (that is, rebuild the internal data structure), so that the hash table will have about twice the number of buckets.
Typically, the default load factor is 0.75, which is a compromise between time and space costs. High load factor reduces space overhead, But it also increases the query cost (this is reflected in most HashMap class operations, including get and put operations). When setting the initial capacity, you should consider the number of entries required in the map and its loading factor, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the loading factor, rehash operations will not occur.
Constructor for HashMap
HashMap has four constructors, as follows:
// Default constructor. HashMap() // Specifies the constructor for capacity size HashMap(int capacity) // Specifies the constructor for capacity size and load factor HashMap(int capacity, float loadFactor) // Constructor containing "sub Map" HashMap(Map<? extends K, ? extends V> map)
HashMap API
void clear() Object clone() boolean containsKey(Object key) boolean containsValue(Object value) Set<Entry<K, V>> entrySet() V get(Object key) boolean isEmpty() Set<K> keySet() V put(K key, V value) void putAll(Map<? extends K, ? extends V> map) V remove(Object key) int size() Collection<V> values()
Part 2 HashMap data structure
Inheritance relationship of HashMap
java.lang.Object
↳ java.util.AbstractMap<K, V>
↳ java.util.HashMap<K, V>
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable { }The relationship between HashMap and Map is as follows:
As can be seen from the figure:
(01) HashMap inherits from AbstractMap class and implements map interface. Map is the "key value pair" interface, and AbstractMap implements the general function interface of "key value pair".
(02) HashMap is a hash table implemented by "zipper method". It includes several important member variables: table, size, threshold, loadFactor and modCount.
Table is an Entry [] array type, and Entry is actually a one-way linked list. The "key value pairs" of the hash table are stored in the Entry array.
Size is the size of the HashMap. It is the number of key value pairs saved by the HashMap.
Threshold is the threshold of HashMap, which is used to judge whether the capacity of HashMap needs to be adjusted. The value of threshold = "capacity * loading factor". When the number of data stored in HashMap reaches the threshold, the capacity of HashMap needs to be doubled.
loadFactor is the load factor.
modCount is used to implement the fail fast mechanism.
Part 3 HashMap source code analysis (based on JDK1.6.0_45)
In order to better understand the principle of HashMap, the source code of HashMap is analyzed below.
When reading the source code, it is recommended to refer to the following instructions to establish an overall understanding of HashMap, so that it is easier to understand HashMap.
package java.util;
import java.io.*;
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
// The default initial capacity is 16 and must be a power of 2.
static final int DEFAULT_INITIAL_CAPACITY = 16;
// Maximum capacity (must be a power of 2 and less than the 30th power of 2. If the incoming capacity is too large, it will be replaced by this value)
static final int MAXIMUM_CAPACITY = 1 << 30;
// Default load factor
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// An Entry array that stores data. The length is a power of 2.
// HashMap is implemented by zipper method, and each Entry is essentially a one-way linked list
transient Entry[] table;
// The size of the HashMap, which is the number of key value pairs saved by the HashMap
transient int size;
// The threshold value of HashMap is used to determine whether the capacity of HashMap needs to be adjusted (threshold = capacity * loading factor)
int threshold;
// Load factor actual size
final float loadFactor;
// Number of times HashMap has been changed
transient volatile int modCount;
// Specifies the constructor for capacity size and load factor
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// The maximum capacity of HashMap can only be MAXIMUM_CAPACITY
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Find the power of the smallest 2 greater than initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
// Set load factor
this.loadFactor = loadFactor;
// Set the "HashMap threshold". When the amount of data stored in the HashMap reaches the threshold, you need to double the capacity of the HashMap.
threshold = (int)(capacity * loadFactor);
// Create an Entry array to hold data
table = new Entry[capacity];
init();
}
// Specifies the constructor for capacity size
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// Default constructor.
public HashMap() {
// Set load factor
this.loadFactor = DEFAULT_LOAD_FACTOR;
// Set the "HashMap threshold". When the amount of data stored in the HashMap reaches the threshold, you need to double the capacity of the HashMap.
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
// Create an Entry array to hold data
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
// Constructor containing "sub Map"
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
// Add all elements in m to the HashMap one by one
putAllForCreate(m);
}
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
// Return index value
// H & (length-1) ensure that the return value is less than length
static int indexFor(int h, int length) {
return h & (length-1);
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
// Get the value corresponding to the key
public V get(Object key) {
if (key == null)
return getForNullKey();
// Get the hash value of the key
int hash = hash(key.hashCode());
// Find the element with "key value equal to key" on the "linked list corresponding to the hash value"
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
// Gets the value of the element whose key is null
// HashMap stores the element with "null key" in table[0]!
private V getForNullKey() {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
// Does HashMap contain key s
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
// Returns the key value pair of "key as key"
final Entry<K,V> getEntry(Object key) {
// Get hash value
// HashMap stores the element with "null key" in table[0]. If the "key is not null", call hash() to calculate the hash value
int hash = (key == null) ? 0 : hash(key.hashCode());
// Find the element with "key value equal to key" on the "linked list corresponding to the hash value"
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
// Add "key value" to HashMap
public V put(K key, V value) {
// If "key is null", add the key value pair to table[0].
if (key == null)
return putForNullKey(value);
// If "key is not null", calculate the hash value of the key, and then add it to the linked list corresponding to the hash value.
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// If the key value pair corresponding to "this key" already exists, replace the old value with the new value. Then exit!
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// If the key value pair corresponding to "this key" does not exist, add "key value" to the table
modCount++;
addEntry(hash, key, value, i);
return null;
}
// putForNullKey() is used to add the "key is null" key value pair to table[0]
private V putForNullKey(V value) {
for (Entry<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;
}
}
// This will not be implemented at all!
modCount++;
addEntry(0, null, value, 0);
return null;
}
// Create the "add method" corresponding to HashMap,
// It is different from put(). putForCreate() is an internal method, which is called by constructors and so on to create HashMap
// put() is an externally provided method for adding elements to HashMap.
private void putForCreate(K key, V value) {
int hash = (key == null) ? 0 : hash(key.hashCode());
int i = indexFor(hash, table.length);
// If there is an element with "key value equal to key" in the HashMap table, replace the value value of the element
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
e.value = value;
return;
}
}
// If there is no element with "key value equal to key" in the HashMap table, add the key value to the HashMap
createEntry(hash, key, value, i);
}
// Add all the elements in "m" to the HashMap.
// This method is called by the internal method of constructing HashMap.
private void putAllForCreate(Map<? extends K, ? extends V> m) {
// Add elements to the HashMap one by one using iterators
for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
Map.Entry<? extends K, ? extends V> e = i.next();
putForCreate(e.getKey(), e.getValue());
}
}
// Resize the HashMap. newCapacity is the adjusted unit
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// Create a new HashMap and add all the elements of the old HashMap to the new HashMap,
// Then, assign "new HashMap" to "old HashMap".
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
// Add all the elements in the HashMap to the newTable
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 = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
// Add all the elements of "m" to the HashMap
public void putAll(Map<? extends K, ? extends V> m) {
// Validity judgment
int numKeysToBeAdded = m.size();
if (numKeysToBeAdded == 0)
return;
// Calculate whether the capacity is sufficient,
// If "current actual capacity < required capacity", the capacity will be x2.
if (numKeysToBeAdded > threshold) {
int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
if (targetCapacity > MAXIMUM_CAPACITY)
targetCapacity = MAXIMUM_CAPACITY;
int newCapacity = table.length;
while (newCapacity < targetCapacity)
newCapacity <<= 1;
if (newCapacity > table.length)
resize(newCapacity);
}
// Add the elements in "m" to the HashMap one by one through the iterator.
for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
Map.Entry<? extends K, ? extends V> e = i.next();
put(e.getKey(), e.getValue());
}
}
// Delete the "key as key" element
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
// Delete the element with "key"
final Entry<K,V> removeEntryForKey(Object key) {
// Gets the hash value. If the key is null, the hash value is 0; Otherwise, call hash() for calculation
int hash = (key == null) ? 0 : hash(key.hashCode());
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
// Delete the element with "key" in the linked list
// The essence is "delete nodes in one-way linked list"
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
// Delete key value pair
final Entry<K,V> removeMapping(Object o) {
if (!(o instanceof Map.Entry))
return null;
Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
Object key = entry.getKey();
int hash = (key == null) ? 0 : hash(key.hashCode());
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
// Delete the "key value pair e" in the linked list
// The essence is "delete nodes in one-way linked list"
while (e != null) {
Entry<K,V> next = e.next;
if (e.hash == hash && e.equals(entry)) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
// Empty the HashMap and set all elements to null
public void clear() {
modCount++;
Entry[] tab = table;
for (int i = 0; i < tab.length; i++)
tab[i] = null;
size = 0;
}
// Whether to include elements with value
public boolean containsValue(Object value) {
// If "value is null", call containsNullValue() to find
if (value == null)
return containsNullValue();
// If "value is not null", check whether there is a node with value in HashMap.
Entry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (value.equals(e.value))
return true;
return false;
}
// Contains null values
private boolean containsNullValue() {
Entry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (e.value == null)
return true;
return false;
}
// Clone a HashMap and return the Object object
public Object clone() {
HashMap<K,V> result = null;
try {
result = (HashMap<K,V>)super.clone();
} catch (CloneNotSupportedException e) {
// assert false;
}
result.table = new Entry[table.length];
result.entrySet = null;
result.modCount = 0;
result.size = 0;
result.init();
// Call putAllForCreate() to add all elements to the HashMap
result.putAllForCreate(this);
return result;
}
// Entry is a one-way linked list.
// It is the linked list corresponding to "HashMap linked storage method".
// It implements map The entry interface implements the functions getKey(), getValue(), setValue(V value), equals(Object o), hashCode()
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
// Point to next node
Entry<K,V> next;
final int hash;
// Constructor.
// Input parameters include "Hashi value (h)", "key (k)", "value (v)", "next node (n)"
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// Judge whether two entries are equal
// If the "key" and "value" of two entries are equal, return true.
// Otherwise, false is returned
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
// Implement hashCode()
public final int hashCode() {
return (key==null ? 0 : key.hashCode()) ^
(value==null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
// When an element is added to the HashMap, recordAccess() is called.
// Nothing is done here
void recordAccess(HashMap<K,V> m) {
}
// When an element is deleted from the HashMap, recordRemoval() is called.
// Nothing is done here
void recordRemoval(HashMap<K,V> m) {
}
}
// Add an Entry. Insert "key value" into the specified location, and bucketIndex is the location index.
void addEntry(int hash, K key, V value, int bucketIndex) {
// Save the value of "bucketIndex" position to "e"
Entry<K,V> e = table[bucketIndex];
// Set the element at the "bucketIndex" position to "new Entry",
// Set "e" to "next node of new Entry"
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
// If the actual size of the HashMap is not less than the threshold, adjust the size of the HashMap
if (size++ >= threshold)
resize(2 * table.length);
}
// Create an Entry. Insert "key value" into the specified location, and bucketIndex is the location index.
// The difference between it and addEntry is:
// (01) addEntry() is generally used when adding an Entry may cause the "actual capacity of HashMap" to exceed the "threshold".
// For example, we create a new HashMap, and then continue to add elements to the HashMap through put();
// put() adds an Entry through addEntry().
// In this case, we don't know when the "actual capacity of HashMap" will exceed the "threshold";
// Therefore, you need to call addEntry()
// (02) createEntry() is generally used when adding an Entry will not cause the "actual capacity of HashMap" to exceed the "threshold".
// For example, we call the "with Map" constructor of HashMap, which adds all the elements of the Map to the HashMap;
// But before adding, we have calculated the "HashMap capacity and threshold". That is, it can be determined that "even if the Map
// All elements added to the HashMap will not exceed the HashMap threshold.
// At this point, just call createEntry().
void createEntry(int hash, K key, V value, int bucketIndex) {
// Save the value of "bucketIndex" position to "e"
Entry<K,V> e = table[bucketIndex];
// Set the element at the "bucketIndex" position to "new Entry",
// Set "e" to "next node of new Entry"
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
size++;
}
// HashIterator is an abstract parent class of HashMap iterator, which implements public functions.
// It contains three subclasses: key iterator, Value iterator and Entry iterator.
private abstract class HashIterator<E> implements Iterator<E> {
// Next element
Entry<K,V> next;
// expectedModCount is used to implement the fast fail mechanism.
int expectedModCount;
// Current index
int index;
// Current element
Entry<K,V> current;
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
// Point next to the first non null element in the table.
// Here, we use the initial value of index as 0, and traverse backward from 0 until we find a non null element and exit the loop.
while (index < t.length && (next = t[index++]) == null)
;
}
}
public final boolean hasNext() {
return next != null;
}
// Get next element
final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
// be careful!!!
// An Entry is a one-way linked list
// If the next node of the Entry is not empty, point to the next node;
// Otherwise, point next to the non null node of the next linked list (also the next Entry).
if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
// Delete current element
public void remove() {
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k);
expectedModCount = modCount;
}
}
// Iterator for value
private final class ValueIterator extends HashIterator<V> {
public V next() {
return nextEntry().value;
}
}
// Iterator for key
private final class KeyIterator extends HashIterator<K> {
public K next() {
return nextEntry().getKey();
}
}
// Iterator for Entry
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() {
return nextEntry();
}
}
// Returns a "key iterator"
Iterator<K> newKeyIterator() {
return new KeyIterator();
}
// Returns a "value iterator"
Iterator<V> newValueIterator() {
return new ValueIterator();
}
// Returns an entry iterator
Iterator<Map.Entry<K,V>> newEntryIterator() {
return new EntryIterator();
}
// The collection corresponding to the Entry of HashMap
private transient Set<Map.Entry<K,V>> entrySet = null;
// Returning a "set of keys" actually returns a "KeySet object"
public Set<K> keySet() {
Set<K> ks = keySet;
return (ks != null ? ks : (keySet = new KeySet()));
}
// Set corresponding to Key
// Key set inherits from AbstractSet, indicating that there are no duplicate keys in the set.
private final class KeySet extends AbstractSet<K> {
public Iterator<K> iterator() {
return newKeyIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
return HashMap.this.removeEntryForKey(o) != null;
}
public void clear() {
HashMap.this.clear();
}
}
// Return the "value set", which actually returns a Values object
public Collection<V> values() {
Collection<V> vs = values;
return (vs != null ? vs : (values = new Values()));
}
// "value set"
// Values inherits from AbstractCollection, which is different from "KeySet inherits from AbstractSet",
// Elements in Values can be repeated. Because different key s can point to the same value.
private final class Values extends AbstractCollection<V> {
public Iterator<V> iterator() {
return newValueIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
HashMap.this.clear();
}
}
// Return to "Entry collection of HashMap"
public Set<Map.Entry<K,V>> entrySet() {
return entrySet0();
}
// Return the "Entry set of HashMap", which actually returns an EntrySet object
private Set<Map.Entry<K,V>> entrySet0() {
Set<Map.Entry<K,V>> es = entrySet;
return es != null ? es : (entrySet = new EntrySet());
}
// Set corresponding to EntrySet
// EntrySet inherits from AbstractSet, indicating that there is no duplicate EntrySet in the set.
private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public Iterator<Map.Entry<K,V>> iterator() {
return newEntryIterator();
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<K,V> e = (Map.Entry<K,V>) o;
Entry<K,V> candidate = getEntry(e.getKey());
return candidate != null && candidate.equals(e);
}
public boolean remove(Object o) {
return removeMapping(o) != null;
}
public int size() {
return size;
}
public void clear() {
HashMap.this.clear();
}
}
// java.io.Serializable write function
// Write the "total capacity, actual capacity and all entries" of HashMap to the output stream
private void writeObject(java.io.ObjectOutputStream s)
throws IOException
{
Iterator<Map.Entry<K,V>> i =
(size > 0) ? entrySet0().iterator() : null;
// Write out the threshold, loadfactor, and any hidden stuff
s.defaultWriteObject();
// Write out number of buckets
s.writeInt(table.length);
// Write out size (number of Mappings)
s.writeInt(size);
// Write out keys and values (alternating)
if (i != null) {
while (i.hasNext()) {
Map.Entry<K,V> e = i.next();
s.writeObject(e.getKey());
s.writeObject(e.getValue());
}
}
}
private static final long serialVersionUID = 362498820763181265L;
// java.io.Serializable read function: read according to the write mode
// Read out the "total capacity, actual capacity and all entries" of HashMap in turn
private void readObject(java.io.ObjectInputStream s)
throws IOException, ClassNotFoundException
{
// Read in the threshold, loadfactor, and any hidden stuff
s.defaultReadObject();
// Read in number of buckets and allocate the bucket array;
int numBuckets = s.readInt();
table = new Entry[numBuckets];
init(); // Give subclass a chance to do its thing.
// Read in size (number of Mappings)
int size = s.readInt();
// Read the keys and values, and put the mappings in the HashMap
for (int i=0; i<size; i++) {
K key = (K) s.readObject();
V value = (V) s.readObject();
putForCreate(key, value);
}
}
// Return "total capacity of HashMap"
int capacity() { return table.length; }
// Return "load factor of HashMap"
float loadFactor() { return loadFactor; }
}explain:
Before introducing the HashMap code in detail, we need to understand that HashMap is a hash table, which solves hash conflicts through the "zipper method".
It should be added that there are two parameters that affect the performance of HashMap: initial capacity and load factor. The capacity is the number of buckets in the hash table. The initial capacity is only the capacity of the hash table when it is created. Load factor is a measure of how full a hash table can be before its capacity automatically increases. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, rehash the hash table (that is, rebuild the internal data structure), so that the hash table will have about twice the number of buckets.
Part 3.1 "zipper method" of HashMap
3.1.1 HashMap data storage array
transient Entry[] table;
The key values in the HashMap are stored in the Entry array.
3.1. 2. Data structure of data node Entry
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
// Point to next node
Entry<K,V> next;
final int hash;
// Constructor.
// Input parameters include "Hashi value (h)", "key (k)", "value (v)", "next node (n)"
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// Judge whether two entries are equal
// If the "key" and "value" of two entries are equal, return true.
// Otherwise, false is returned
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
// Implement hashCode()
public final int hashCode() {
return (key==null ? 0 : key.hashCode()) ^
(value==null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
// When an element is added to the HashMap, recordAccess() is called.
// Nothing is done here
void recordAccess(HashMap<K,V> m) {
}
// When an element is deleted from the HashMap, recordRemoval() is called.
// Nothing is done here
void recordRemoval(HashMap<K,V> m) {
}
}From this, we can see that Entry is actually a one-way linked list. This is why we say that HashMap solves hash conflicts through zipper method.
Entry implements map The entry interface implements the functions getKey(), getValue(), setValue(V value), equals(Object o), hashCode(). These are basic functions for reading / modifying key and value values.
Part 3.2 constructor of HashMap
HashMap includes four constructors
// Default constructor.
public HashMap() {
// Set load factor
this.loadFactor = DEFAULT_LOAD_FACTOR;
// Set the "HashMap threshold". When the amount of data stored in the HashMap reaches the threshold, you need to double the capacity of the HashMap.
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
// Create an Entry array to hold data
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
// Specifies the constructor for capacity size and load factor
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// The maximum capacity of HashMap can only be MAXIMUM_CAPACITY
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
// Set load factor
this.loadFactor = loadFactor;
// Set the "HashMap threshold". When the amount of data stored in the HashMap reaches the threshold, you need to double the capacity of the HashMap.
threshold = (int)(capacity * loadFactor);
// Create an Entry array to hold data
table = new Entry[capacity];
init();
}
// Specifies the constructor for capacity size
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// Constructor containing "sub Map"
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
// Add all elements in m to the HashMap one by one
putAllForCreate(m);
}Part 3.3 main external interfaces of HashMap
3.3.1 clear()
clear() is used to empty the HashMap. It is implemented by setting all elements to null.
public void clear() {
modCount++;
Entry[] tab = table;
for (int i = 0; i < tab.length; i++)
tab[i] = null;
size = 0;
}3.3.2 containsKey()
containsKey() is used to judge whether the HashMap contains a key.
public boolean containsKey(Object key) {
return getEntry(key) != null;
}containsKey() first obtains the Entry corresponding to the key through getEntry(key), and then determines whether the Entry is null.
The source code of getEntry() is as follows:
final Entry<K,V> getEntry(Object key) {
// Get hash value
// HashMap stores the element with "null key" in table[0]. If the "key is not null", call hash() to calculate the hash value
int hash = (key == null) ? 0 : hash(key.hashCode());
// Find the element with "key value equal to key" on the "linked list corresponding to the hash value"
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}The function of getEntry() is to return the key value pair of "key as key", which has been described in its implementation source code.
It should be emphasized here: HashMap places the elements with "null key" at position 0 of table, that is, table[0]; "Key is not null" is placed in the rest of the table!
3.3.3 containsValue()
containsValue() is used to judge whether HashMap contains elements with "value".
public boolean containsValue(Object value) {
// If "value is null", call containsNullValue() to find
if (value == null)
return containsNullValue();
// If "value is not null", check whether there is a node with value in HashMap.
Entry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (value.equals(e.value))
return true;
return false;
}From this, we can see that containsNullValue() is processed in two steps: first, if "value is null", call containsNullValue(). Second, if "value is not null", find out whether there is a node with value in the HashMap.
containsNullValue() is used to judge whether the HashMap contains elements with "null value".
private boolean containsNullValue() {
Entry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (e.value == null)
return true;
return false;
}3.3.4 entrySet(),values(),keySet()
The principles of the three are similar. Here, take entrySet() as an example.
The function of entrySet() is to return "the collection of all entries in HashMap", which is a collection. The implementation code is as follows:
// Return to "Entry collection of HashMap"
public Set<Map.Entry<K,V>> entrySet() {
return entrySet0();
}
// Return the "Entry set of HashMap", which actually returns an EntrySet object
private Set<Map.Entry<K,V>> entrySet0() {
Set<Map.Entry<K,V>> es = entrySet;
return es != null ? es : (entrySet = new EntrySet());
}
// Set corresponding to EntrySet
// EntrySet inherits from AbstractSet, indicating that there is no duplicate EntrySet in the set.
private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public Iterator<Map.Entry<K,V>> iterator() {
return newEntryIterator();
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<K,V> e = (Map.Entry<K,V>) o;
Entry<K,V> candidate = getEntry(e.getKey());
return candidate != null && candidate.equals(e);
}
public boolean remove(Object o) {
return removeMapping(o) != null;
}
public int size() {
return size;
}
public void clear() {
HashMap.this.clear();
}
}HashMap is a hash table realized by zipper method. It shows that HashMap includes many entries, and each Entry is essentially a one-way linked list. So how does HashMap traverse key value pairs one by one?
Let's take a look at how HashMap traverses through entrySet().
entrySet() is actually implemented through newentryitterer (). Let's look at its code:
// Returns an entry iterator
Iterator<Map.Entry<K,V>> newEntryIterator() {
return new EntryIterator();
}
// Iterator for Entry
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() {
return nextEntry();
}
}
// HashIterator is an abstract parent class of HashMap iterator, which implements public functions.
// It contains three subclasses: key iterator, Value iterator and Entry iterator.
private abstract class HashIterator<E> implements Iterator<E> {
// Next element
Entry<K,V> next;
// expectedModCount is used to implement the fast fail mechanism.
int expectedModCount;
// Current index
int index;
// Current element
Entry<K,V> current;
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
// Point next to the first non null element in the table.
// Here, we use the initial value of index as 0, and traverse backward from 0 until we find a non null element and exit the loop.
while (index < t.length && (next = t[index++]) == null)
;
}
}
public final boolean hasNext() {
return next != null;
}
// Get next element
final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
// be careful!!!
// An Entry is a one-way linked list
// If the next node of the Entry is not empty, point to the next node;
// Otherwise, point next to the non null node of the next linked list (also the next Entry).
if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
// Delete current element
public void remove() {
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k);
expectedModCount = modCount;
}
}When we traverse the HashMap through the next() method of Iterator obtained by entrySet(), we actually call nextEntry(). The implementation of nextEntry() traverses the Entry first (traversing from small to large according to the serial number of the Entry in the table); Then traverse each Entry (that is, each one-way linked list) one by one.
3.3.5 get()
get() is used to obtain the value corresponding to the key. Its implementation code is as follows:
public V get(Object key) {
if (key == null)
return getForNullKey();
// Get the hash value of the key
int hash = hash(key.hashCode());
// Find the element with "key value equal to key" on the "linked list corresponding to the hash value"
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}3.3.6 put()
The function of put() is to provide an external interface so that HashMap objects can add "key value" to HashMap through put().
public V put(K key, V value) {
// If "key is null", add the key value pair to table[0].
if (key == null)
return putForNullKey(value);
// If "key is not null", calculate the hash value of the key, and then add it to the linked list corresponding to the hash value.
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// If the key value pair corresponding to "this key" already exists, replace the old value with the new value. Then exit!
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// If the key value pair corresponding to "this key" does not exist, add "key value" to the table
modCount++;
addEntry(hash, key, value, i);
return null;
}If the key corresponding to the key value pair to be added to the HashMap already exists in the HashMap, find the key value pair; Then the new value replaces the old value and exits!
If the key corresponding to the key value pair to be added to the HashMap is not in the HashMap, add it to the linked list corresponding to the hash value and call addEntry().
Let's look at the code of addEntry():
void addEntry(int hash, K key, V value, int bucketIndex) {
// Save the value of "bucketIndex" position to "e"
Entry<K,V> e = table[bucketIndex];
// Set the element at the "bucketIndex" position to "new Entry",
// Set "e" to "next node of new Entry"
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
// If the actual size of the HashMap is not less than the threshold, adjust the size of the HashMap
if (size++ >= threshold)
resize(2 * table.length);
}addEntry() is used to add an Entry. Insert "key value" into the specified location, and bucketIndex is the location index.
When it comes to addEntry(), we have to say another function createEntry(). The code of createEntry() is as follows:
void createEntry(int hash, K key, V value, int bucketIndex) {
// Save the value of "bucketIndex" position to "e"
Entry<K,V> e = table[bucketIndex];
// Set the element at the "bucketIndex" position to "new Entry",
// Set "e" to "next node of new Entry"
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
size++;
}Their function is to add key and value to HashMap. Moreover, comparing the codes of addEntry() and createEntry(), we find that addEntry() has two more sentences:
if (size++ >= threshold)
resize(2 * table.length);What is the difference between them?
Reading the code, we can find that their use scenarios are different.
(01) addEntry() is generally used when adding an Entry may cause the "actual capacity of HashMap" to exceed the "threshold".
For example, we create a new HashMap, and then continue to add elements to the HashMap through put(); Put() adds an Entry through addEntry().
In this case, we don't know when the "actual capacity of HashMap" will exceed the "threshold";
Therefore, you need to call addEntry()
(02) createEntry() is generally used when {adding an Entry will not cause the "actual capacity of HashMap" to exceed the "threshold".
For example, we call the "with Map" constructor of HashMap, which adds all the elements of the Map to the HashMap;
But before adding, we have calculated the "HashMap capacity and threshold". That is, it can be determined that "even if all elements in the Map are added to the HashMap, the HashMap threshold will not be exceeded".
At this point, just call createEntry().
3.3.7 putAll()
putAll() is used to add all elements of "m" to HashMap. Its code is as follows:
public void putAll(Map<? extends K, ? extends V> m) {
// Validity judgment
int numKeysToBeAdded = m.size();
if (numKeysToBeAdded == 0)
return;
// Calculate whether the capacity is sufficient,
// If "current actual capacity < required capacity", the capacity will be x2.
if (numKeysToBeAdded > threshold) {
int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
if (targetCapacity > MAXIMUM_CAPACITY)
targetCapacity = MAXIMUM_CAPACITY;
int newCapacity = table.length;
while (newCapacity < targetCapacity)
newCapacity <<= 1;
if (newCapacity > table.length)
resize(newCapacity);
}
// Add the elements in "m" to the HashMap one by one through the iterator.
for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
Map.Entry<? extends K, ? extends V> e = i.next();
put(e.getKey(), e.getValue());
}
}3.3.8 remove()
The function of remove() is to delete the "key as key" element
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
// Delete the element with "key"
final Entry<K,V> removeEntryForKey(Object key) {
// Gets the hash value. If the key is null, the hash value is 0; Otherwise, call hash() for calculation
int hash = (key == null) ? 0 : hash(key.hashCode());
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
// Delete the element with "key" in the linked list
// The essence is "delete nodes in one-way linked list"
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}Part 3.4 Cloneable interface implemented by HashMap
HashMap implements the clonable interface, that is, the clone() method.
The clone() method simply clones a HashMap object and returns it.
// Clone a HashMap and return the Object object
public Object clone() {
HashMap<K,V> result = null;
try {
result = (HashMap<K,V>)super.clone();
} catch (CloneNotSupportedException e) {
// assert false;
}
result.table = new Entry[table.length];
result.entrySet = null;
result.modCount = 0;
result.size = 0;
result.init();
// Call putAllForCreate() to add all elements to the HashMap
result.putAllForCreate(this);
return result;
}Part 3.5 Serializable interface implemented by HashMap
HashMap implements Java io. Serializable, which realizes the functions of serial reading and writing respectively.
The serial write function is writeObject(), which is used to write the "total capacity, actual capacity and all entries" of HashMap to the output stream.
The serial read function is readObject(), which is used to read out the "total capacity, actual capacity and all entries" of HashMap in turn
// java.io.Serializable write function
// Write the "total capacity, actual capacity and all entries" of HashMap to the output stream
private void writeObject(java.io.ObjectOutputStream s)
throws IOException
{
Iterator<Map.Entry<K,V>> i =
(size > 0) ? entrySet0().iterator() : null;
// Write out the threshold, loadfactor, and any hidden stuff
s.defaultWriteObject();
// Write out number of buckets
s.writeInt(table.length);
// Write out size (number of Mappings)
s.writeInt(size);
// Write out keys and values (alternating)
if (i != null) {
while (i.hasNext()) {
Map.Entry<K,V> e = i.next();
s.writeObject(e.getKey());
s.writeObject(e.getValue());
}
}
}
// java.io.Serializable read function: read according to the write mode
// Read out the "total capacity, actual capacity and all entries" of HashMap in turn
private void readObject(java.io.ObjectInputStream s)
throws IOException, ClassNotFoundException
{
// Read in the threshold, loadfactor, and any hidden stuff
s.defaultReadObject();
// Read in number of buckets and allocate the bucket array;
int numBuckets = s.readInt();
table = new Entry[numBuckets];
init(); // Give subclass a chance to do its thing.
// Read in size (number of Mappings)
int size = s.readInt();
// Read the keys and values, and put the mappings in the HashMap
for (int i=0; i<size; i++) {
K key = (K) s.readObject();
V value = (V) s.readObject();
putForCreate(key, value);
}
}Part 4 HashMap traversal method
4.1 traversing key value pairs of HashMap
Step 1: get the Set of "key value pairs" of HashMap according to entrySet().
Step 2: traverse the set obtained in the "first step" through the Iterator iterator.
// Suppose the map is a HashMap object
// The key in the map is of String type and the value is of Integer type
Integer integ = null;
Iterator iter = map.entrySet().iterator();
while(iter.hasNext()) {
Map.Entry entry = (Map.Entry)iter.next();
// Get key
key = (String)entry.getKey();
// Get value
integ = (Integer)entry.getValue();
}4.2 key to traverse HashMap
Step 1: get the Set of "keys" of HashMap according to keySet().
Step 2: traverse the set obtained in the "first step" through the Iterator iterator.
// Suppose the map is a HashMap object
// The key in the map is of String type and the value is of Integer type
String key = null;
Integer integ = null;
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
// Get key
key = (String)iter.next();
// Get value according to key
integ = (Integer)map.get(key);
}4.3 traversing HashMap values
Step 1: get the collection of "values" of HashMap according to value().
Step 2: traverse the set obtained in the "first step" through the Iterator iterator.
// Suppose the map is a HashMap object
// The key in the map is of String type and the value is of Integer type
Integer value = null;
Collection c = map.values();
Iterator iter= c.iterator();
while (iter.hasNext()) {
value = (Integer)iter.next();
}The traversal test procedure is as follows:
import java.util.Map;
import java.util.Random;
import java.util.Iterator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;
import java.util.Collection;
/*
* @desc Traverse the test program of HashMap.
* (01) Use entrySet() to traverse key and value. Refer to the implementation function:
* iteratorHashMapByEntryset()
* (02) Use keySet() to traverse key and value. Refer to the implementation function:
* iteratorHashMapByKeyset()
* (03) Traverse value through values() and refer to the implementation function:
* iteratorHashMapJustValues()
*
* @author skywang
*/
public class HashMapIteratorTest {
public static void main(String[] args) {
int val = 0;
String key = null;
Integer value = null;
Random r = new Random();
HashMap map = new HashMap();
for (int i=0; i<12; i++) {
// Randomly obtain a number between [0100]
val = r.nextInt(100);
key = String.valueOf(val);
value = r.nextInt(5);
// Add to HashMap
map.put(key, value);
System.out.println(" key:"+key+" value:"+value);
}
// Traverse the key value of HashMap through entrySet()
iteratorHashMapByEntryset(map) ;
// Traverse the key value of HashMap through keySet()
iteratorHashMapByKeyset(map) ;
// Simply traverse the value of HashMap
iteratorHashMapJustValues(map);
}
/*
* Traverse HashMap through entry set
* efficient!
*/
private static void iteratorHashMapByEntryset(HashMap map) {
if (map == null)
return ;
System.out.println("\niterator HashMap By entryset");
String key = null;
Integer integ = null;
Iterator iter = map.entrySet().iterator();
while(iter.hasNext()) {
Map.Entry entry = (Map.Entry)iter.next();
key = (String)entry.getKey();
integ = (Integer)entry.getValue();
System.out.println(key+" -- "+integ.intValue());
}
}
/*
* Traverse HashMap through keyset
* Low efficiency!
*/
private static void iteratorHashMapByKeyset(HashMap map) {
if (map == null)
return ;
System.out.println("\niterator HashMap By keyset");
String key = null;
Integer integ = null;
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
key = (String)iter.next();
integ = (Integer)map.get(key);
System.out.println(key+" -- "+integ.intValue());
}
}
/*
* Traverse the values of HashMap
*/
private static void iteratorHashMapJustValues(HashMap map) {
if (map == null)
return ;
Collection c = map.values();
Iterator iter= c.iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}
}
}Part 5 HashMap example
Let's learn how to use HashMap through an example
import java.util.Map;
import java.util.Random;
import java.util.Iterator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;
import java.util.Collection;
/*
* @desc HashMap Test procedure
*
* @author skywang
*/
public class HashMapTest {
public static void main(String[] args) {
testHashMapAPIs();
}
private static void testHashMapAPIs() {
// Initialize random seed
Random r = new Random();
// New HashMap
HashMap map = new HashMap();
// Add operation
map.put("one", r.nextInt(10));
map.put("two", r.nextInt(10));
map.put("three", r.nextInt(10));
// Print out map
System.out.println("map:"+map );
// Traverse key value through Iterator
Iterator iter = map.entrySet().iterator();
while(iter.hasNext()) {
Map.Entry entry = (Map.Entry)iter.next();
System.out.println("next : "+ entry.getKey() +" - "+entry.getValue());
}
// Number of key value pairs in HashMap
System.out.println("size:"+map.size());
// containsKey(Object key): whether the key is included
System.out.println("contains key two : "+map.containsKey("two"));
System.out.println("contains key five : "+map.containsKey("five"));
// containsValue(Object value): whether to include value
System.out.println("contains value 0 : "+map.containsValue(new Integer(0)));
// remove(Object key): deletes the key value pair corresponding to the key
map.remove("three");
System.out.println("map:"+map );
// clear(): clear the HashMap
map.clear();
// Isempty(): is HashMap empty
System.out.println((map.isEmpty()?"map is empty":"map is not empty") );
}
}(a) operation result:
map:{two=7, one=9, three=6}
next : two - 7
next : one - 9
next : three - 6
size:3
contains key two : true
contains key five : false
contains value 0 : false
map:{two=7, one=9}
map is empty