How is HashMap structured internally and how does it work?

HashMap in Java is implemented based on an array of buckets, each of which contains a linked list or a tree (TreeNode) of elements with the same hash code. When adding an element, the hash code of the key is computed, which is used to determine the bucket index. If the bucket is empty, the element is placed directly there. If not, a search is performed through the list or tree to update the value or add a new node.

Main points of operation:

• Collisions are handled using chaining (linked list) or a tree (if there are many elements) to speed up search.
• When a certain array size threshold is reached, rehashing occurs with redistribution of elements.
• In Java 8 and above, long chains are converted into red-black trees to improve search performance.

Example of simplified insertion logic:

int hash = key.hashCode();
int index = (hash & 0x7fffffff) % table.length;
Node<K,V> node = table[index];
// if node == null, insert new
// otherwise, search in chain or tree, update or add

Thus, HashMap provides amortized access time of O(1) with good hash distribution.