Je souhaite créer une grande (environ 300 000 entrées) Liste des objets auto-définis de la classe médicament .
Chaque médicament a une carte d'identité et je veux pouvoir rechercher les médicaments dans le temps logarithmique via cet identifiant.
Quel type de liste dois-je utiliser?
Comment puis-je déclarer qu'il devrait être consultable via l'ID?
7 Réponses :
n'utiliseriez pas Treemap au lieu de la liste à l'aide de l'identifiant comme clé?
FYI, la raison pour laquelle j'ai suggéré Treemap est parce que Treemap est garantie de fonctionner contient, d'obtenir et de mettre en place O (log n)
Si vous n'avez pas besoin de commander les clés, cela est inutile
L'exigence était pour la recherche logarithmique, alors je pense que cela doit être.
L'avantage de Treemap est que vous pouvez récupérer les éléments dans l'ordre par clé. Cela n'a pas été considéré comme une exigence dans la question initiale, bien que cela ne prouve pas que ce n'est pas une exigence. Mais l'exigence d'une recherche logarithmique est remplie par un hashmap. Vous n'avez pas besoin de Treemap si c'est le seul problème.
Depuis la liste des utilisateurs initialement suggéré, il semblerait que l'ordre est nécessaire. Mais vrai, il n'a pas été explicitement déclaré.
Les différentes implémentations de l'interface de la carte doivent faire ce que vous voulez.
N'oubliez pas de remplacer la méthode HashCode () de votre classe de médicament si vous envisagez d'utiliser un hashmap.
Pas que je ne te crois pas, mais me rappelle pourquoi HashCode () doit être remplacé? La valeur par défaut n'est-elle pas assez bonne?
Vous n'avez besoin que d'implémenter hashcode et est égal à uniquement si vous souhaitez utiliser votre classe comme clé d'un carte ou si vous souhaitez le mettre dans un définir . Si vous souhaitez simplement l'utiliser comme valeur d'un mapper , vous n'avez pas besoin de les implémenter. Aussi: si vous implémentez égale () , alors vous doit mettre en oeuvre Implément hashcode () aussi.
Avoir un contrôle grainé fin sur le HashCode, vous pouvez garantir que les entrées de la carte sont uniformément réparties entre les godets. Le pire des cas est lorsque toutes les entrées atterrissent dans le même seau et la complexité de la recherche devient O (n).
La mise en œuvre par défaut prend simplement l'adresse en mémoire pour être le code de hachage. Si vous utilisez votre objet de médicament comme clé, vous ne pouvez pas faire ce qui suit: mymap.put (nouveau médicament ("tout ce qui est"), 23.42); mymap.get (nouveau médicament ("tout")); Parce que les deux instances de drogue ont un critère différent et ce dernier retournera null. Voir Java.sun.com/javase /6/docs/api/java/lang/Object.html#hashcod e () pour plus de détails.
En supposant que le type d'identifiant est une chaîne, et que c'est la clé, il n'y a pas besoin (et aucun moyen) de remplacer le égal (objet) et hashcode () Méthodes.
Re Malax: mais gardez à l'esprit que cela ne s'applique que si vous utilisez votre objet comme clé, comme les notes de Joachim. Mais normalement, la clé n'est pas l'objet cible lui-même, mais un identifiant. Dans ce cas, Christian dit qu'il a un "ID de drogue". Si cela peut être stocké dans une chaîne ou un entier, comme il semble probable que ces classes ont déjà généralement de bonnes fonctions de hashcode.
@Malax: La mise en œuvre par défaut pas prend simplement l'adresse en mémoire. Il prend l'IdentityHashCode (tel que défini par System.IDidityHashCode () ) qui peut basé sur la position en mémoire. Pensez à une JVM 64 bits: Comment une valeur de 32 bits est-elle être la position en mémoire dans ce cas?
@ Joachim, vous avez absolument raison, j'ai omis toute la partie identityhashscode dans mon commentaire pour le garder simple. Mais tu as raison. :-) @jay: "Si vous utilisez votre objet de médicament comme une clé" est exactement ce que j'ai écrit ;-)
Si la recherche d'une clé est importante pour vous, vous devez probablement utiliser une carte et non une liste. De Java Collections Trail :
la carte à usage général Les implémentations sont HASHMAP, Treemap et LinkedHashMap. Si tu as besoin Opérations de type MAPA ou clés Itération de la collecte-vue, utilisation Treemap; Si vous voulez une vitesse maximale et Ne vous souciez pas de l'ordre d'itération, utilisez Hashmap; Si vous voulez près de HASHMAP Performance et insertion-commande Itération, utilisez LinkedHashMap.
En raison du nombre élevé d'entrées, vous pourriez envisager d'utiliser une base de données au lieu de tout tenir dans la mémoire.
Si vous voulez toujours le garder en mémoire, vous pouvez regarder des arbres B.
Vous pouvez utiliser n'importe quelle liste, et tant qu'il est trié, vous pouvez utiliser un Recherche binaire . Mais j'utiliserais une carte qui recherche dans O (1).
List<Drug> drugList; <--- List of all drugs
Drug drugToSearchFor; <---- The drug that you want to search for, containing the id
// Sort before search
Collections.sort(drugList);
int index = Collections.binarySearch(drugList, drugToSearchFor);
if (index >= 0) {
return true;
} else {
return false;
}
Je sais que je suis assez redondant avec cette déclaration, mais comme tout le monde l'a dit n'est pas exactement le cas pour une carte?
Quelle est la gamme des identifiants?
Toute chance de les mettre dans une DB et de le laisser faire le travail avec l'aide de SQL / JDBC? Cela va sans aucun doute être plus rapide et plus efficace.
@Balusque uniquement si les données ne changent pas trop. S'il doit tout mettre à jour à intervalles de courte distance et que la persistance n'est pas nécessaire, une DB n'aura pas beaucoup de sens. Mais mes premières pensées dirigent vers une dB aussi.