1. Structure of a HashMap
Bucket Array:
- The primary data structure is an array of buckets, where each bucket can hold multiple key-value pairs (nodes). The position of these buckets is determined by hashing the keys.
A bucket can be:
- Empty
- Contain a single key-value pair
- Contain multiple key-value pairs (collision), either as a Linked List or a Red-Black Tree.
Node Structure:
Each key-value pair is represented as a Node<K,V> object, defined internally like this:
static class Node<K, V> {
final int hash; // Precomputed hash code of the key
final K key; // The key object
V value; // The value associated with the key
Node<K, V> next; // Reference to the next node in the same bucket
}static class Entry<K,V> implements Map.Entry<K,V>
{
final K key;
V value;
Entry<K,V> next;
int hash;
}As you see, this inner class has four fields. key, value, next and hash.
