Quelle structure des données est adaptée à cette situation?
https://stackoverflow.com/questions/1306385
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je suis en train de décider à utiliser pour structure de données stocker des paires clé-valeur lorsque les caractéristiques ne sont nécessaires
- insertion
- recherche
Plus précisément, je ne dois pas être en mesure de supprimer des paires, ou itérer clés / valeurs / paires.
Les touches sont tuples entiers, les valeurs sont des pointeurs (références, peu importe). Je ne stocker quelques millions de paires réparties sur des objets (beaucoup).
Actuellement, j'envisage d'utiliser soit
- une table de hachage
- un arbre kd
- un b-arbre
Je penche vers la table de hachage (pour l'insertion O(1) / temps de recherche), mais je voulais confirmer mes inclinations.
Quelle structure (de ceux ci-dessus ou autre) recommanderiez-vous et pourquoi? Si vous recommanderiez une table de hachage, dois-je créer une table séparée pour chaque objet, ou tout simplement créer une seule table et utiliser l'identifiant de l'objet dans le cadre du tuple clé?
La solution
A Hashtable sera le meilleur choix ici que toutes les opérations qui comptent pour vous êtes O (1) (et en tant que tel, vous ne devriez pas avoir à vous soucier de créer plusieurs tables de hachage).
Autres conseils
Je suis un grand fan de tables de hachage, car ils sont faciles et il y a des implémentations disponibles pour à peu près toutes les grandes langues là-bas. Le joint (1) d'insertion / recherche est une caractéristique particulièrement bonne.
Vous devriez probablement utiliser une seule table, pour sauver la mémoire. Les tables de hachage sont notoirement inefficaces sage mémoire, et en utilisant une seule table contribuerait à minimiser cela.
tables de hachage seraient usefull ici et je ne vois aucune raison d'avoir plus d'une table.
La plupart des arbres ont un O (n ln n) rechercher du temps, mais hashtables ont un O (1) lookup temps, de sorte que est celui que vous voulez utiliser. Il est également très fréquent, et souvent la mise en œuvre est hautement optimisé pour démarrer.
