[JAVA] Comment utiliser un tableau pour la clé TreeMap

Dans Comment utiliser un tableau pour la clé de HashMap, il devrait être différent s'il s'agit de TreeMap, mais je n'ai pas pu le vérifier tout de suite, je l'ai donc divisé.

Hypothèses clés de TreeMap

Ici, il s'appelle TreeMap. HashMap est un peu différent. → Comment utiliser un tableau pour les clés HashMap L'hypothèse clé est

La première est que containsKey, get et put de TreeSet utilisent compareTo, donc à proprement parler, equals n'est peut-être pas nécessaire, mais c'est nécessaire. La seconde est que l'implémentation de Compareable signifie l'implémentation de compareTo. S'il ne peut pas être rendu comparable, préparez un comparateur séparé et transmettez-le au constructeur TreeMap. Le troisième n'est pas imuutable et peut être modifié ultérieurement, mais si vous modifiez la valeur de clé après l'avoir placée, il se peut qu'il ne soit pas trouvé. Ceci est implémenté dans un arbre bifurqué, donc si vous changez la clé de l'extérieur et que la droite ou la gauche est incorrecte, elle explosera.

La différence entre HashMap et TreeMap est de savoir si vous avez besoin d'un hashCode ou d'un compareTo. Si vous avez les deux, vous pouvez utiliser à la fois HashMap et TreeMap.

Résultats de array equals et hashCode

Si c'est un tableau, equals n'est pas correct, il n'implémente pas Comparable.

Main.java


    public static void main(String[] args) {
        byte[] b01 = { 1, 2, 3 };
        byte[] b02 = { 1, 2, 3 };
        System.out.println(b01 == b02);
        System.out.println(b01.equals(b02));
        System.out.println(Arrays.equals(b01, b02));
        //Comparable c = (Comparable)b01;
        TreeMap<byte[], String> map = new TreeMap<>();
        map.put(b01, "OK");
    }

Les casts commentés entraîneront une erreur de compilation. Quand tu cours ...

false
false
true
Exception in thread "main"
java.lang.ClassCastException: [B cannot be cast to java.lang.Comparable
    at java.util.TreeMap.compare(TreeMap.java:1290)
    at java.util.TreeMap.put(TreeMap.java:538)
    at Main.main(Main.java:15)

J'ai Arrays.equals, mais je dois me comparer à moi-même.

Partie 1: Utilisez ByteBuffer

Je me suis demandé qui avait implémenté Comparable en premier lieu, et quand j'ai grep, j'ai également implémenté le corps java.nio.Buffer.

Testons-le.

Main.java


    public static void main(String[] args) {
        byte[] b01 = { 1, 2, 3 };
        byte[] b02 = { 1, 2, 3 };
        ByteBuffer w01 = ByteBuffer.wrap(b01);
        ByteBuffer w02 = ByteBuffer.wrap(b02);
        Map<ByteBuffer, String> map = new TreeMap<>();
        map.put(w01, "OK");
        System.out.println(w01 == w02);
        System.out.println(w01.equals(w02));
        System.out.println(map.get(w01));
        System.out.println(map.get(w02));
    }

Quand tu cours ...

false
true
OK
OK

OK du tout. C'est la meilleure sensation. J'aime la bibliothèque standard ajoutée à partir de JDK 1.4.

Partie 2: Créer un ByteArrayWrapper

J'ose créer une classe qui encapsule l'octet []. J'ai utilisé ByteBuffer comme référence.

ByteArrayWrapper.java


import java.util.Arrays;

public class ByteArrayWrapper implements Comparable<ByteArrayWrapper> {
    private byte[] data;

    public ByteArrayWrapper(byte[] data) {
        this.data = data.clone();
    }

    public boolean equals(Object other) {
        if (other instanceof ByteArrayWrapper) {
            return Arrays.equals(data, ((ByteArrayWrapper) other).data);
        }
        return false;
    }

    public int compareTo(ByteArrayWrapper that) {
        int n = Math.min(this.data.length, that.data.length);
        for (int i = 0; i < n; i++) {
            int cmp = Byte.compare(this.data[i], that.data[i]);
            if (cmp != 0)
                return cmp;
        }
        return this.data.length - that.data.length;
    }
}

Testons-le.

Main.java


    public static void main(String[] args) {
        byte[] b01 = { 1, 2, 3 };
        byte[] b02 = { 1, 2, 3 };
        ByteArrayWrapper w01 = new ByteArrayWrapper(b01);
        ByteArrayWrapper w02 = new ByteArrayWrapper(b02);
        Map<ByteArrayWrapper, String> map = new TreeMap<>();
        map.put(w01, "OK");
        System.out.println(w01 == w02);
        System.out.println(w01.equals(w02));
        System.out.println(map.get(w01));
        System.out.println(map.get(w02));
    }

Le résultat est ···

false
true
OK
OK

Je clonage () cette fois sur la base de la leçon que j'ai apprise de HashMap, mais ça va probablement.

Wrapper ByteArray modifié

(1/18 postscript) J'ai essayé de le réparer en changeant l'argument du constructeur d'octet [] en octet ... (argument de longueur variable) dans le commentaire.

ByteArrayWrapper.java


import java.util.Arrays;

public class ByteArrayWrapper implements Comparable<ByteArrayWrapper> {
    private byte[] data;

    public ByteArrayWrapper(byte... data) {
        this.data = data.clone();
    }

    public boolean equals(Object other) {
        if (other instanceof ByteArrayWrapper) {
            return Arrays.equals(data, ((ByteArrayWrapper) other).data);
        }
        return false;
    }
    
    public int compareTo(ByteArrayWrapper that) {
        int n = Math.min(this.data.length, that.data.length);
        for (int i = 0; i < n; i++) {
            int cmp = Byte.compare(this.data[i], that.data[i]);
            if (cmp != 0)
                return cmp;
        }
        return this.data.length - that.data.length;
    }
}

Vous pouvez transmettre le tableau comme précédemment, ou vous pouvez le transmettre en tant que ByteArrayWrapper (1, 2, 3). C'était censé l'être, mais il n'y avait pas beaucoup de mérite dans le type d'octet car il nécessitait un cast. Avec le type int et le type long, vous pouvez créer une instance sans cast et sans préparer de tableau.

Main.java


    public static void main(String[] args) {
        byte[] b01 = { 1, 2, 3 };
        ByteArrayWrapper w01 = new ByteArrayWrapper(b01);
        ByteArrayWrapper w02 = new ByteArrayWrapper((byte)1, (byte)2, (byte)3);
        Map<ByteArrayWrapper, String> map1 = new HashMap<>();
        map1.put(w01, "OK");
        Map<ByteArrayWrapper, String> map2 = new TreeMap<>();
        map2.put(w01, "OK");
        System.out.println(map1.get(w01));
        System.out.println(map1.get(w02));
        System.out.println(map2.get(w01));
        System.out.println(map2.get(w02));
    }

Partie 3: Utilisez BigInteger → Non

java.math.BigInteger est également comparable, mais il ne peut pas être utilisé car {0, 100} devient {100}.

Partie 4: Conversion en chaîne de caractères → Pas efficace

Ce serait bien si HashMap était unique, mais TreeMap a une relation de taille, il n'y a donc pas d'autre choix que de faire de la valeur numérique une longueur fixe. S'il n'y a pas assez de chiffres, appuyez sur 0 vers la gauche.

Partie 5: Passer le comparateur à TreeMap

(1/18 postscript) Au début, j'ai écrit que "Comparable est implémenté ou Passer Comparer à TreeMap", et je n'ai fait que l'exemple de Comparable, donc j'ai fait un exemple de Comparer en plus.

La partie 1 à la partie 3 est une méthode pour implémenter et réaliser Comparable qui encapsule l'octet []. Le cinquième est le cas de la préparation d'une autre méthode, Comparator.

C'est presque la même chose que compareTo de ByteArrayWrapper, mais crée ByteArrayComparator.

ByteArrayComparator.java


import java.util.Comparator;

public class ByteArrayComparator implements Comparator<byte[]> {
    public int compare(byte[] o1, byte[] o2) {
        int n = Math.min(o1.length, o2.length);
        for (int i = 0; i < n; i++) {
            int cmp = Byte.compare(o1[i], o2[i]);
            if (cmp != 0)
                return cmp;
        }
        return o1.length - o2.length;
    }
}

Testons-le.

Main.java


    public static void main(String[] args) {
        byte[] b01 = { 1, 2, 3 };
        byte[] b02 = { 1, 2, 3 };
        Map<byte[], String> map = new TreeMap<>(new ByteArrayComparator());
        map.put(b01, "OK");
        System.out.println(map.get(b01));
        System.out.println(map.get(b02));
    }

Le résultat est ···

OK
OK

Peut-être que ça va.

finalement

Il a été confirmé que ByteArrayWrapper n'a pas besoin de hashCode dans TreeMap, mais il est généralement préférable d'implémenter les deux si vous le faites quand même. (1/18 postscript) J'ai changé l'argument du constructeur d'octet [] en octet ... (argument de longueur variable). Également ajouté égal (octet [] autre).

ByteArrayWrapper.java


import java.util.Arrays;

public class ByteArrayWrapper implements Comparable<ByteArrayWrapper> {
    private byte[] data;

    public ByteArrayWrapper(byte... data) {
        this.data = data.clone();
    }

    public boolean equals(Object other) {
        if (other instanceof ByteArrayWrapper) {
            return equals(((ByteArrayWrapper) other).data);
        }
        return false;
    }
    
    public boolean equals(byte[] other) {
        return Arrays.equals(data, other);
    }
    
    public int hashCode() {
        return Arrays.hashCode(data);
    }

    public int compareTo(ByteArrayWrapper that) {
        int n = Math.min(this.data.length, that.data.length);
        for (int i = 0; i < n; i++) {
            int cmp = Byte.compare(this.data[i], that.data[i]);
            if (cmp != 0)
                return cmp;
        }
        return this.data.length - that.data.length;
    }
}

Main.java


    public static void main(String[] args) {
        byte[] b01 = { 1, 2, 3 };
        ByteArrayWrapper w01 = new ByteArrayWrapper(b01);
        ByteArrayWrapper w02 = new ByteArrayWrapper((byte)1, (byte)2, (byte)3);
        Map<ByteArrayWrapper, String> map1 = new HashMap<>();
        map1.put(w01, "OK");
        Map<ByteArrayWrapper, String> map2 = new TreeMap<>();
        map2.put(w01, "OK");
        System.out.println(map1.get(w01));
        System.out.println(map1.get(w02));
        System.out.println(map2.get(w01));
        System.out.println(map2.get(w02));
    }

Quand je teste ...

OK
OK
OK
OK

Recommended Posts

Comment utiliser un tableau pour la clé TreeMap
Comment utiliser un tableau pour les clés HashMap
Comment créer des pages pour le tableau "kaminari"
[Java] Comment transformer un tableau à deux dimensions avec une instruction for étendue
Comment faire une méthode de jugement pour rechercher n'importe quel caractère dans le tableau
Comment créer un tableau Java
Comment changer une chaîne dans un tableau en un nombre dans Ruby
Comment générer des valeurs de tableau sans utiliser d'instruction for
Comment utiliser binding.pry pour afficher le fichier
Comment ajouter un nouveau hachage / tableau
Comment créer un référentiel Maven pour 2020
[Ruby] Comment utiliser slice pour les débutants
[Java] Comment rechercher des valeurs dans un tableau (ou une liste) avec la méthode contains
[Pour les débutants Rails] Résumé de l'utilisation de RSpec (obtenir un aperçu)
[Java] [Pour les débutants] Comment insérer des éléments directement dans un tableau à deux dimensions
Comment créer une base de données H2 n'importe où
Comment créer un JRE léger pour la distribution
Comment générer une clé primaire à l'aide de @GeneratedValue
[Pour les super débutants] Comment utiliser l'autofocus: vrai
Comment utiliser Map
Comment utiliser rbenv
Comment utiliser with_option
Comment utiliser fields_for
Comment utiliser java.util.logging
Comment utiliser la carte
Comment utiliser collection_select
Comment utiliser Twitter4J
Comment utiliser active_hash! !!
Comment utiliser MapStruct
Comment utiliser TreeSet
[Comment utiliser l'étiquette]
Comment utiliser l'identité
Comment utiliser le hachage
Comment utiliser Dozer.mapper
Comment utiliser Gradle
Comment utiliser org.immutables
Comment utiliser java.util.stream.Collector
Comment utiliser VisualVM
Comment utiliser Map
[Java] Comment convertir un élément d'un tableau de type String en type Int
Comment écrire un test unitaire pour Spring Boot 2
Comment écrire pour appliquer Gem Pagy (pagination) à un tableau
[Spring Boot] Comment créer un projet (pour les débutants)
Comment sortir le standard d'un tableau avec for Each
Comment utiliser Truth (bibliothèque d'assertions pour Java / Android)
[Pour ceux qui créent des portfolios] Comment utiliser font-awesome-rails
Comment convertir un fichier en tableau d'octets en Java
Comment faire un MOD pour Slay the Spire
Comment utiliser GitHub pour les super débutants (développement d'équipe)
[Java] Comment utiliser Map