Quelle est l'approche la plus efficace pour utiliser HashMaps?
a) Utilisez plusieurs hachons plus petits, ou
B) stocker tous les objets d'un hashmap géant?
(supposons que l'algorithme de hachage pour les clés est assez efficace, ce qui entraîne peu de collisions)
Clarification: Option B implique la ségrégation par la clé primaire - I.E. Aucune recherche supplémentaire n'est nécessaire pour déterminer quel hashmap à utiliser. (Par exemple, si les touches de recherche sont alphanumériques, HASHMAP 1 stocke les magasins de A A A, HASHMAP 2, etc.)
3 Réponses :
Certainement B. L'avantage des tables de hachage est que le nombre moyen de comparaisons par recherche est indépendant de la taille.
Si vous divisez votre carte en N plus petits HASHMAPS, vous devrez rechercher la moitié d'entre eux en moyenne pour chaque recherche. Si les plus petits HASHMAP ont le même facteur de charge que la carte plus large aurait eue, vous augmenterez le nombre total de comparaisons d'un facteur d'environ N / 2.
et si les plus petits haches ont un facteur de charge plus petit, vous gaspillez la mémoire.
Tout ce qui suppose que vous distribuiez les clés de manière aléatoire entre les plus petits HASHMAPS. Si vous les distribuez en fonction de la fonction de la clé (par exemple, un préfixe de chaîne), ce que vous avez créé est un Trie , qui est efficace pour certaines applications (par exemple, automativement complète dans les formulaires Web.)
La première phrase suppose que les méthodes de hashcode des objets génèrent toutes des valeurs de hachage bien distribuées. Dans le pire des cas (c'est-à-dire où tous les objets hachage à la même valeur), la recherche de hashtable sera O (n) .
Ces cartes sont-elles utilisées dans des endroits logiquement distincts? Par exemple, je n'aurais pas une carte contenant des utilisateurs, des résultats de requête en cache, des enregistreurs, etc., simplement parce que vous savez que les clés ne seront pas affrontées. Cependant, je ne voudrais pas diviser une seule carte en plusieurs cartes.
GARDER UN HASHMAP pour chaque mappage logique de la clé à la valeur.
En outre @ Jon's Réponse, il peut y avoir des raisons pratiques pour lesquelles vous souhaitez conserver des tables de hachage séparées.
Si vous avez des tables séparées pour différents mappages, vous pouvez «effacer» chacun des mappages de manière indépendante; par exemple. en appelant «clair» ou se débarrasser de la référence à la table correspondante.
Si les tables distinctes contiennent des mappages à des entrées en cache, vous pouvez utiliser différentes stratégies pour "vieillir" les entrées respectives.
Si l'application est multi-threadée, l'utilisation de tableaux distincts peut réduire la conflit de verrouillage, et peut (pour certaines architectures de processeur) augmenter les rapports de cache de mémoire du processeur.