J'essaye de créer une classe qui implémente l'interface de carte. J'écris donc du code qui va vérifier si l'objet appelant est vide ou non. Cependant, je suis un peu confus quant à la structure de données que je devrais utiliser en interne. À l'heure actuelle, j'utilise une table de hachage. Merci d'avanceJava: structure de données interne dans la carte
De Wikipedia,
tableaux Associatif sont généralement utilisés lorsque la recherche est l'opération la plus fréquente . Pour cette raison, les mises en œuvre sont généralement conçus pour permettre consultation rapide, au détriment d'insertion plus lente et une empreinte de stockage plus grande que d'autres données structures (telles que l'association listes ).
représentations efficaces:
Il existe deux principales données efficaces structures utilisées pour représenter tableaux associatifs, la table de hachage et l'arbre de recherche binaire auto-équilibrage (comme un arbre rouge-noir ou un AVL arbre). Sauter les listes sont également une alternative , bien que relativement nouveau et pas aussi largement utilisé. B-arbres (et variantes) peuvent également être utilisés, et sont couramment utilisé lorsque le tableau associatif est trop grand pour résider entièrement en mémoire, par exemple dans une base de données simple . avantages et inconvénients suivants:
performances de fonctionnement Asymptotic: tables de hachage ont recherche plus rapide moyen et le temps d'insertion, O (1), par rapport à un Θ de l'arbre binaire équilibré (log n), alors que arbres arborescents ont plus rapide recherche de cas et le temps d'insertion, O (log n) par rapport à Θ (n). Sauter listes ont O (n) le plus pessimiste et O (log n) temps d'opération en moyenne, mais avec moins d'insertion et de suppression en tête que les arbres binaires équilibrés .
préservation de commande: arbres binaires équilibré et sauter les listes conservent commande - permettant un à efficacement itérer les clés pour ou localiser efficacement une association dont la clé est plus proche d'une valeur donnée. Les tables de hachage ne conservent pas la commande et ne peuvent donc pas exécuter ces opérations aussi efficacement (elles nécessitent que les données soient triées dans une étape séparée ).
requêtes Range: arbres binaires équilibrés peuvent être facilement adaptés à affecter efficacement une valeur unique à une large gamme ordonnée de clés, ou à compter le nombre de clés dans une gamme ordonnée. (Avec n éléments dans le tableau et en effectuant l'opération sur une plage contiguë de m, un arbre binaire équilibré prendra O (log (n) + m) temps alors qu'une table de hachage nécessitera Θ (n) temps qu'il doit rechercher l'ensemble de la table )
comportement Répartition:. tables de hachage avec magasin adressage ouvert toutes les données dans un grand bloc contigu de mémoire qui est réaffecté rarement, alors que les allocations d'arbres remplissent de nombreuses petites , allocations fréquentes. Comme une table de hachage résultat peut être difficile à allouer dans un tas fragmenté, et inversement arbres peuvent provoquer la fragmentation tas . Les arbres sont également plus vulnérables aux inefficacités dans allocateurs.
Compacité: Les tables de hachage peuvent avoir un stockage plus compact pour les types de petite valeur, en particulier lorsque les valeurs sont bits.
Persistance: Il existe des versions persistantes simples des arbres binaires équilibrés, qui sont particulièrement importants dans les langages fonctionnels.
Soutenir les nouveaux types de clés: Construire une table de hachage nécessite une fonction de hachage raisonnable pour le type de clé qui peut être difficile à bien écrire, tandis que arbres binaires équilibrés et les listes de saut ne nécessitent un ordre total sur la touches.
implémentations Parfois simples une structure de données ou l'autre ont inconvénients qui peuvent être surmontés par une meilleure conception . Par exemple:
tables de hachage qui utilisent des données non vérifiées comme clés peuvent être vulnérables aux attaques par déni de service où un utilisateur fournit des données non fiables destinées pour générer un grand nombre de collisions . Cela peut être surmonté par en choisissant des fonctions de hachage au hasard à partir de une famille universelle, ou en hachant entrée non sécurisée avec une fonction de hachage cryptographique avant l'insertion. Les arbres équilibrés simples gaspillent de l'espace sur les pointeurs et attribuent métadonnées; ces problèmes peuvent être atténués en stockant plusieurs éléments dans chaque nœud et en utilisant les pools de mémoire .
Outre la table elle-même, vous pouvez également gérer une variable membre entière pour suivre la taille de la collection, en l'incrémentant chaque fois qu'un nouveau mappage est placé et en décrémentant à chaque suppression. De cette façon, vous pouvez simplifier les size et isEmpty méthodes d'interface:
public int size() {
return this.size;
}
public boolean isEmpty() {
return this.size == 0;
}
J'ai essayé différentes méthodes, mais a fini par étendre une structure de données qui lui-même était si forte qu'il fallait pas de compétences de codage pour elle. J'ai donc décidé d'utiliser des tableaux de chaînes normales (2) à partir d'une structure similaire à une carte de hachage virtuelle qui s'élargirait au fur et à mesure que le besoin d'espace augmenterait.
Voici le lien vers le code complet.
http://code.google.com/p/rohan-oopconcept-assignment/source/browse/trunk/src/EmployeeMap.java