Comment implémenter Python dict

L'objet dict en Python indique qu'il s'agit d'un type de données Python primitif, qui est stocké sous forme de paires clé-valeur. Son nom chinois est traduit dans un dictionnaire. Comme son nom l'indique, il est très efficace à trouver. la valeur correspondante via le nom de la clé. La complexité temporelle est O(1) au niveau constant.

dicter l'implémentation sous-jacente (recommandé apprentissage : Tutoriel vidéo Python)

Dans Python2, la couche inférieure de dict est implémentée par Hash Table et la méthode d'adresse ouverte est utilisée pour résoudre les conflits.

Donc la complexité temporelle de sa recherche sera O(1).

Le principe de mise en œuvre de l'opération de Dict (y compris l'insertion, la suppression et le pool de tampons, etc.)

Présentez d'abord : la stratégie de recherche d'éléments de l'objet PyDictObject :

Il existe deux stratégies de recherche, à savoir lookdict et lookdict_string. Lookdict_string est la forme spéciale de lookdict lors de la recherche de PyStringObject. Ensuite, la logique principale de la stratégie de recherche générale. lookdict est :

(1) Rechercher la première entrée :

a) Obtenir l'index de l'entrée en fonction de la valeur de hachage

b) Si l'entrée est dans le format inutilisé état, la recherche se termine ; si la clé pointée par l'entrée est la même que la clé recherchée. Si les clés sont les mêmes, la recherche est réussie

c) Si l'entrée actuelle est dans l'état factice, set freeslot (le freeslot ici peut être renvoyé comme prochaine adresse immédiatement disponible pour stocker l'entrée)

d) Vérifiez l'entrée active si la valeur pointée par sa clé est la même que la valeur recherchée, la valeur recherchée. la recherche est réussie

(2) Parcourir les éléments de la chaîne de détection restante :

a )Selon la fonction de détection utilisée, obtenir la prochaine entrée à vérifier sur la chaîne de détection

b) Vérifiez une entrée inutilisée, indiquant que la recherche a échoué :

Si l'emplacement libre n'est pas vide, renvoyez l'emplacement libre sinon renvoyez l'entrée inutilisée

c) Vérifiez si la clé de l'entrée est la même que la référence de la clé recherchée. Si elles sont identiques, la recherche est réussie et renvoie l'entrée

d) Vérifiez l'entrée si la valeur de la clé est la même que la valeur de la clé recherchée. S'ils sont identiques, la recherche est réussie et l'entrée

est renvoyée. e) Pendant le processus de traversée, si une entrée dans un état factice est trouvée et que l'emplacement libre n'est pas défini, définissez l'emplacement libre

.

Ce qui suit est : la stratégie d'insertion et de suppression d'éléments de l'objet PyDictObject :

Vous devez d'abord utiliser la stratégie de recherche Si la recherche réussit, la valeur sera remplacée directement si la recherche. échoue, l'entrée dans un état inutilisé ou factice sera renvoyée. Définissez les valeurs de clé, de valeur et de hachage, et ajustez la taille de ma_table en fonction des éléments actuellement insérés (l'ajustement est basé sur le taux de chargement, qui est ajusté en fonction de). si elle est supérieure à 2/3); la suppression est également similaire, calculez d'abord la valeur de hachage, puis recherchez l'entrée correspondante, la recherche est réussie, supprimez les éléments conservés dans l'entrée et modifiez l'entrée de l'état Actif à l'état factice

Dans le processus d'implémentation de PyDictObject, le pool de tampons sera utilisé lorsque l'objet PyDictObject est détruit, il commence à accepter les objets PyDictObject mis en mémoire tampon. le pool de tampons peut accepter est de 80. Lors de la création d'un nouvel objet PyDictObject, s'il y en a un dans le pool de tampons, il peut être retiré directement du pool de tampons. Utilisez

Pour plus d'articles techniques liés à Python, veuillez visiter la colonne Tutoriel Python pour apprendre !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!