Optimisation des performances Java HashMap / alternative

Je veux créer un HashMap volumineux mais les performances de put() ne sont pas suffisantes. Des idées?

Les autres suggestions de structure de données sont les bienvenues mais j’ai besoin de la fonctionnalité de recherche d’une carte Java:

map.get(key)

Dans mon cas, je veux créer une carte avec 26 millions d’entrées. En utilisant Java HashMap standard, le taux de mise devient incroyablement lent après 2 à 3 millions d’insertions.

De plus, est-ce que quelqu’un sait si l’utilisation de différentes dissortingbutions de codes de hachage pour les clés pourrait aider?

Ma méthode de hashcode:

 byte[] a = new byte[2]; byte[] b = new byte[3]; ... public int hashCode() { int hash = 503; hash = hash * 5381 + (a[0] + a[1]); hash = hash * 5381 + (b[0] + b[1] + b[2]); return hash; } 

J’utilise la propriété associative d’addition pour garantir que les objects égaux ont le même code de hachage. Les tableaux sont des octets avec des valeurs comsockets entre 0 et 51. Les valeurs ne sont utilisées qu’une seule fois dans les deux tableaux. Les objects sont égaux si les tableaux a contiennent les mêmes valeurs (dans l’un ou l’autre ordre) et il en va de même pour le tableau b. Donc a = {0,1} b = {45,12,33} et a = {1,0} b = {33,45,12} sont égaux.

EDIT, quelques notes:

  • Quelques personnes ont critiqué l’utilisation d’une carte de hachage ou d’une autre structure de données pour stocker 26 millions d’entrées. Je ne vois pas pourquoi cela semble étrange. Cela ressemble à un problème classique de structures de données et d’algorithmes. J’ai 26 millions d’articles et je veux pouvoir les insérer rapidement et les rechercher dans une structure de données: donnez-moi la structure de données et les algorithmes.

  • La définition de la capacité initiale de Java HashMap par défaut à 26 millions diminue les performances.

  • Certaines personnes ont suggéré d’utiliser des bases de données, dans d’autres situations, c’est certainement l’option intelligente. Mais je pose vraiment une question sur les structures de données et les algorithmes, une firebase database complète serait exagérée et beaucoup plus lente qu’une bonne solution de structure de données (après tout, la firebase database ne serait que logicielle mais aurait une communication sur disque).

Comme de nombreuses personnes l’ont souligné, la hashCode() était à blâmer. Il ne produisait qu’environ 20 000 codes pour 26 millions d’objects distincts. C’est une moyenne de 1 300 objects par groupe de hachage = très très mauvais. Toutefois, si je convertis les deux tableaux en un nombre de base 52, je suis assuré d’obtenir un code de hachage unique pour chaque object:

 public int hashCode() { // assume that both a and b are sorted return a[0] + powerOf52(a[1], 1) + powerOf52(b[0], 2) + powerOf52(b[1], 3) + powerOf52(b[2], 4); } public static int powerOf52(byte b, int power) { int result = b; for (int i = 0; i < power; i++) { result *= 52; } return result; } 

Les tableaux sont sortingés pour garantir que cette méthode remplit le contrat hashCode() dont les objects égaux ont le même code de hachage. Avec l’ancienne méthode, le nombre moyen de mises par seconde sur des blocs de 100 000 put, soit 100 000 à 2 000 000 était:

 168350.17 109409.195 81344.91 64319.023 53780.79 45931.258 39680.29 34972.676 31354.514 28343.062 25562.371 23850.695 22299.22 20998.006 19797.799 18702.951 17702.434 16832.182 16084.52 15353.083 

L'utilisation de la nouvelle méthode donne:

 337837.84 337268.12 337078.66 336983.97 313873.2 317460.3 317748.5 320000.0 309704.06 310752.03 312944.5 265780.75 275540.5 264350.44 273522.97 270910.94 279008.7 276285.5 283455.16 289603.25 

Beaucoup mieux L'ancienne méthode s'est très vite déroulée tandis que la nouvelle maintient un bon débit.

Une chose que je remarque dans votre hashCode() est que l’ordre des éléments dans les tableaux a[] et b[] n’a pas d’importance. Ainsi (a[]={1,2,3}, b[]={99,100}) va hacher à la même valeur que (a[]={3,1,2}, b[]={100,99}) . En fait, toutes les clés k1 et k2sum(k1.a)==sum(k2.a) et sum(k1.b)=sum(k2.b) entraîneront des collisions. Je suggère d’atsortingbuer un poids à chaque position du tableau:

 hash = hash * 5381 + (c0*a[0] + c1*a[1]); hash = hash * 5381 + (c0*b[0] + c1*b[1] + c3*b[2]); 

où, c0 , c1 et c3 sont des constantes distinctes (vous pouvez utiliser différentes constantes pour b si nécessaire). Cela devrait égaliser les choses un peu plus.

Pour élaborer sur Pascal: Comprenez-vous comment fonctionne une HashMap? Vous avez un certain nombre d’emplacements dans votre table de hachage. La valeur de hachage de chaque clé est trouvée, puis mappée sur une entrée de la table. Si deux valeurs de hachage correspondent à la même entrée – une “collision par hachage” – HashMap génère une liste chaînée.

Les collisions de hachage peuvent tuer les performances d’une carte de hachage. Dans le cas extrême, si toutes vos clés ont le même code de hachage, ou si elles ont des codes de hachage différents, mais qu’elles correspondent toutes au même emplacement, votre carte de hachage se transforme en une liste liée.

Donc, si vous rencontrez des problèmes de performances, la première chose que je vérifierai est: est-ce que je reçois une dissortingbution aléatoire de codes de hachage? Sinon, vous avez besoin d’une meilleure fonction de hachage. Eh bien, “mieux” dans ce cas peut signifier “mieux pour mon dataset particulier”. Comme, supposons que vous travailliez avec des chaînes et que vous preniez la longueur de la chaîne pour la valeur de hachage. (Pas comment fonctionne le Ssortingng.hashCode de Java, mais je ne fais qu’un exemple simple.) Si vos chaînes ont des longueurs très variables, de 1 à 10 000, et sont dissortingbuées de manière assez uniforme sur cette plage, cela pourrait être très bon. fonction de hachage. Mais si vos chaînes sont toutes composées de 1 ou 2 caractères, ce serait une très mauvaise fonction de hachage.

Edit: Je devrais append: Chaque fois que vous ajoutez une nouvelle entrée, HashMap vérifie s’il s’agit d’un doublon. En cas de collision par hachage, il doit comparer la clé entrante avec chaque clé associée à cet emplacement. Donc, dans le pire des cas, où tout se passe dans un seul emplacement, la deuxième clé est comparée à la première, la troisième est comparée à # 1 et # 2, la quasortingème est comparée à # 1, # 2 et # 3. , etc. Au moment où vous atteignez la clé n ° 1 million, vous avez fait plus d’un billion de comparaisons.

@Oscar: Euh, je ne vois pas comment c’est “pas vraiment”. C’est plutôt un “laissez-moi clarifier”. Mais oui, il est vrai que si vous créez une nouvelle entrée avec la même clé qu’une entrée existante, cela écrase la première entrée. C’est ce que je voulais dire lorsque je parlais de rechercher des doublons dans le dernier paragraphe: chaque fois qu’une clé hache dans le même emplacement, HashMap doit vérifier s’il s’agit d’une copie d’une clé existante ou si elle se trouve dans le même emplacement. fonction de hachage. Je ne sais pas que c’est le “point entier” d’un HashMap: je dirais que le “point entier” est que vous pouvez récupérer des éléments par clé rapidement.

Mais de toute façon, cela n’affecte pas le “point entier” que j’essayais de faire: quand vous avez deux clés – oui, des clés différentes, pas la même clé qui réapparaît – cette carte correspond au même emplacement de la table , HashMap construit une liste chaînée. Puis, comme il doit vérifier chaque nouvelle clé pour voir s’il s’agit bien d’une copie d’une clé existante, chaque tentative d’ajout d’une nouvelle entrée qui correspond à ce même emplacement doit poursuivre la liste chaînée en examinant chaque entrée existante pour voir si est une copie d’une clé précédemment vue ou s’il s’agit d’une nouvelle clé.

Mise à jour longtemps après le message original

Je viens de recevoir un vote sur cette réponse 6 ans après sa publication, ce qui m’a amené à relire la question.

La fonction de hachage donnée dans la question n’est pas un bon hash pour 26 millions d’entrées.

Il additionne a [0] + a [1] et b [0] + b [1] + b [2]. Il dit que les valeurs de chaque octet vont de 0 à 51, ce qui donne seulement (51 * 2 + 1) * (51 * 3 + 1) = 15 862 valeurs de hachage possibles. Avec 26 millions d’entrées, cela signifie une moyenne d’environ 1639 entrées par valeur de hachage. Cela implique beaucoup de collisions, nécessitant de nombreuses recherches séquentielles dans des listes liées.

L’OP dit que les différents ordres du tableau a et du tableau b doivent être considérés égaux, c.-à-d. [[1,2], [3,4,5]]. Est égal à [[2,1], [5,3,4] ]), et donc pour remplir le contrat, ils doivent avoir des codes de hachage égaux. D’accord. Pourtant, il y a beaucoup plus de 15 000 valeurs possibles. Sa deuxième fonction de hachage proposée est bien meilleure, donnant une gamme plus large.

Bien que quelqu’un ait commenté, il semble inapproprié qu’une fonction de hachage modifie d’autres données. Il serait plus logique de “normaliser” l’object lors de sa création ou de faire fonctionner la fonction de hachage à partir de copies des tableaux. En outre, l’utilisation d’une boucle pour calculer les constantes à chaque fois que la fonction est effectuée est inefficace. Comme il n’y a que quatre valeurs ici, j’aurais soit écrit

 return a[0]+a[1]*52+b[0]*52*52+b[1]*52*52*52+b[2]*52*52*52*52; 

ce qui obligerait le compilateur à effectuer le calcul une fois au moment de la compilation; ou avoir 4 constantes statiques définies dans la classe.

De plus, le premier brouillon d’une fonction de hachage comporte plusieurs calculs qui n’ajoutent rien à la gamme des sorties. Notez qu’il définit d’abord hash = 503 que multiplie par 5381 avant même de considérer les valeurs de la classe. Donc, en fait, il ajoute 503 * 5381 à chaque valeur. Qu’est-ce que cela accomplit? L’ajout d’une constante à chaque valeur de hachage ne fait que graver les cycles du processeur sans accomplir quoi que ce soit d’utile. Leçon ici: Ajouter de la complexité à une fonction de hachage n’est pas le but. L’objective est d’obtenir un large éventail de valeurs différentes, non seulement pour append de la complexité au profit de la complexité.

Ma première idée est de vous assurer que vous initialisez correctement votre HashMap. A partir des JavaDocs pour HashMap :

Une instance de HashMap a deux parameters qui affectent ses performances: la capacité initiale et le facteur de charge. La capacité correspond au nombre de compartiments dans la table de hachage et la capacité initiale correspond simplement à la capacité au moment de la création de la table de hachage. Le facteur de charge mesure la capacité de la table de hachage à augmenter avant que sa capacité ne soit automatiquement augmentée. Lorsque le nombre d’entrées dans la table de hachage dépasse le produit du facteur de charge et de la capacité actuelle, la table de hachage est répétée (c’est-à-dire que les structures de données internes sont recréées).

Donc, si vous commencez avec un HashMap trop petit, alors chaque fois qu’il doit être redimensionné, tous les hachages sont recalculés … ce qui peut être ce que vous ressentez lorsque vous atteignez le point d’insertion de 2-3 millions.

Je suggère une approche à trois volets:

  1. Exécutez Java avec plus de mémoire: java -Xmx256M par exemple pour fonctionner avec 256 mégaoctets. Utilisez plus si nécessaire et vous avez beaucoup de RAM.

  2. Mettez en cache vos valeurs de hachage calculées comme suggéré par une autre affiche, de sorte que chaque object ne calcule qu’une seule fois sa valeur de hachage.

  3. Utilisez un meilleur algorithme de hachage. Celui que vous avez posté renverrait le même hachage où a = {0, 1} comme si: a = {1, 0}, toutes choses égales par ailleurs.

Utilisez gratuitement ce que Java vous offre.

 public int hashCode() { return 31 * Arrays.hashCode(a) + Arrays.hashCode(b); } 

Je suis sûr que cela a beaucoup moins de chance de se heurter à votre méthode hashCode existante, bien que cela dépende de la nature exacte de vos données.

Entrer dans la zone grise du “sujet on / off”, mais nécessaire pour éliminer la confusion concernant la suggestion d’Oscar Reyes selon laquelle davantage de collisions de hash est une bonne chose car cela réduit le nombre d’éléments dans HashMap. Je peux mal comprendre ce que dit Oscar, mais je ne semble pas être le seul: kdgregory, delfuego, Nash0, et je semble tous partager la même compréhension.

Si je comprends ce que dit Oscar à propos de la même classe avec le même hashcode, il propose qu’une seule instance d’une classe avec un hashcode donné soit insérée dans HashMap. Par exemple, si j’ai une instance de SomeClass avec un code de hachage de 1 et une seconde instance de SomeClass avec un code de hachage de 1, une seule instance de SomeClass est insérée.

L’exemple Java pastebin à http://pastebin.com/f20af40b9 semble indiquer que ce qui précède résume correctement ce que propose Oscar.

Indépendamment de toute compréhension ou incompréhension, différentes instances de la même classe ne sont pas insérées une seule fois dans HashMap si elles ont le même code de hachage, et pas avant que l’on ait déterminé si les clés sont égales ou non. Le contrat de hachage exige que les objects égaux aient le même code de hachage; Cependant, il n’est pas nécessaire que les objects inégaux aient des codes de hachage différents (bien que cela puisse être souhaitable pour d’autres raisons) [1].

L’exemple de pastebin.com/f20af40b9 (auquel Oscar fait référence au moins deux fois) suit, mais légèrement modifié pour utiliser les assertions de JUnit plutôt que les lignes d’impression. Cet exemple est utilisé pour prendre en charge la proposition selon laquelle les mêmes codes de hachage provoquent des collisions et lorsque les classes sont identiques, une seule entrée est créée (par exemple, une seule chaîne dans ce cas spécifique):

 @Test public void shouldOverwriteWhenEqualAndHashcodeSame() { Ssortingng s = new Ssortingng("ese"); Ssortingng ese = new Ssortingng("ese"); // same hash right? assertEquals(s.hashCode(), ese.hashCode()); // same class assertEquals(s.getClass(), ese.getClass()); // AND equal assertTrue(s.equals(ese)); Map map = new HashMap(); map.put(s, 1); map.put(ese, 2); SomeClass some = new SomeClass(); // still same hash right? assertEquals(s.hashCode(), ese.hashCode()); assertEquals(s.hashCode(), some.hashCode()); map.put(some, 3); // what would we get? assertEquals(2, map.size()); assertEquals(2, map.get("ese")); assertEquals(3, map.get(some)); assertTrue(s.equals(ese) && s.equals("ese")); } class SomeClass { public int hashCode() { return 100727; } } 

Cependant, le hashcode n’est pas l’histoire complète. Ce que néglige l’exemple de pastebin est le fait que s et ese sont tous deux égaux: ils sont tous les deux la chaîne “ese”. Ainsi, l’insertion ou l’obtention du contenu de la carte en utilisant s ou ese ou "ese" comme clé sont tous équivalents car s.equals(ese) && s.equals("ese") .

Un deuxième test montre qu’il est erroné de conclure que des codes de hachage identiques sur la même classe sont la raison pour laquelle la valeur -> valeur s -> 1 est écrasée par ese -> 2 lorsque map.put(ese, 2) est appelé dans le premier test. Dans le test deux, s et ceux-ci ont toujours le même code de hachage (comme vérifié par assertEquals(s.hashCode(), ese.hashCode()); ) ET ils sont de la même classe. Cependant, s et ese sont des instances de MySsortingng dans ce test, pas des instances de Java Ssortingng – la seule différence pertinente pour ce test étant les égales: Ssortingng s equals Ssortingng ese test 1 ci-dessus, alors que MySsortingngs s does not equal MySsortingng ese :

 @Test public void shouldInsertWhenNotEqualAndHashcodeSame() { MySsortingng s = new MySsortingng("ese"); MySsortingng ese = new MySsortingng("ese"); // same hash right? assertEquals(s.hashCode(), ese.hashCode()); // same class assertEquals(s.getClass(), ese.getClass()); // BUT not equal assertFalse(s.equals(ese)); Map map = new HashMap(); map.put(s, 1); map.put(ese, 2); SomeClass some = new SomeClass(); // still same hash right? assertEquals(s.hashCode(), ese.hashCode()); assertEquals(s.hashCode(), some.hashCode()); map.put(some, 3); // what would we get? assertEquals(3, map.size()); assertEquals(1, map.get(s)); assertEquals(2, map.get(ese)); assertEquals(3, map.get(some)); } /** * NOTE: equals is not overridden so the default implementation is used * which means objects are only equal if they're the same instance, whereas * the actual Java Ssortingng class compares the value of its contents. */ class MySsortingng { Ssortingng i; MySsortingng(Ssortingng i) { this.i = i; } @Override public int hashCode() { return 100727; } } 

Sur la base d’un commentaire ultérieur, Oscar semble inverser ce qu’il a dit plus tôt et reconnaît l’importance des égaux. Cependant, il semble toujours que la notion d’égalité soit ce qui compte, pas la “même classe”, n’est pas claire (c’est moi qui souligne):

“Pas vraiment. La liste est créée uniquement si le hachage est le même, mais la clé est différente. Par exemple, si une Chaîne donne le hashcode 2345 et que Entier donne le même code de hachage 2345, l’entier est inséré dans la liste. equals (Integer) est false Mais si vous avez la même classe (ou au moins .equals renvoie true), la même entrée est utilisée: par exemple new Ssortingng (“one”) et `new Ssortingng (” one “) utilisé comme touches, utilisera la même entrée. En fait, c’est le point entier de HashMap en premier lieu! Voir par vous-même: pastebin.com/f20af40b9 – Oscar Reyes “

par rapport aux commentaires antérieurs qui traitent explicitement de l’importance de la même classe et du même code de hachage, sans mentionner les égaux:

“@delfuego: Voyez par vous-même: pastebin.com/f20af40b9 Donc, dans cette question, la même classe est utilisée (attendez une minute, la même classe est utilisée correctement?) Ce qui implique que lorsque le même hachage est utilisé, la même entrée est utilisé et il n’y a pas “liste” des entrées. – Oscar Reyes “

ou

“En fait, cela augmenterait les performances. Plus il y aurait de collisions, moins il y aurait d’entrées dans la hashtable, moins il y avait de travail à faire. N’est-ce pas le hash ou la hashtable? création où la performance se dégrade – Oscar Reyes “

ou

“@kdgregory: Oui, mais seulement si la collision se produit avec différentes classes, pour la même classe (ce qui est le cas), la même entrée est utilisée. – Oscar Reyes”

Encore une fois, je peux mal comprendre ce que Oscar essayait réellement de dire. Cependant, ses commentaires originaux ont causé suffisamment de confusion pour qu’il semble prudent de tout régler avec des tests explicites, de sorte qu’il n’y ait pas de doute.


[1] – De Java efficace, deuxième édition par Joshua Bloch:

  • Chaque fois qu’elle est invoquée sur le même object plusieurs fois pendant l’exécution d’une application, la méthode hashCode doit systématiquement renvoyer le même entier, à condition qu’aucune information utilisée dans des comparaisons égales sur l’object ne soit modifiée. Cet entier ne doit pas nécessairement restr cohérent d’une exécution d’une application à une autre exécution de la même application.

  • Si deux objects sont égaux selon la méthode égale s (Obj ect), alors l’appel de la méthode hashCode sur chacun des deux objects doit produire le même résultat entier.

  • Il n’est pas obligatoire que si deux objects sont inégaux selon la méthode égale à s (Object), alors l’appel de la méthode hashCode sur chacun des deux objects doit produire des résultats entiers distincts. Cependant, le programmeur doit savoir que produire des résultats entiers distincts pour des objects inégaux peut améliorer les performances des tables de hachage.

Si les tableaux de votre hashCode publié sont des octets, vous vous retrouverez probablement avec beaucoup de doublons.

a [0] + a [1] sera toujours compris entre 0 et 512. L’ajout des b entraînera toujours un nombre entre 0 et 768. multipliez ceux-ci et vous obtenez une limite supérieure de 400 000 combinaisons uniques, en supposant que vos données sont parfaitement dissortingbuées parmi toutes les valeurs possibles de chaque octet. Si vos données sont régulières, vous avez probablement des sorties beaucoup moins uniques de cette méthode.

HashMap a une capacité initiale et les performances de HashMap dépendent très fortement du hashCode qui produit les objects sous-jacents.

Essayez de modifier les deux.

Si les clés ont un motif quelconque, vous pouvez diviser la carte en plus petites cartes et avoir une carte d’index.

Exemple: Clés: 1,2,3, …. n 28 cartes de 1 million chacune. Carte d’index: 1-1,000,000 -> Map1 1,000,000-2,000,000 -> Map2

Vous ferez donc deux recherches, mais le jeu de clés sera de 1 000 000 contre 28 000 000. Vous pouvez facilement faire cela avec des modèles de piqûres aussi.

Si les clés sont complètement aléatoires, cela ne fonctionnera pas

Si les tableaux de deux octets que vous mentionnez sont votre clé entière, les valeurs sont comsockets entre 0 et 51, uniques et l’ordre dans les tableaux a et b est insignifiant, mes calculs me disent qu’il y a seulement environ 26 millions de permutations possibles. que vous essayez probablement de remplir la carte avec des valeurs pour toutes les clés possibles.

Dans ce cas, le remplissage et la récupération des valeurs de votre magasin de données seraient bien sûr beaucoup plus rapides si vous utilisez un tableau au lieu d’un HashMap et l’indexez de 0 à 25989599.

Je suis en retard ici, mais quelques commentaires sur les grandes cartes:

  1. Comme nous en avons longuement discuté dans d’autres articles, avec un bon hashCode (), 26 millions d’entrées dans une map ne sont pas une grosse affaire.
  2. Cependant, un problème potentiellement caché est l’impact des cartes géantes.

Je suppose que ces cartes vivent longtemps. c’est-à-dire que vous les remplissez et qu’ils restnt pendant toute la durée de l’application. Je suppose aussi que l’application elle-même a une longue vie – comme un serveur quelconque.

Chaque entrée d’un Java HashMap nécessite trois objects: la clé, la valeur et l’entrée qui les relie. Donc, 26M entrées dans la carte signifient 26M * 3 == 78M objects. Cela va bien jusqu’à ce que vous atteigniez un GC complet. Ensuite, vous avez un problème de pause dans le monde. Le GC examinera chacun des objects 78M et déterminera qu’ils sont tous vivants. Les objects 78M + ne sont que des objects à regarder. Si votre application peut tolérer de longues pauses occasionnelles (peut-être plusieurs secondes), il n’y a pas de problème. Si vous essayez d’obtenir une latence, vous pourriez avoir un problème majeur (bien sûr, si vous voulez des garanties de latence, Java n’est pas la plate-forme à choisir :)) Si les valeurs de vos cartes changent rapidement, vous pouvez obtenir des collectes complètes fréquentes ce qui aggrave grandement le problème.

Je ne connais pas une excellente solution à ce problème. Idées:

  • Il est parfois possible d’ajuster les tailles de GC et de tas pour “empêcher” la plupart des GC.
  • Si le contenu de votre carte est très variable, vous pouvez essayer FastMap de Javolution – il peut regrouper des objects Entry, ce qui pourrait réduire la fréquence des collectes complètes.
  • Vous pouvez créer votre propre implémentation de carte et faire de la gestion explicite de la mémoire sur l’octet [] (c’est-à-dire échanger le processeur pour une latence plus prévisible en sérialisant des millions d’objects en un seul octet)
  • N’utilisez pas Java pour cette partie – adressez-vous à une firebase database DB prévisible sur une socket
  • J’espère que le nouveau collecteur G1 aidera (s’applique principalement au cas de désabonnement)

Juste quelques reflections de quelqu’un qui a passé beaucoup de temps avec des cartes géantes en Java.


Vous pouvez essayer d’utiliser une firebase database en mémoire telle que HSQLDB .

Dans mon cas, je veux créer une carte avec 26 millions d’entrées. En utilisant Java HashMap standard, le taux de mise devient incroyablement lent après 2 à 3 millions d’insertions.

De mon expérience (projet étudiant en 2009):

  • J’ai construit un Red Black Tree pour 100 000 nœuds de 1 à 100 000. Il a fallu 785,68 secondes (13 minutes). Et j’ai échoué à construire RBTree pour 1 million de nœuds (comme vos résultats avec HashMap).
  • En utilisant “Prime Tree”, ma structure de données d’algorithme. Je pourrais construire un arbre / une carte pour 10 millions de nœuds en 21,29 secondes (RAM: 1,97 Go). Le coût de la valeur-clé de recherche est O (1).

Remarque: “Prime Tree” fonctionne mieux sur les “touches continues” de 1 à 10 millions. Pour travailler avec des clés comme HashMap, nous avons besoin de quelques ajustements mineurs.


Alors, qu’est-ce que #PrimeTree? En bref, il s’agit d’une structure de données arborescente telle que Binary Tree, les numéros de twigs étant des nombres premiers (au lieu de “2” -binary).

SQLite vous permet de l’utiliser en mémoire.

Avez-vous envisagé d’utiliser une firebase database intégrée pour cela? Regardez Berkeley DB . Il est open-source, détenu par Oracle maintenant.

Il stocke tout en tant que paire clé-> valeur, ce n’est pas un SGBDR. et il vise à être rapide.

Vous devez d’abord vérifier que vous utilisez correctement Map, la bonne méthode hashCode () pour les clés, la capacité initiale pour Map, la bonne implémentation Map, etc.

Ensuite, je suggère d’utiliser un profileur pour voir ce qui se passe réellement et où le temps d’exécution est passé. La méthode hashCode () est-elle par exemple exécutée des milliards de fois?

Si cela ne vous aide pas, pourquoi ne pas utiliser quelque chose comme EHCache ou memcached ? Oui, ce sont des produits pour la mise en cache, mais vous pouvez les configurer de manière à ce qu’ils aient suffisamment de capacité et qu’ils n’expulsent jamais aucune valeur du stockage en cache.

Une autre option serait un moteur de firebase database plus léger que le SGBDR complet SQL. Quelque chose comme Berkeley DB , peut-être.

Notez que je n’ai personnellement aucune expérience de la performance de ces produits, mais ils pourraient en valoir la peine.

Vous pouvez essayer de mettre en cache le code de hachage calculé sur l’object clé.

Quelque chose comme ça:

 public int hashCode() { if(this.hashCode == null) { this.hashCode = computeHashCode(); } return this.hashCode; } private int computeHashCode() { int hash = 503; hash = hash * 5381 + (a[0] + a[1]); hash = hash * 5381 + (b[0] + b[1] + b[2]); return hash; } 

Bien sûr, vous devez faire attention à ne pas changer le contenu de la clé après que le hashCode ait été calculé pour la première fois.

Edit: Il semble que la mise en cache avec des valeurs de code ne vaut pas la peine lorsque vous ajoutez chaque clé une seule fois à une carte. Dans une autre situation, cela pourrait être utile.

Une autre affiche a déjà souligné que l’implémentation de votre hashcode entraînera de nombreuses collisions en raison de la manière dont vous ajoutez les valeurs ensemble. Je suis prêt à être que, si vous regardez l’object HashMap dans un débogueur, vous constaterez que vous avez peut-être 200 valeurs de hachage distinctes, avec des chaînes de seau extrêmement longues.

Si vous avez toujours des valeurs dans la plage 0..51, chacune de ces valeurs prendra 6 bits à représenter. If you always have 5 values, you can create a 30-bit hashcode with left-shifts and additions:

  int code = a[0]; code = (code < < 6) + a[1]; code = (code << 6) + b[0]; code = (code << 6) + b[1]; code = (code << 6) + b[2]; return code; 

The left-shift is fast, but will leave you with hashcodes that aren't evenly dissortingbuted (because 6 bits implies a range 0..63). An alternative is to multiply the hash by 51 and add each value. This still won't be perfectly dissortingbuted (eg, {2,0} and {1,52} will collide), and will be slower than the shift.

  int code = a[0]; code *= 51 + a[1]; code *= 51 + b[0]; code *= 51 + b[1]; code *= 51 + b[2]; return code; 

As pointed out, your hashcode implementation has too many collisions, and fixing it should result in decent performance. Moreover, caching hashCodes and implementing equals efficiently will help.

If you need to optimize even further:

By your description, there are only (52 * 51 / 2) * (52 * 51 * 50 / 6) = 29304600 different keys (of which 26000000, ie about 90%, will be present). Therefore, you can design a hash function without any collisions, and use a simple array rather than a hashmap to hold your data, reducing memory consumption and increasing lookup speed:

 T[] array = new T[Key.maxHashCode]; void put(Key k, T value) { array[k.hashCode()] = value; T get(Key k) { return array[k.hashCode()]; } 

(Generally, it is impossible to design an efficient, collision-free hash function that clusters well, which is why a HashMap will tolerate collisions, which incurs some overhead)

Assuming a and b are sorted, you might use the following hash function:

 public int hashCode() { assert a[0] < a[1]; int ahash = a[1] * a[1] / 2 + a[0]; assert b[0] < b[1] && b[1] < b[2]; int bhash = b[2] * b[2] * b[2] / 6 + b[1] * b[1] / 2 + b[0]; return bhash * 52 * 52 / 2 + ahash; } static final int maxHashCode = 52 * 52 / 2 * 52 * 52 * 52 / 6; 

I think this is collision-free. Proving this is left as an exercise for the mathematically inclined reader.

In Effective Java: Programming Language Guide (Java Series)

Chapter 3 you can find good rules to follow when computing hashCode().

Specially:

If the field is an array, treat it as if each element were a separate field. That is, compute a hash code for each significant element by applying these rules recursively, and combine these values per step 2.b. If every element in an array field is significant, you can use one of the Arrays.hashCode methods added in release 1.5.

Allocate a large map in the beginning. If you know it will have 26 million ensortinges and you have the memory for it, do a new HashMap(30000000) .

Are you sure, you have enough memory for 26 million ensortinges with 26 million keys and values? This sounds like a lot memory to me. Are you sure that the garbage collection is doing still fine at your 2 to 3 million mark? I could imagine that as a bottleneck.

You could try two things:

  • Make your hashCode method return something simpler and more effective such as a consecutive int

  • Initialize your map as:

     Map map = new HashMap( 30000000, .95f ); 

Those two actions will reduce tremendously the amount of rehashing the structure is doing, and are pretty easy to test I think.

If that doesn’t work, consider using a different storage such a RDBMS.

MODIFIER

Is strange that setting the initial capacity reduce the performance in your case.

See from the javadocs :

If the initial capacity is greater than the maximum number of ensortinges divided by the load factor, no rehash operations will ever occur.

I made a microbeachmark ( which is not by anymeans definitive but at least proves this point )

 $cat Huge*java import java.util.*; public class Huge { public static void main( Ssortingng [] args ) { Map map = new HashMap( 30000000 , 0.95f ); for( int i = 0 ; i < 26000000 ; i ++ ) { map.put( i, i ); } } } import java.util.*; public class Huge2 { public static void main( String [] args ) { Map map = new HashMap(); for( int i = 0 ; i < 26000000 ; i ++ ) { map.put( i, i ); } } } $time java -Xms2g -Xmx2g Huge real 0m16.207s user 0m14.761s sys 0m1.377s $time java -Xms2g -Xmx2g Huge2 real 0m21.781s user 0m20.045s sys 0m1.656s $ 

So, using the initial capacity drops from 21s to 16s because of the rehasing. That leave us with your hashCode method as an "area of opportunity" 😉

MODIFIER

Is not the HashMap

As per your last edition.

I think you should really profile your application and see where it the memory/cpu is being consumed.

I have created a class implementing your same hashCode

That hash code give millions of collisions, then the ensortinges in the HashMap is reduced dramatically.

I pass from 21s, 16s in my previous test to 10s and 8s. The reason is because the hashCode provokes a high number of collisions and you are not storing the 26M objects you think but a much significant lower number ( about 20k I would say ) So:

The problems IS NOT THE HASHMAP is somewhere else in your code.

It is about time to get a profiler and find out where. I would think it is on the creation of the item or probably you're writing to disk or receiving data from the network.

Here's my implementation of your class.

note I didn't use a 0-51 range as you did but -126 to 127 for my values and admits repeated, that's because I did this test before you updated your question

The only difference is that your class will have more collisions thus less items stored in the map.

 import java.util.*; public class Item { private static byte w = Byte.MIN_VALUE; private static byte x = Byte.MIN_VALUE; private static byte y = Byte.MIN_VALUE; private static byte z = Byte.MIN_VALUE; // Just to avoid typing :) private static final byte M = Byte.MAX_VALUE; private static final byte m = Byte.MIN_VALUE; private byte [] a = new byte[2]; private byte [] b = new byte[3]; public Item () { // make a different value for the bytes increment(); a[0] = z; a[1] = y; b[0] = x; b[1] = w; b[2] = z; } private static void increment() { z++; if( z == M ) { z = m; y++; } if( y == M ) { y = m; x++; } if( x == M ) { x = m; w++; } } public Ssortingng toSsortingng() { return "" + this.hashCode(); } public int hashCode() { int hash = 503; hash = hash * 5381 + (a[0] + a[1]); hash = hash * 5381 + (b[0] + b[1] + b[2]); return hash; } // I don't realy care about this right now. public boolean equals( Object other ) { return this.hashCode() == other.hashCode(); } // print how many collisions do we have in 26M items. public static void main( Ssortingng [] args ) { Set set = new HashSet(); int collisions = 0; for ( int i = 0 ; i < 26000000 ; i++ ) { if( ! set.add( new Item() ) ) { collisions++; } } System.out.println( collisions ); } } 

Using this class has Key for the previous program

  map.put( new Item() , i ); 

Donne moi:

 real 0m11.188s user 0m10.784s sys 0m0.261s real 0m9.348s user 0m9.071s sys 0m0.161s 

I did a small test a while back with a list vs a hashmap, funny thing was iterating through the list and finding the object took the same amount of time in milliseconds as using the hashmaps get function… just an fyi. Oh yeah memory is a big issue when working with hashmaps that size.

The popular hashing methods used are not really very good for large sets and, as pointed out above, the hash used is particularly bad. Better is to use a hash algorithm with high mixing and coverage such as BuzHash (sample implementation at http://www.java2s.com/Code/Java/Development-Class/AveryefficientjavahashalgorithmbasedontheBuzHashalgoritm.htm )