Une chose que je constate dans votre hashCode() méthode est que l'ordre des éléments dans les tableaux de a[] et b[] n'a pas d'importance. Ainsi, {[4] } hachera à la même valeur que (a[]={3,1,2}, b[]={100,99}). En fait toutes les touches k1 et k2 où sum(k1.a)==sum(k2.a) et sum(k1.b)=sum(k2.b) entraînera dans 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, c1 et c3 sont distincts de constantes (vous pouvez utiliser différentes constantes de b si nécessaire). Cela devrait égaliser les choses un peu plus.

Pour développer 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 cartographiés à une entrée dans la table. Si deux valeurs de hachage correspondent à la même entrée-une "collision de hachage" - HashMap construit 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 elles sont toutes mappées sur le même emplacement, ensuite, votre carte de hachage se transforme en une liste liée.

Donc, si vous voyez des problèmes de performance, la première chose que je vérifierais est: Est-ce que J'obtiens une distribution aléatoire des 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 de données 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 la chaîne de Java.hashCode fonctionne, mais je ne fais qu'un exemple simple.) Si votre les chaînes ont des longueurs très variables, de 1 à 10 000, et sont assez uniformément réparties sur cette plage, ce qui pourrait être une très bonne fonction de hachage. Mais si vos chaînes sont toutes de 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. Quand il y a une collision de hachage, il doit comparer la clé entrante à chaque clé mappée à cet emplacement. Donc dans le pire des cas où tout hachages pour un logement unique, la deuxième clé, c'est par rapport à la première, la troisième clé est comparé à #1 et #2, la quatrième clé est comparé à #1, #2, et #3, etc. Au moment où vous arrivez à la clé # 1 million, Vous avez fait plus d'un billion compare.

@Oscar: euh, je ne vois pas en quoi c'est un "pas vraiment". C'est plus comme un "laissez-moi clarifier". Mais oui, il est vrai que si vous faites 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é recherche de doublons dans le dernier paragraphe: chaque fois qu'une clé est hachée sur le même emplacement, HashMap doit vérifier s'il s'agit d'un doublon d'une clé existante, ou si elles sont juste dans le même emplacement par coïncidence de la fonction de hachage. Je ne sais pas si c'est le "point" d'un HashMap: je dirais que le "point" est que vous pouvez récupérer les éléments clés 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 apparaît à nouveau - cette carte au même emplacement dans la table, HashMap construit une liste liée. Ensuite, parce qu'il doit vérifier chaque nouvelle clé pour voir si elle est en fait un double de la clé existante, chaque tentative pour ajouter une nouvelle entrée qui correspond à ce même logement doit chasser la liste liée de l'examen de chaque entrée existante pour voir si c'est un doublon d'un déjà-vu clé, ou si c'est une nouvelle clé.

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

Je viens d'avoir un vote sur cette réponse 6 ans après l'affichage qui m'a conduit à relire la question.

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

, Il ajoute un ensemble[0]+a[1] et b[0]+b[1]+b[2]. Il dit que les valeurs de chaque octet vont de 0 à 51, de sorte que cela ne donne que (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. C'est beaucoup, beaucoup de collisions, nécessitant beaucoup de séquentielles recherche dans les 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]].égal([[2,1],[5,3,4]]), et donc pour remplir le contrat, ils doivent avoir des codes de hachage égaux. Ok. Pourtant, il y a beaucoup plus de 15 000 valeurs possibles. Sa deuxième fonction de hachage proposée est beaucoup mieux, ce qui donne une gamme plus large.

Bien que, comme quelqu'un d'autre l'a commenté, il semble inapproprié qu'une fonction de hachage modifie d'autres données. Il serait il est plus logique de "normaliser" l'objet 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 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;

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

En outre, le premier brouillon à une fonction de hachage a plusieurs calculs qui ne font rien pour ajouter à la gamme de 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. Si ... en effet, il ajoute 503*5381 à chaque valeur. Qu'est-ce accomplir? L'ajout d'une constante à chaque valeur de hachage brûle simplement les cycles cpu sans rien accomplir d'utile. Leçon ici: Ajouter de la complexité à une fonction de hachage n'est pas le but. L'objectif est d'obtenir un large éventail de valeurs différentes, pas seulement d'ajouter de la complexité pour le bien de la complexité.

Ma première idée est de m'assurer que vous initialisez votre HashMap de manière appropriée. De la JavaDocs pour HashMap:

Une instance de HashMap a deux paramètres qui affectent ses performances: capacité initiale et facteur de charge. La capacité est le nombre de compartiments dans la table de hachage, et la capacité initiale est tout simplement la capacité au moment de la table de hachage est créé. Le facteur de charge est une mesure de la capacité de la table de hachage avant sa capacité automatiquement augmenté. 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 rabattue (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, alors chaque fois qu'il a besoin de redimensionner, tous les les hachages sont recalculés... ce qui pourrait être ce que vous ressentez quand vous arrivez aux 2-3 millions point d'insertion.

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 objet ne calcule sa valeur de hachage qu'une seule fois.

3. Utilisez un meilleur algorithme de hachage. Celui que vous avez posté retournerait le même hachage où a = {0, 1} comme il le ferait où a ={1, 0}, Tout le reste étant égal.

Utilisez ce que Java vous donne gratuitement.

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

Je suis 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 de "on/off topic", mais nécessaire pour éliminer la confusion concernant Oscar Reyes suggestion que plus de collisions de hachage est une bonne chose car elle réduit le nombre d'éléments dans le HashMap. Je peux mal comprendre ce Qu'Oscar dit, 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 cela une seule instance d'une classe avec un hashcode donné sera 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é.

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

Quelle que soit la compréhension ou l'incompréhension, ce qui se passe est différent les instances de la même classe nepas sont insérées une seule fois dans le HashMap si elles ont le même hashcode-pas tant qu'il n'est pas déterminé si les clés sont égales ou non. Le contrat hashcode exige que les objets égaux aient le même hashcode; cependant, il n'exige pas que les objets inégaux aient des hashcodes différents (bien que cela puisse être souhaitable pour d'autres raisons) [1].

Le pastebin.com/f20af40b9 exemple (auquel Oscar se réfère au moins deux fois) suit, mais modifié légèrement pour utiliser les assertions JUnit plutôt que printlines. Cet exemple est utilisé pour soutenir la proposition selon laquelle les mêmes hashcodes 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 pastebin néglige, c'est le fait que les deux s et ese sont égaux: ils sont tous deux la chaîne "ese". Ainsi, insérer ou obtenir le contenu de la carte en utilisant s ou ese ou "ese" comme la clé sont tous équivalents parce que s.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 -> 1 est écrasée par ese -> 2 Lorsque map.put(ese, 2) est appelée dans le premier test. Dans le deuxième test, s et ese ont toujours le même hashcode (comme vérifié par assertEquals(s.hashCode(), ese.hashCode());) et ils sont la même classe. Cependant, s et ese sont des instances MyString dans ce test, pas des instances Java String - avec la seule différence pertinent pour ce test étant les égaux: String s equals String ese dans le test Un ci-dessus, tandis que MyStrings s does not equal MyString ese dans 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 que l'égalité est ce qui compte, pas la "même classe" , n'est pas claire (emphase mienne):

"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 hashcode 2345 et et Integer donne le même hashcode 2345, puis l'entier est inséré dans la liste parce que la chaîne.equals( Entier ) est faux. Mais si vous avez la même classe ( ou au moins .renvoie true) alors la même entrée est utilisée. Par exemple, new String ("one") et `new String ("one") utilisés comme clés, utiliseront la même entrée. En fait, c'est tout le point de HashMap en premier lieu! Voyez par vous-même: pastebin.com/f20af40b9 -Oscar Reyes "

Par rapport aux commentaires précédents qui adressez explicitement l'importance de la classe identique et du même hashcode, sans mention d'égal à égal:

"@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ée et il n'y a pas de "liste" d'entrées. – Oscar De Los Reyes"

Ou

"en fait, cela augmenterait les performances. Le plus collisions eq moins d'entrées dans l'égaliseur hashtable. moins de travail à faire. N'est-ce pas le hachage (qui semble bien ) ni la table de hachage (qui fonctionne très bien ) je parie que c'est sur la création d'objet où la performance est dégradante. – Oscar De Los Reyes"

Ou

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

Encore une fois, je peux mal comprendre ce Qu'Oscar était réellement essaie de dire. Cependant, ses commentaires initiaux ont causé suffisamment de confusion qu'il semble prudent de tout éclaircir avec des tests explicites afin qu'il n'y ait pas de doutes persistants.

[1] - de Effective Java, Deuxième Édition {[30] } par Joshua Bloch:

• Chaque fois qu'il est appelé 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, fourni aucune information utilisée dans égal s des comparaisons sur les l'objet est modifié. 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 égale s (Obj ect), l'appel de la méthode hashCode sur chacun des deux objets doit produire la même chose résultat sous forme d'entier.

• Il n'est pas nécessaire que si deux objets sont inégaux selon la méthode s(Object) égale, alors appeler le hashCode méthode sur chacun des deux objets doit produire des résultats entiers distincts. Cependant, le programmeur devrait être conscient que la production de résultats entiers distincts pour des objets inégaux peut améliorer la performance des tables de hachage.

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

A[0] + a[1] sera toujours entre 0 et 512. l'ajout des b entraînera toujours un nombre compris entre 0 et 768. multipliez-les et vous obtenez une limite supérieure de 400 000 combinaisons uniques, en supposant que vos données sont parfaitement réparties entre 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 des objets sous-jacents.

Essayez de modifier les deux.

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

Exemple: Touches: 1,2,3,.... et 28 cartes de 1 million chacune. Carte d'indice de: 1-1, 000, 000 - > Map1 1 000 000-2 000 000 - > Map2

Donc, vous ferez deux recherches, mais le jeu de clés serait 1.000.000 vs 28.000.000. Vous pouvez facilement le faire avec des motifs de piqûre 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 dans la plage 0-51, uniques et l'ordre dans les tableaux a et b est insignifiant, mes calculs me disent qu'il n'y a qu'environ 26 millions de permutations possibles et que vous essayez probablement de remplir la carte avec des valeurs pour

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 discuté longuement dans d'autres messages, avec un bon hashCode (), 26m entrées dans une carte n'est pas une grosse affaire.
2. cependant, un problème potentiellement caché ici est l'impact GC des cartes géantes.

Je suppose que ces cartes sont de longue durée. c'est à dire vous les remplir et ils restent pour la durée de l'application. Je suppose également que l'application elle-même est longue durée de vie-comme un serveur quelconque.

Chaque l'entrée dans un HashMap Java nécessite trois objets: la clé, la valeur et l'entrée qui les lie ensemble. 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-le-monde. Le GC regardera chacun des objets 78M et déterminera qu'ils sont tous vivants. 78M + objects 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'atteindre toutes les garanties de latence que 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 se désabonnent rapidement, vous pouvez vous retrouver avec des collectes complètes fréquentes qui aggrave considérablement le problème.

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

• il est parfois possible de régler les tailles de GC et de tas pour" principalement " empêcher les GCs complets.
• si le contenu de votre carte désabonne beaucoup, vous pouvez essayer Javolution FastMap -- Il peut regrouper des objets D'Entrée, ce qui pourrait réduire la fréquence des collectes complètes
• vous pouvez créer votre propre map impl et gérer explicitement la mémoire sur byte [] (c'est-à-dire échanger le cpu 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 base de données prévisible en mémoire sur un socket
• espérons que le nouveau collecteur G1 aidera (s'applique principalement au taux de désabonnement élevé cas)

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

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

Dans mon cas, je veux créer une carte avec 26 millions d'entrées. En utilisant le HashMap Java 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 arbre noir rouge 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", mes données d'algorithme structure. Je pourrais construire un arbre / carte pour 10 millions de nœuds en 21.29 secondes (RAM: 1.97 Gb). Clé de recherche-le coût de la valeur est O (1).

Note: "Prime Tree" fonctionne le mieux sur les "clés continues" de 1 à 10 millions. Pour travailler avec des clés comme HashMap, nous avons besoin d'un ajustement mineur.

Alors, qu'est-ce que #PrimeTree? En bref, c'est une structure de données d'arbre comme L'arbre binaire, avec des nombres de branches sont des nombres premiers (au lieu de "2"-binaire).

SQLite vous permet de l'utiliser dans la 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, appartenant à Oracle now.

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

Vous devez d'abord vérifier que vous utilisez Map correctement, bonne méthode hashCode() pour les clés, capacité initiale pour la carte, bonne implémentation de la carte, etc. comme beaucoup d'autres réponses décrire.

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é. Est-ce que, par exemple, la méthode hashCode() est exécutée pour des milliards de fois?

Si cela ne fonctionne pas, que diriez-vous d'utiliser quelque chose comme EHCache ou memcached? Oui, ils sont produits pour la mise en cache, mais vous pouvez les configurer de sorte qu'ils auront une capacité suffisante et n'expulseront jamais de valeurs du stockage du 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 en valoir la peine.

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

Quelque Chose comme ceci:

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 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 ajoutez chaque clé 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 beaucoup de collisions en raison de la façon dont vous ajoutez des valeurs ensemble. Je suis prêt à l'être, 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 dans la plage 0..51, chacune de ces valeurs 6 bits pour représenter. Si vous avez toujours 5 valeurs, vous pouvez créer un hashcode 30 bits avec gauche-changements et 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 vers la gauche est rapide, mais vous laissera des hashcodes qui ne sont pas répartis uniformément (car 6 bits implique une plage 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'equals aideront.

Si vous avez besoin d'optimiser encore plus:

Par votre description, il n'y a que (52 * 51 / 2) * (52 * 51 * 50 / 6) = 29304600 différentes clés (dont 26000000, soit environ 90%, seront présentes). Par conséquent, vous pouvez concevoir une fonction de hachage sans aucune collision, et utiliser un simple tableau plutôt qu'un hashmap pour contenir vos données, réduisant la consommation de mémoire et augmentant 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 regroupe bien, c'est pourquoi un HashMap tolère les collisions, ce qui entraîne une surcharge)

En supposant que a et b sont 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 mathématiquement incliné.

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 séparé. C'est, calculer un code de hachage pour chaque élément en appliquant ces règles récursivement, et combinent ces valeurs par étape 2.b. Si tous les élément dans un champ de tableau est significatif, vous pouvez utiliser l'un des Tableau.hashCode méthodes ajoutées dans la version 1.5.

Allouer 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 un new HashMap(30000000).

Êtes-vous sûr que vous avez assez de mémoire pour 26 millions d'entrées avec 26 millions de clés et de valeurs? Cela ressemble à beaucoup de mémoire pour moi. Êtes-vous sûr que la collecte des ordures se porte toujours bien à votre marque de 2 à 3 millions? Je pourrais imaginer cela comme un goulot d'étranglement.

Vous pouvez essayer deux choses:

• Faites en sorte que votre méthode hashCode renvoie quelque chose de plus simple et plus efficace, comme un int consécutif

• Initialisez votre carte comme:

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

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

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

Modifier

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

Voir à partir de la javadocs:

si la capacité initiale est supérieure au nombre maximal d'entrées divisé par le facteur de charge, aucune opération de ressaisissement ne se produira jamais.

J'ai fait un microbeachmark (qui n'est pas 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
$

Donc, en utilisant le la capacité initiale passe de 21s à 16s en raison du rehasing. Cela nous laisse avec votre méthode hashCode comme une "zone d'opportunité";)

Modifier

N'est pas le HashMap

Selon votre dernière édition.

Je pense que vous devriez vraiment profiler votre application et voir où la mémoire / cpu 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 est considérablement réduit.

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 objets 26M que vous pensez mais un nombre beaucoup plus faible (environ 20k je dirais) donc:

Les problèmes N'est pas le HASHMAP est ailleurs dans votre code.

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

Voici ma mise en œuvre de votre classe.

Note Je n'ai pas utilisé une plage 0-51 comme vous l'avez fait mais -126 à 127 pour mes valeurs et admet répété, c'est parce que j'ai fait ce test avant de mettre à 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 );

Me donne:

real     0m11.188s
user     0m10.784s
sys 0m0.261s


real     0m9.348s
user     0m9.071s
sys  0m0.161s

Peut-être essayer d'utiliser si vous avez besoin qu'il soit 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 vs un hashmap, la chose amusante était d'itérer dans la liste et de trouver l'objet prenait le même temps en millisecondes que d'utiliser la fonction get HashMaps... juste un avis. 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 est d'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)