Welke datastructuur ligt ten grondslag aan dict in Python? Hoe worden botsingen opgelost?

In Python is dict gebaseerd op een hashtabel met open adressering en het gebruik van de open adresseringsmethode met dubbele hashing (open addressing with probing).

Belangrijke punten:

• Sleutels worden gehasht om een index in de array te krijgen.
• Bij een botsing (wanneer twee sleutels dezelfde index hebben) wordt de probing-methode gebruikt, waarbij de volgende vrije cel wordt gezocht volgens een bepaald algoritme.
• Vanaf Python 3.6+ wordt een geordende implementatie van de woordenboek gebruikt, waarbij de invoerorde wordt behouden.

Een voorbeeld van het oplossen van botsingen is lineair probing of dubbele hashing, maar in CPython wordt een algoritme met een variabele stapgrootte gebruikt om clustering te verminderen.

Dit zorgt voor efficiënte toegang, invoeging en verwijdering van elementen.