Je veux créer un grand HashMap mais les put()performances ne sont pas assez bonnes. Des idées?

D'autres suggestions de structure de données sont les bienvenues, mais j'ai besoin de la fonction de recherche d'une carte Java:

map.get(key)

Dans mon cas, je souhaite créer une carte avec 26 millions d'entrées. En utilisant le Java HashMap standard, le taux de vente devient insupportablement lent après 2-3 millions d'insertions.

En outre, est-ce que quelqu'un sait si l'utilisation de différentes distributions de code 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 m'assurer que les objets égaux ont le même hashcode. Les tableaux sont des octets avec des valeurs comprises entre 0 et 51. Les valeurs ne sont utilisées qu'une seule fois dans l'un ou l'autre tableau. Les objets sont égaux si les tableaux a contiennent les mêmes valeurs (dans les deux ordres) 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'éléments et je veux pouvoir les insérer rapidement et les rechercher à partir d'une structure de données: donnez-moi la structure des données et les algorithmes.

• La définition de la capacité initiale du 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 base de données complète serait excessive et beaucoup plus lente qu'une bonne solution de structure de données (après tout, la base de données n'est qu'un logiciel mais aurait une surcharge de communication et éventuellement de disque).

Comme de nombreuses personnes l'ont souligné, la hashCode()méthode était à blâmer. Il ne générait qu'environ 20 000 codes pour 26 millions d'objets distincts. C'est une moyenne de 1 300 objets par seau de hachage = très très mauvais. Cependant, si je transforme les deux tableaux en un nombre en base 52, je suis assuré d'obtenir un code de hachage unique pour chaque objet:

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 triés pour garantir que ces méthodes remplissent le hashCode()contrat selon lequel les objets égaux ont le même code de hachage. En utilisant l'ancienne méthode, le nombre moyen de put par seconde sur des blocs de 100 000 put, de 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 arrêtée très rapidement tandis que la nouvelle maintient un bon débit.

Une chose que je remarque dans votre hashCode()méthode est que l'ordre des éléments dans les tableaux a[]et de b[]peu d' importance. Ainsi (a[]={1,2,3}, b[]={99,100})sera haché à la même valeur que (a[]={3,1,2}, b[]={100,99}). En fait, toutes les clés k1et k2où sum(k1.a)==sum(k2.a)et sum(k1.b)=sum(k2.b)entraîneront des collisions. Je suggère d'attribuer 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, c1et c3sont distinctes des constantes (vous pouvez utiliser différentes constantes pour le bcas échéant). Cela devrait égaliser un peu plus les choses.

Pour élaborer sur Pascal: Comprenez-vous comment fonctionne un HashMap? Vous avez un certain nombre d'emplacements dans votre table de hachage. La valeur de hachage pour chaque clé est trouvée, puis mappée à une entrée de la table. Si deux valeurs de hachage correspondent à la même entrée - une "collision de hachage" - HashMap crée une liste lié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, alors 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érifierais est la suivante: est-ce que j'obtiens une distribution 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 ensemble particulier de données». Par exemple, supposons que vous travailliez avec des chaînes et que vous ayez pris la longueur de la chaîne pour la valeur de hachage. (Pas comment fonctionne String.hashCode de Java, mais je ne fais qu'un simple exemple.) Si vos chaînes ont des longueurs très variables, de 1 à 10000, et sont assez uniformément réparties sur cette plage, cela pourrait être un très bon fonction de hachage. Mais si vos chaînes contiennent toutes 1 ou 2 caractères, ce serait une très mauvaise fonction de hachage.

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

@Oscar: Euh, je ne vois pas comment c'est un "pas vraiment". C'est plus comme 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 quand j'ai parlé de la recherche de 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'un duplicata d'une clé existante, ou s'ils sont juste dans le même emplacement par coïncidence du fonction de hachage. Je ne sais pas si c'est le "point entier" d'un HashMap: je dirais que le "point entier" est que vous pouvez récupérer rapidement des éléments par clé.

Mais de toute façon, cela n'affecte pas le "point entier" que j'essayais de faire valoir: lorsque vous avez deux clés - oui, des clés différentes, pas la même clé apparaissant à nouveau - qui correspondent au même emplacement dans le tableau , HashMap construit une liste chaînée. Ensuite, comme il doit vérifier chaque nouvelle clé pour voir s'il s'agit en fait d'un duplicata d'une clé existante, chaque tentative d'ajouter une nouvelle entrée qui correspond à ce même emplacement doit poursuivre la liste liée en examinant chaque entrée existante pour voir si cela est un double d'une clé vue précédemment, ou s'il s'agit d'une nouvelle clé.

Mettre à jour longtemps après le message d'origine

Je viens d'obtenir un vote positif sur cette réponse 6 ans après la publication, ce qui m'a amené à relire la question.

La fonction de hachage donnée dans la question n'est pas un bon hachage 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 représente beaucoup de collisions, nécessitant de nombreuses recherches séquentielles dans des listes liées.

L'OP dit que différents ordres dans le tableau a et le tableau b doivent être considérés comme égaux, c'est-à-dire [[1,2], [3,4,5]]. Equals ([[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 plage plus large.

Bien que, comme quelqu'un d'autre l'a commenté, il semble inapproprié pour une fonction de hachage de modifier d'autres données. Il serait plus judicieux de "normaliser" l'objet lors de sa création, ou de faire fonctionner la fonction de hachage à partir de copies des tableaux. De plus, l'utilisation d'une boucle pour calculer des constantes à chaque fois que la fonction est exécuté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 ne s'ajoutent en rien à la plage de sorties. Notez qu'il définit d'abord hash = 503 puis 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 brûler les cycles du processeur sans rien accomplir d'utile. Leçon ici: Le but n'est pas d'ajouter de la complexité à une fonction de hachage. Le but est d'obtenir une large gamme de valeurs différentes, pas seulement d'ajouter de la complexité pour des raisons de complexité.

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

Une instance de HashMap a deux paramètres qui affectent ses performances: la capacité initiale et le facteur de charge. La capacité est le nombre de compartiments dans la table de hachage, et la capacité initiale est simplement la capacité au moment de la création de la table de hachage. Le facteur de charge est une mesure du niveau de remplissage autorisé de la table de hachage 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 remaniée (c'est-à-dire que les structures de données internes sont reconstruites) de sorte que la table de hachage a environ deux fois le nombre de compartiments.

Donc, si vous commencez avec un HashMap trop petit, chaque fois qu'il doit être redimensionné, tous les hachages sont recalculés ... ce qui pourrait être ce que vous ressentez lorsque vous arrivez au point d'insertion de 2-3 millions.

Je suggérerais une approche en trois volets:

1. Exécutez Java avec plus de mémoire: java -Xmx256Mpar exemple pour exécuter 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 objet ne calcule sa valeur de hachage qu'une seule fois.

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

Utilisez ce que Java vous offre gratuitement.

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

Je suis presque sûr que cela a beaucoup moins de chances de se heurter que 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 / hors sujet", mais nécessaire pour éliminer la confusion concernant la suggestion d'Oscar Reyes selon laquelle plus de collisions de hachage est une bonne chose car cela réduit le nombre d'éléments dans le 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 (mauvaise) compréhension.

Si je comprends ce qu'Oscar dit à 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 le HashMap. Par exemple, si j'ai une instance de SomeClass avec un hashcode de 1 et une deuxième instance de SomeClass avec un hashcode de 1, une seule instance de SomeClass est insérée.

L'exemple de 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 malentendu, ce qui se passe, c'est que différentes instances de la même classe ne sont pas insérées une seule fois dans le HashMap si elles ont le même hashcode - pas tant qu'il n'a pas été déterminé si les clés sont égales ou non. Le contrat de hashcode exige que les objets égaux aient le même hashcode; cependant, il ne nécessite pas que les objets inégaux aient des codes de hachage différents (bien que cela puisse être souhaitable pour d'autres raisons) [1].

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

@Test
public void shouldOverwriteWhenEqualAndHashcodeSame() {
    String s = new String("ese");
    String ese = new String("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 l'exemple de pastebin néglige, c'est le fait que les deux set esesont égaux: ils sont tous les deux la chaîne "ese". Ainsi, insérer ou récupérer le contenu de la carte en utilisant sou eseou "ese"comme clé sont tous équivalents cars.equals(ese) && s.equals("ese") .

Un deuxième test démontre qu'il est erroné de conclure que des hashcodes identiques sur la même classe sont la raison pour laquelle la clé -> valeur s -> 1est écrasée par ese -> 2quand map.put(ese, 2)est appelée dans le premier test. Dans le test deux, set eseont toujours le même hashcode (comme vérifié par assertEquals(s.hashCode(), ese.hashCode());) ET ils sont la même classe. Cependant, set ce esesont des MyStringinstances de ce test, pas des Stringinstances Java - la seule différence pertinente pour ce test étant les égaux: String s equals String esedans le test un ci-dessus, alors que MyStrings s does not equal MyString esedans le test deux:

@Test
public void shouldInsertWhenNotEqualAndHashcodeSame() {
    MyString s = new MyString("ese");
    MyString ese = new MyString("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 String class compares the value of its contents.
 */
class MyString {
    String i;

    MyString(String 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é est ce qui compte, et non 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 un String donne le hashcode 2345 et et et Integer donne le même hashcode 2345, alors l'entier est inséré dans la liste parce que String. 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 String ("one") et `new String (" one ") utilisé comme clés, utiliseront la même entrée. En fait, c'est le point TOUT de HashMap en premier lieu! Voyez par vous-même: pastebin.com/f20af40b9 - Oscar Reyes "

par rapport aux commentaires précédents qui abordent explicitement l'importance d'une classe identique et du même hashcode, sans mention d'é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, non?) Ce qui implique que lorsque le même hachage est utilisé, la même entrée est utilisé et il n'y a pas de "liste" des entrées. - Oscar Reyes "

ou

"En fait, cela augmenterait les performances. Plus il y a de collisions eq, moins d'entrées dans l'équation de la table de hachage, moins de travail à faire. N'est-ce pas le hachage (qui a l'air bien) ni la table de hachage (qui fonctionne très bien) je parie que c'est sur l'objet création où la performance est dégradante. - 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 qu'Oscar essayait de dire. Cependant, ses commentaires originaux ont causé suffisamment de confusion pour qu'il semble prudent de tout éclaircir avec des tests explicites afin qu'il n'y ait pas de doutes persistants.

[1] - Tiré de Effective Java, deuxième édition par Joshua Bloch:

• Chaque fois qu'elle est appelée sur le même objet plus d'une fois lors de 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 les comparaisons égales sur l'objet ne soit modifiée. Cet entier n'a pas besoin de rester cohérent d'une exécution d'une application à une autre exécution de la même application.

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

• Il n'est pas nécessaire que si deux objets sont inégaux selon la méthode égale s (Object), l'appel de la méthode hashCode sur chacun des deux objets doit produire des résultats entiers distincts. Cependant, le programmeur doit être conscient que la production de résultats entiers distincts pour des objets 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 se traduira toujours par un nombre compris 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 soient parfaitement distribué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 de hashCode qui produit des objets sous-jacents.

Essayez de modifier les deux.

Si les touches ont un modèle, vous pouvez diviser la carte en cartes plus petites 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 l'ensemble de clés serait de 1 000 000 contre 28 000 000. Vous pouvez facilement le faire avec des motifs de piqûre également.

Si les touches 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 comprises entre 0 et 51, uniques et l'ordre dans les tableaux a et b est insignifiant, mes calculs me disent qu'il n'y a que 26 millions de permutations possibles et 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 que vous l'indexez de 0 à 25989599.

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

1. Comme discuté en détail dans d'autres articles, avec un bon hashCode (), 26 millions d'entrées dans une carte ne sont pas un gros problème.
2. Cependant, un problème potentiellement caché ici est l'impact GC des cartes géantes.

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

Chaque entrée dans un HashMap Java nécessite trois objets: la clé, la valeur et l'entrée qui les lie. Donc, 26M entrées dans la carte signifie 26M * 3 == 78M objets. C'est 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 78 millions d'objets et déterminera qu'ils sont tous vivants. 78M + d'objets, c'est juste beaucoup d'objets à 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 des garanties de 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 évoluent rapidement, vous pouvez vous retrouver avec des collectes complètes fréquentes ce qui aggrave considérablement le problème.

Je ne connais pas de solution idéale à ce problème. Idées:

• Il est parfois possible d'ajuster les tailles de GC et de segment de mémoire pour éviter «principalement» les GC complets.
• Si le contenu de votre carte se désactive beaucoup, vous pouvez essayer FastMap de Javolution - il peut regrouper des objets Entry, ce qui pourrait réduire la fréquence des collectes complètes.
• Vous pouvez créer votre propre implément de carte et faire une 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'objets en un seul octet [] - ugh!)
• N'utilisez pas Java pour cette partie - parlez à une sorte de DB en mémoire prévisible via un socket
• J'espère que le nouveau collecteur G1 aidera (s'applique principalement au cas à taux de désabonnement élevé)

Juste quelques pensées de quelqu'un qui a passé beaucoup de temps avec des cartes géantes à Java.

Dans mon cas, je souhaite créer une carte avec 26 millions d'entrées. En utilisant le Java HashMap standard, le taux de vente devient insupportablement 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. Cela a pris 785,68 secondes (13 minutes). Et je n'ai pas réussi à créer 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 créer 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 avec des "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, c'est une structure de données arborescente comme Binary Tree, avec des branches les nombres sont des nombres premiers (au lieu de "2" -binary).

Vous pouvez essayer d'utiliser une base de données en mémoire comme HSQLDB .

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

Avez-vous envisagé d'utiliser une base de données intégrée pour ce faire? Regardez Berkeley DB . Il est open-source, propriété d'Oracle maintenant.

Il stocke tout sous forme de 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, une bonne méthode hashCode () pour les clés, la capacité initiale de Map, la bonne implémentation de Map, etc. comme beaucoup d'autres réponses le décrivent.

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

Si cela ne veut pas de l' aide, que diriez - vous d' utiliser quelque chose comme EHCache ou memcached ? Oui, ce sont des produits pour la mise en cache, mais vous pouvez les configurer pour qu'ils aient une capacité suffisante et n'expulsent jamais de valeurs du stockage en cache.

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

Notez que je n'ai personnellement aucune expérience des performances de ces produits, mais ils pourraient valoir la peine d'être essayés.

Vous pouvez essayer de mettre en cache le code de hachage calculé sur l'objet 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 modifier le contenu de la clé après que le hashCode a été calculé pour la première fois.

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

Une autre affiche a déjà souligné que votre implémentation de hashcode entraînera de nombreuses collisions en raison de la façon dont vous ajoutez des valeurs ensemble. Je suis prêt à être que, si vous regardez l'objet 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 comprises entre 0 et 51, chacune de ces valeurs prendra 6 bits pour être représentée. Si vous avez toujours 5 valeurs, vous pouvez créer un hashcode 30 bits avec des décalages à gauche et des ajouts:

    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;

Le décalage à gauche est rapide, mais vous laissera avec des codes de hachage qui ne sont pas uniformément répartis (car 6 bits implique une plage de 0 à 63). Une alternative consiste à multiplier le hachage par 51 et à ajouter chaque valeur. Cela ne sera toujours pas parfaitement distribué (par exemple, {2,0} et {1,52} entreront en collision), et sera plus lent que le décalage.

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

Comme indiqué, votre implémentation de hashcode a trop de collisions et sa correction devrait entraîner des performances décentes. De plus, la mise en cache des hashCodes et l'implémentation efficace d'égaux vous aideront.

Si vous avez besoin d'optimiser encore plus:

D'après votre description, il n'y a que (52 * 51/2) * (52 * 51 * 50/6) = 29304600 clés différentes (dont 26000000, soit environ 90%, seront présentes). Par conséquent, vous pouvez concevoir une fonction de hachage sans aucune collision et utiliser un tableau simple plutôt qu'une carte de hachage pour contenir vos données, ce qui réduit la consommation de mémoire et augmente la vitesse de recherche:

T[] array = new T[Key.maxHashCode];

void put(Key k, T value) {
    array[k.hashCode()] = value;

T get(Key k) {
    return array[k.hashCode()];
}

(En général, il est impossible de concevoir une fonction de hachage efficace et sans collision qui se clusterise bien, c'est pourquoi un HashMap tolérera les collisions, ce qui entraîne une surcharge)

En supposant que aet bsont triés, vous pouvez utiliser la fonction de hachage suivante:

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;  

Je pense que c'est sans collision. Prouver cela est laissé comme un exercice pour le lecteur incliné mathématiquement.

Dans Effective Java: Guide du langage de programmation (série Java)

Chapitre 3, vous pouvez trouver de bonnes règles à suivre lors du calcul de hashCode ().

Spécialement:

Si le champ est un tableau, traitez-le comme si chaque élément était un champ distinct. Autrement dit, calculez un code de hachage pour chaque élément significatif en appliquant ces règles de manière récursive et combinez ces valeurs à l'étape 2.b. Si chaque élément d'un champ de tableau est significatif, vous pouvez utiliser l'une des méthodes Arrays.hashCode ajoutées dans la version 1.5.

Attribuez une grande carte au début. Si vous savez qu'il aura 26 millions d'entrées et que vous avez la mémoire pour cela, faites unnew HashMap(30000000) .

Êtes-vous sûr d'avoir suffisamment de mémoire pour 26 millions d'entrées avec 26 millions de clés et de valeurs? Cela me rappelle beaucoup de mémoire. Êtes-vous sûr que le ramasse-miettes fonctionne toujours bien à votre 2 à 3 millions? Je pourrais imaginer cela comme un goulot d'étranglement.

Vous pouvez essayer deux choses:

Ces deux actions réduiront énormément la quantité de remaniement de la structure et sont assez faciles à tester, je pense.

Si cela ne fonctionne pas, envisagez d'utiliser un stockage différent tel qu'un SGBDR.

ÉDITER

Est-ce étrange que le réglage de la capacité initiale réduise les performances dans votre cas.

Voir dans les javadocs :

Si la capacité initiale est supérieure au nombre maximum d'entrées divisé par le facteur de charge, aucune opération de reprise n'aura jamais lieu.

J'ai fait une microbeachmark (ce qui n'est en aucun cas définitif mais prouve au moins ce point)

$cat Huge*java
import java.util.*;
public class Huge {
    public static void main( String [] 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
$

Ainsi, l'utilisation de la capacité initiale passe de 21 s à 16 s à cause du rehasing. Cela nous laisse avec votre hashCodeméthode comme "zone d'opportunité";)

ÉDITER

N'est-ce pas le HashMap

Selon votre dernière édition.

Je pense que vous devriez vraiment profiler votre application et voir où la mémoire / le processeur est consommée.

J'ai créé une classe implémentant votre même hashCode

Ce code de hachage donne des millions de collisions, puis les entrées dans le HashMap sont considérablement réduites.

Je passe de 21s, 16s dans mon test précédent à 10s et 8s. La raison en est que le hashCode provoque un nombre élevé de collisions et que vous ne stockez pas les 26 millions d'objets que vous pensez, mais un nombre beaucoup plus faible (environ 20k je dirais) Donc:

Le problème N'EST PAS LE HASHMAP est ailleurs dans votre code.

Il est temps de trouver un profileur et de savoir où. Je pense que c'est lors de la création de l'élément ou probablement que vous écrivez sur le disque ou que vous recevez des données du réseau.

Voici ma mise en œuvre de votre classe.

notez que je n'ai pas utilisé une plage de 0-51 comme vous l'avez fait mais de -126 à 127 pour mes valeurs et admet répété, c'est parce que j'ai fait ce test avant que vous ne mettiez à jour votre question

La seule différence est que votre classe aura plus de collisions donc moins d'éléments stockés dans la carte.

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 String toString() {
        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( String [] 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 );
    }
}

L'utilisation de cette classe a une clé pour le programme précédent

 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

Essayez peut-être d'utiliser si vous en avez besoin pour être synchronisé

http://commons.apache.org/collections/api/org/apache/commons/collections/FastHashMap.html

J'ai fait un petit test il y a quelque temps avec une liste par rapport à un hashmap, une chose amusante était de parcourir la liste et de trouver l'objet prenait le même temps en millisecondes que d'utiliser la fonction get hashmaps ... juste un fyi. Oh oui, la mémoire est un gros problème lorsque vous travaillez avec des hashmaps de cette taille.

Les méthodes de hachage populaires utilisées ne sont pas vraiment très bonnes pour les grands ensembles et, comme indiqué ci-dessus, le hachage utilisé est particulièrement mauvais. Mieux vaut utiliser un algorithme de hachage avec un mélange et une couverture élevés tels que BuzHash (exemple d'implémentation à http://www.java2s.com/Code/Java/Development-Class/AveryefficientjavahashalgorithmbasedontheBuzHashalgoritm.htm )