Can you explain how the HashMap data structure is implemented and how it works internally?

HashMap is a data structure that stores key-value pairs and provides fast access to values by key. Internally, it is implemented as an array of buckets, each of which can contain one or more pairs.

Working principle:

1. The key is passed through a hash function, which calculates the bucket index.
2. The value is placed in the bucket at this index.
3. If there are already elements in the bucket (collision), they are stored as a linked list or tree.
4. When searching for a key, the index is recalculated, and then the elements in the bucket are iterated for an exact match of the key.

In Python, dictionaries (dict) are implemented similarly but with optimizations for fast access and dynamic resizing.

Example (simplified):

class SimpleHashMap:
    def __init__(self, size=10):
        self.size = size
        self.buckets = [[] for _ in range(size)]

    def _hash(self, key):
        return hash(key) % self.size

    def put(self, key, value):
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    def get(self, key):
        index = self._hash(key)
        bucket = self.buckets[index]
        for k, v in bucket:
            if k == key:
                return v
        return None

This demonstrates the basic mechanism of hashing and collision resolution.