Aká dátová štruktúra je základom dict v Pythone? Ako sa riešia kolízie?

V Pythone je dict implementiran na osnovi hashtable s otvorenim adresiranjem i korištenjem metode otvorenog adresiranja s dvostrukim hashiranjem (open addressing with probing).

Glavne točke:

• Ključevi se hash-juju da dobiju indeks u nizu.
• Pri koliziji (kada dva ključa imaju isti indeks), koristi se metoda sondiranja (probing), pri čemu se traži sledeće slobodno mesto prema određenem algoritmu.
• Od Pythona 3.6+ se uporablja ugradbena implementacija slovarja, ki ohranja vrstni red vstavljanja.

Primer rešitve kolizij je linearno sondiranje ali dvojno hashiranje, vendar v CPython-u uporablja algoritem s spremenljivim korakom za sondiranje, da zmanjša klasterizacijo.

To zagotavlja učinkovit dostop, vstavljanje in brisanje elementov.