Existe-t-il une structure de données pour ce type de liste / carte?

22

Il y a peut-être un nom pour ce que je veux, mais je n'en suis pas conscient. J'ai besoin de quelque chose de similaire à un LinkedHashMapen Java, mais où il renvoie la valeur «précédente» s'il n'y a pas de valeur à la clé spécifiée.

Autrement dit, j'ai une liste d'objets stockés par une clé entière (qui est en unités de temps dans mon cas):

; key->value
10->A
15->B
20->C

Donc, si je demandais une valeur pour la clé 0-9, elle reviendrait null. La partie spéciale est que si je demandais quelque chose 10 <= i <= 14 cela retournerait A. Ou, pour i> = 20, cela retournerait C.

Existe-t-il une structure de données pour cela?

java data-structures Entaille
la source
Je ne sais pas s'il y en a un implémenté mais vous pourriez probablement étendre l'existant pour le faire. Que cela atteindra vos objectifs de performance ou non sans une réécriture, je ne sais pas ...
Rig
1
+1 pour la grande question. La plupart des gens avec trois représentants à faible chiffre posent le type de question "s'il vous plaît, faites mes devoirs". Pas le cas ici.
Tulains Córdova du

Réponses:

33

Vous recherchez une carte navigable . Il s'agit d'un sous-type de SortedMap qui a également certaines fonctions disponibles en plus de la nature de la carte en cours de tri. Notez que la carte navigable "est destinée à remplacer l'interface SortedMap." ( Améliorations de Java SE 6 Collections Framework ). Tout ce qui met en œuvre actuellement des SortedMapoutils NavigableMapet cela est susceptible de rester vrai.

En particulier, la méthode floorKey(K key)qui "renvoie la plus grande clé inférieure ou égale à la clé donnée, ou null s'il n'y a pas une telle clé.

Ce n'est là qu'une des nombreuses méthodes qui vous permettent d'obtenir des clés ou des sous-plans spécifiques de la carte.

  • plafond / plancher (l'entrée qui est supérieure / inférieure au paramètre)
  • accès aux clés ou carte en ordre décroissant
  • tête / queue (les entrées inférieures / supérieures à une clé donnée)
  • supérieur / inférieur (la touche suivante qui est supérieure ou inférieure au paramètre)
  • sous-carte (compte tenu de deux clés, retournez la carte située entre les deux clés)

Java a deux implémentations de NavigableMap - TreeMap et ConcurrentSkipListMap .

Si vous regardez l'idée / l'implémentation d'une liste de sauts, vous verrez pourquoi cela fonctionnerait très bien avec une telle structure et ses requêtes.


la source
1+ excellente réponse. Jamais pensé qu'une telle carte spécifique existait dans l'API Java.
Tulains Córdova
@ user61852 Mon type de données préféré est la liste à sauter et je l'ai fouillé. Quand je l'ai vu implémenté en 1.6, j'ai regardé tout ce qu'il offrait et j'ai remarqué les interfaces qu'il avait et donc ma familiarité avec lui.
C'est le genre de choses qui me convaincent que Java est l'un des langages les mieux conçus que vous puissiez trouver.
Tulains Córdova
1
Notez que bien que cela semble résoudre le problème d'OP, cela ne fonctionne pas comme LinkedHashMapcelui qu'il mentionne. Ni TreeMapni ne ConcurrentSkipListMapsont ordonnés par le temps d'insertion comme LinkedHashMap, ils sont plutôt ordonnés par un Comparatorou l'ordre naturel de la clé s'ils implémentent Comparable.
MikeFHay
1
Très bon point. L'opération au sol est ce que je cherchais, le comparateur que je peux ajouter facilement. Et dans mon cas, cela fonctionne beaucoup mieux pour implémenter le comparateur au lieu de réinventer la roue. Merci.
Nick
1

Ce que vous recherchez est une table de symboles qui prend en charge les opérations ordonnées. Et dans votre cas, c'est l'opération au sol.

L'implémentation de hachage d'une table de symboles est la plus rapide, mais elle n'offre pas ces opérations ordonnées.

Mais l'implémentation arborescente des tables de symboles le fait. Un exemple de cela en Java est la classe TreeMap

Moha le chameau tout-puissant
la source