Clés composites : un guide sur la façon de les gérer

Les clés composites surviennent lorsqu'une combinaison de données est requise pour définir la « clé » pour votre recherche de carte ou de cache. Un exemple de ceci pourrait être lorsque vous devez mettre en cache des valeurs en fonction du nom d'un client ainsi que du rôle d'un utilisateur. Dans un cas comme celui-ci, votre cache devra être capable de stocker des valeurs uniques basées sur chacun de ces deux (ou plusieurs) critères.

Il existe différentes manières de gérer les clés composites dans le code.

Combinez les critères dans une chaîne

La première réponse à laquelle on accède le plus souvent consiste à combiner les critères dans une chaîne à utiliser comme clé. C'est simple et ne demande pas beaucoup d'efforts :

 private String getMapKey(Long userId, String userLocale) { return userId + "." userLocale; }

C’est une façon assez basique de gérer le problème. L'utilisation d'une clé de chaîne peut faciliter le débogage et les enquêtes, car la clé de cache est dans un format lisible par l'homme. Mais il y a quelques problèmes à prendre en compte avec cette approche :

1. Cela nécessite la création d’une nouvelle chaîne à chaque interaction avec la carte. Bien que cette allocation de chaîne soit généralement petite, si la carte est consultée fréquemment, elle peut conduire à un grand nombre d'allocations qui prennent du temps et doivent être récupérées. La taille de l'allocation de chaîne peut également être plus grande en fonction de la taille des composants de votre clé ou du nombre dont vous disposez.

   
   

2. Vous devez vous assurer que la clé composite que vous créez ne peut pas être usurpée dans une autre valeur de clé :

 public String getMapKey(Integer groupId, Integer accessType) { return groupId.toString() + accessType.toString(); }

Dans ce qui précède, si vous aviez groupId = 1 et accessType = 23, ce serait la même clé de cache que groupId = 12 et accessType = 3. En ajoutant un caractère séparateur entre les chaînes, vous pouvez empêcher ce type de chevauchement. Mais faites attention aux parties facultatives d’une clé :

 public String getMapKey(String userProvidedString, String extensionName) { return userProvidedString + (extensionName == null ? "" : ("." + extensionName)); }

Dans l'exemple ci-dessus, extensionName est une partie facultative de la clé. Si extensionName est facultatif, userProvidedString peut inclure un séparateur et un extensionName valide et accéder aux données du cache auxquelles elles n'auraient pas dû avoir accès.

Lorsque vous utilisez des chaînes, vous devez réfléchir à la manière dont vous combinez vos données pour éviter toute collision dans les clés. Surtout autour de toute entrée générée par l'utilisateur pour la clé.

Utiliser des cartes/caches imbriqués

Une autre option consiste à ne pas combiner du tout les clés, mais à imbriquer vos structures de données (Maps of Maps of Maps) :

 Map<Integer, Map<String, String>> groupAndLocaleMap = new HashMap<>(); groupAndLocaleMap.computeIfAbsent(userId, k -> new HashMap()).put(userLocale, mapValue);

Cela présente l'avantage de ne pas avoir besoin d'allouer de nouvelle mémoire lors de l'interaction avec les cartes, car les valeurs transmises pour les clés sont déjà allouées. Et même si vous devrez effectuer plusieurs recherches pour obtenir la valeur finale, les cartes seront plus petites.

Mais l’inconvénient de cette approche est qu’elle devient de plus en plus compliquée à mesure que l’imbrication s’enfonce. Même avec seulement deux niveaux, l’initialisation de la carte peut paraître déroutante. Lorsque vous commencez à traiter 3 éléments de données ou plus, cela peut conduire à rendre votre code très verbeux. En plus de cela, chaque niveau nécessite une vérification nulle pour éviter les pointeurs nuls.

Certaines « parties clés » peuvent également ne pas fonctionner correctement comme clé de carte. Les tableaux ou les collections n'ont pas de méthodes égales par défaut qui comparent leur contenu. Vous devrez donc soit les mettre en œuvre, soit utiliser une autre alternative.

L’utilisation de cartes imbriquées peut également devenir moins efficace en termes d’espace en fonction du caractère unique de chaque niveau de vos clés.

Créer un objet clé composite

La dernière option consiste à créer un objet personnalisé pour la clé au lieu de combiner les valeurs de la clé dans une chaîne :

 private class MapKey { private final int userId; private final String userLocale; public MapKey(int userId, String userLocale) { this.userId = userId; this.userLocale = userLocale; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; MapKey mapKey = (MapKey) o; return userId == mapKey.userId && Objects.equals(userLocale, mapKey.userLocale); } @Override public int hashCode() { return Objects.hash(userId, userLocale); } }

Alors que chaque interaction nécessite toujours une nouvelle allocation de mémoire pour un nouvel objet. L'allocation de clé d'objet est nettement inférieure à celle nécessaire pour une chaîne composite. La raison en est que les parties qui composent la clé n'ont pas besoin d'être réaffectées en tant que chaînes. Au lieu de cela, seule la clé de l'objet d'encapsulation nécessite une nouvelle mémoire.

Un objet clé composite peut également permettre des personnalisations dans les implémentations d'égalité de clé et de hashcode. Comme ignorer les majuscules dans une chaîne ou utiliser un tableau ou une collection dans le cadre d'une clé.

L’inconvénient ici est que, encore une fois, cela nécessite beaucoup plus de code qu’une chaîne composite. Et cela nécessite de s'assurer que vous disposez de contrats d'égalité et de hashcode valides dans la classe clé de votre carte.

Alors lequel dois-je choisir ?

D'une manière générale, je suggérerais d'utiliser une clé de chaîne composite. C'est simple et facile à comprendre, nécessite le moins de code et est plus facile à déboguer plus tard. Bien qu'il s'agisse probablement de l'option la plus lente, l'écriture de code simple et lisible est généralement plus importante que les avantages que vous obtiendriez en utilisant l'une des deux autres options. Souviens-toi:

« L’optimisation prématurée est la racine de tous les maux » Donald Knuth

Si vous n'avez aucune preuve ou raison de croire que votre recherche de carte/cache va constituer un goulot d'étranglement en termes de performances, optez pour la lisibilité.

Mais si vous ÊTES dans un scénario où le débit vers votre carte ou votre cache est très élevé, il peut être judicieux de passer à l'une des deux autres options. Voyons comment les trois se comparent en termes de performances, ainsi qu'en termes de taille d'allocation de mémoire.

Pour tester les 3 scénarios ci-dessus, j'ai écrit du code qui reproduirait la même implémentation des 3 scénarios pour une clé composite. La clé elle-même se compose d'une valeur entière, d'une valeur de chaîne et d'une valeur longue. Les trois implémentations ont utilisé les mêmes données de test à chaque exécution pour créer les clés.

Toutes les exécutions ont été exécutées avec 1 million d'enregistrements dans la carte (le hashmap de Java a été utilisé). 3 essais ont été effectués pour construire la clé avec différentes combinaisons de tailles de clé :

• 100 entiers, 100 chaînes, 100 longs — 1 million de clés uniques

• 1 int, 1 chaîne, 1 000 000 longs – 1 million de clés uniques

• 1 000 000 d'ints, 1 chaîne, 1 longue — 1 million de clés uniques

  
  

Tout d’abord, regardons combien d’espace chaque carte occupe dans le tas. Ceci est important car cela affecte la quantité de mémoire nécessaire pour exécuter votre application.

Il y a une remarque intéressante et évidente à faire ici : dans le dernier scénario (1 000 000 d'ints), la taille des cartes imbriquées est nettement plus grande que les autres. En effet, dans ce scénario, les cartes imbriquées créent 1 carte de premier niveau avec 1 million d'entrées. Ensuite, pour les deuxième et troisième niveaux, il crée 1 million de cartes avec une seule entrée.

Toutes ces cartes imbriquées stockent une surcharge supplémentaire et sont pour la plupart vides. Il s’agit évidemment d’un cas limite, mais je voulais le montrer pour faire valoir un point. Lors de l'utilisation de l'implémentation des cartes d'imbrication, le caractère unique (et l'ordre de ce caractère unique) compte beaucoup.

Si vous inversez l’ordre à 1, 1, 1 million, vous obtenez en fait le besoin de stockage le plus bas.

Dans les deux autres scénarios, le mappage imbriqué est le plus efficace, l'objet clé personnalisé venant en deuxième position et les clés de chaîne en dernier.

Examinons ensuite le temps nécessaire pour créer chacune de ces cartes à partir de zéro :

Encore une fois, nous constatons que les cartes imbriquées fonctionnent le moins bien dans le scénario 1 million-1-1 pour l'allocation de mémoire, mais même dans ce cas, elles surpassent les autres en termes de temps CPU. Dans ce qui précède, nous pouvons également voir comment la clé String fonctionne le moins bien dans tous les cas, tandis que l'utilisation d'un objet clé personnalisé est légèrement plus lente et nécessite plus d'allocation de mémoire que les clés imbriquées.

Enfin, examinons le scénario de débit le plus élevé et l’efficacité de la lecture. Nous avons exécuté 1 million d'opérations de lecture (1 pour chaque clé créée) ; nous n'avons inclus aucune clé inexistante.

C'est là que nous voyons vraiment à quel point la recherche de clé basée sur une chaîne est lente. C'est de loin le plus lent et alloue de loin le plus de mémoire parmi les 3 options. L’objet clé personnalisé fonctionne de manière « proche » de l’implémentation des cartes imbriquées, mais reste toujours légèrement plus lent.

Cependant, lors de la recherche des allocations de mémoire, remarquez à quel point les cartes imbriquées brillent. Non, ce n'est pas un problème dans le graphique ; la recherche d'une valeur dans les cartes imbriquées ne nécessite aucune allocation de mémoire supplémentaire pour effectuer la recherche. Comment est-ce possible?

Eh bien, lorsque vous combinez les objets composites dans une clé de chaîne, vous devez à chaque fois allouer de la mémoire pour un nouvel objet chaîne :

 private String lookup(int key1, String key2, long key3) { return map.get(key1 + "." + key2 + "." + key3); }

Lorsque vous utilisez une clé composite, vous devez toujours allouer de la mémoire pour un nouvel objet clé. Mais comme les membres de cet objet sont déjà créés et référencés, il en alloue toujours beaucoup moins qu'une nouvelle chaîne :

 private String lookup(int key1, String key2, long key3) { return map.get(new MapKey(key1, key2, key3)); }

Mais l’implémentation des cartes imbriquées ne nécessite aucune nouvelle allocation de mémoire lors de la recherche. Vous réutilisez les parties données comme clés de chacune des cartes imbriquées :

 private String lookup(int key1, String key2, long key3) { return map.get(key1).get(key2).get(key3); }

Alors, sur la base de ce qui précède, lequel est le plus performant ?

Il est facile de constater que les cartes imbriquées arrivent en tête dans presque tous les scénarios. Si vous recherchez des performances brutes dans la plupart des cas d’utilisation, c’est probablement la meilleure option. Cependant, vous devez effectuer vos propres tests pour confirmer vos cas d'utilisation.

L'objet key constitue une très bonne option à usage général lorsque les cartes imbriquées deviennent peu pratiques ou impossibles à utiliser pour votre implémentation. Et la clé de chaîne composite, bien que la plus simple à implémenter, sera presque toujours la plus lente.

Le dernier point à considérer lorsque vous cherchez à implémenter des clés composites est que vous pouvez combiner les éléments ci-dessus. Par exemple, vous pouvez utiliser des cartes imbriquées pour le premier ou les deux premiers niveaux, puis utiliser un objet clé composite pour simplifier les niveaux plus profonds.

Cela pourrait toujours garder vos données partitionnées pour des recherches rapides tout en optimisant les performances de stockage et de recherche. Et gardez également votre code lisible.

TLDR ;

La plupart du temps, restez simple. Combinez vos clés composites dans une clé de chaîne pour le stockage dans une carte ou un cache si c'est l'option la plus simple et que les performances ne sont pas une préoccupation majeure.

Dans les scénarios où les performances sont critiques, assurez-vous d’effectuer vos propres tests. Mais l’utilisation de cartes imbriquées sera la plus performante dans la plupart des cas. Il aura probablement également les besoins de stockage les plus faibles. Et les clés composites restent une alternative performante lorsque les mappages d’imbrication deviennent peu pratiques.

Également publié ici