Dictionnaires et Hashtables complexité de l'espace

Question

J'ai une certaine confusion sur les dictionnaires et les tables de hachage que je voulais clarifier. Supposons que j'ai le dictionnaire actuel et la sortie actuelle des hachages de l'exécution actuelle de python.

Dict = dict() 
print(hash('a')) 
print(hash('b')) 
print(hash('c')) 
Dict['a'] = 1 
Dict['b'] = 2 
Dict['c'] = 3 
print(Dict) 

a la sortie de

1714333803 
1519074822 
1245896149 
{'a': 1, 'c': 3, 'b': 2} 

donc à ma connaissance une table de hachage est tout simplement un tableau où le hachage est l'index de la table de hachage. Par exemple, 'a' avait un hash de 1714333803, donc mon index de hashtable 1714333803 a une valeur de 'a'. Donc, je suis confus combien d'index une hashtable a et comment la fonction de hachage produit la réponse? Utilise-t-il le module et a-t-il une gamme fixe d'index? Parce que l'impression donnée du dictionnaire génère {'a': 1, 'c': 3, 'b': 2}, mais est-il correct de supposer que, même si cela sort, le dictionnaire est en fait un tableau d'au moins 1714333803 index, parce que cela semble ridiculement exagéré de contenir 3 éléments et de ne pas mentionner combien d'un le gaspillage de l'espace c'est. Aussi pour la hashtable, qu'est-ce qui dans les index n'a aucune valeur, null?

Answer 1

La taille réelle du dict dépend de l'implémentation, mais dans votre cas, c'est probablement 8. Alors, comment cela fonctionne-t-il?

Le principe de fonctionnement d'un dict (ou d'une table de hachage en général) consiste à calculer un hachage numérique pour chaque clé. Dans votre cas, c'est hash("a") == 1714333803, par exemple. Maintenant, le hachage n'est pas utilisé directement comme index. Au lieu de cela, il est mappé à la taille du dictionnaire.

Une méthode simple pour ce faire est modulo (%). Disons que votre dict a une taille de 8. Puis hash("a") % 8 == 1714333803 % 8 == 3. Donc, votre article est en réalité à la 4ème position. Aucun élément ne peut avoir un index en dehors du tableau.

Il y a des choses plus complexes ici, comme les collisions de hachage. Par exemple, si un autre élément a un hachage 98499, ce également correspond à 3. Il existe des stratégies de résolution de collision qui choisissent un index différent dans ce cas.

Alors, pourquoi votre dict de taille 8? Parce que c'est le default size in python. Une fois que votre dict est trop petit, il doit être redimensionné. Contrairement aux tableaux, ceci est fait avant que le dict soit réellement plein - à savoir, au two thirds filling. Ceci est fait pour réduire les collisions de hachage - si votre dict est plein à 99%, une collision est pratiquement garantie. Pour un dict de taille 8, vous devez entrer 5-6 éléments avant de le redimensionner, à savoir doubles its capacity à 16.