Comment puis-je définir un bon hashcode pour une liste liée circulaire en Java?

Donc, vous voulez un calcul de hashcode qui donne des résultats égaux pour "image" et "Turepic", mais (de préférence) différent du hachemode de par exemple. "Éruptic". Ainsi, il ne suffit pas de simplement ajouter les Hashcodes des lettres contenues dans le mot - vous devez également avoir des informations de position aussi, mais pourtant, il devrait être indépendant de la permutation réelle du mot. Vous devez définir des "classes d'équivalence" et calculer toujours le même hashcode pour chaque membre de la classe.

Le moyen le plus simple d'y parvenir est de sélectionner Sélectionner un membre spécifique de la classe d'équivalence et d'utiliser toujours le hashcode de cette variation pour tous les mots équivalents forts>. Par exemple. Sélectionnez la première variante alphabétiquement (merci à @Michael pour la résumer de manière concise). Pour "Photo" et al., Ce serait "Ctutrypi". "Picture" et "Turepic" (et toutes les autres variations équivalentes) doivent renvoyer le code de hachage de "Ctutrypi". Ce code de hachage pourrait être calculé par la méthode linkedlist standard, ou toute autre manière préférée. P>

On pourrait dire que ce calcul est très coûteux. TRUE, mais on pourrait cacher le résultat, de sorte que seul le premier calcul serait coûteux. Et je suppose que la sélection de la première variante alphabétique pourrait être optimisée assez bien dans le cas commun (par rapport à la solution triviale de générer toutes les permutations dans la classe d'équivalence spécifique, puis de les trier et de choisir le premier). P>

Par exemple Dans beaucoup de mots, la première lettre alphabétique est unique ("image" en est l'une d'entre elles - sa première lettre alphabétiquement est "C", et il n'y en a qu'un "C"). Vous n'avez donc besoin que de le trouver, puis calculez le hashcode à partir de là. Si ce n'est pas unique, vous devez comparer le deuxième, troisième, etc. Lettres après cela, jusqu'à ce que vous trouviez une différence (ou que vous vous relancez). P>

Mise à jour 2 - Exemples Strong > p>

• "Abracadabra" contient 5 'A. Les 2e personnages après les "A sont" B "," C "," D "," B "et" A ", respectivement. Donc, dans la 2e manche de comparaison, vous pouvez conclure que la variation de lexicographiquement la plus petite est "AABRACADABR". LI>
• "abab" contient 2 'A, et un "B" après chacun (et ensuite vous roulez, atteignant un "A" à nouveau, alors la quête se termine là-bas). Vous avez donc deux variantes identiques les plus petites lexicographiquement de celle-ci. Mais comme ils sont identiques, ils produisent évidemment le même hashcode. Li> ul>

  mise à jour: strong> à la fin, tout se résume à quel point avez-vous besoin du hashcode - c'est-à-dire que vous envisagez de mettre vos listes circulaires dans une collection associative comme Définir code> ou mappe code>. Sinon, vous pouvez faire avec une méthode de hachage simple ou même triviale. Mais si vous utilisez fortement une collection associative, une implémentation de hachage triviale vous offre de nombreuses collisions, ainsi que des performances sous-optimales. Dans ce cas, il vaut la peine d'essayer de mettre en œuvre cette méthode de hachage et de mesurer si elle paie elle-même en performance. P>

  Mise à jour 3: code d'échantillon h3>

  lettre code> est fondamentalement laissé la même chose que ci-dessus, je n'ai fait que les champs privés code>, renommé antextnode code> à suivant code> et ajouté getters / setters au besoin.

  dans de la circulaire code> J'ai fait plus de modifications: déposé queue code> et thecurrentnode code> et a fait le mot vraiment circulaire (c.-à-d. last.next == tête code>). Le constructeur, tostring code> et est égal à code> ne sont pas pertinents pour calculer le hashcode, ils sont donc omis pour le souci de simplicité. P>

  public class CircularWord {
      private final Letter head;
      private final int numberOfElements;
      
      // constructor, toString(), equals() omitted
  
      @Override
      public int hashCode() {
          return hashCodeStartingFrom(getStartOfSmallestRotation());
      }
  
      private Letter getStartOfSmallestRotation() {
          if (head == null) {
              return null;
          }
          Set<Letter> candidates = allLetters();
          int counter = numberOfElements;
  
          while (candidates.size() > 1 && counter > 0) {
              candidates = selectSmallestSuccessors(candidates);
              counter--;
          }
          return rollOverToStart(counter, candidates.iterator().next());
      }
  
      private Set<Letter> allLetters() {
          Set<Letter> letters = new LinkedHashSet<Letter>();
          Letter letter = head;
  
          for (int i = 0; i < numberOfElements; i++) {
              letters.add(letter);
              letter = letter.getNext();
          }
          return letters;
      }
  
      private Set<Letter> selectSmallestSuccessors(Set<Letter> candidates) {
          Set<Letter> smallestSuccessors = new LinkedHashSet<Letter>();
  
          char min = Character.MAX_VALUE;
          for (Letter letter : candidates) {
              Letter nextLetter = letter.getNext();
              if (nextLetter.getValue() < min) {
                  min = nextLetter.getValue();
                  smallestSuccessors.clear();
              }
              if (nextLetter.getValue() == min) {
                  smallestSuccessors.add(nextLetter);
              }
          }
          return smallestSuccessors;
      }
  
      private Letter rollOverToStart(int counter, Letter lastCandidate) {
          for (; counter >= 0; counter--) {
              lastCandidate = lastCandidate.getNext();
          }
          return lastCandidate;
      }
  
      private int hashCodeStartingFrom(Letter startFrom) {
          int hash = 0;
          Letter letter = startFrom;
          for (int i = 0; i < numberOfElements; i++) {
              hash = 31 * hash + letter.getValue();
              letter = letter.getNext();
          }
          return hash;
      }
  
  }