Les collections

Rappel sur les différentes interfaces, classes concrètes consacrées aux collections et la façon de les employer.

Les Interfaces

  • File d’attente :
  • Les tableaux circulaires (CircularArrayQueue) sont plus efficaces que les listes chaînées (LinkedList). Leur contenu est cependant borné et leur capacité est limitée.

  • Les interfaces fondamentales :
  • Collection Principales implémentations : additeratorsize,isEmpty,containsequalsaddAllremoveremoveAll,clearretainAlltoArray
    Iterator Principales implémentations : nexthasNextremove
    AbstractCollection Possibilité de surcharger une Collection et d’utiliser les méthodes génériques sans avoir à les reprogrammer.

Les Listes

  • Les tableaux et les vecteurs :
  • L’emploi des tableaux (Array) et des vecteurs (Vector) consomme beaucoup de temps machine.
    Les listes chaînées ne subissent pas ce ralentissement.
    Un Vector a toutes ses méthodes synchronisées ce qui fait ralentir son exécution (tout comme Hashtable).

  • Interface ListIterator :
  • Etend Iterator avec la gestion de l’ajout de données triées.
    addprevioushasPreviousset (remplacement de valeur)
    Attention : un remove après un next supprime l’élément de gauche. Un remove après un previous supprime l’élément de droite. Deux remove successifs ne peuvent se faire.
    Deux itérateurs sur une même liste peuvent exister et déclencher uneConcurrentModificationException.
    Il est préférable d’utiliser n itérateurs sur des vues de la liste, et un seul itérateur modificateur.
    L’appel à set ne déclenchera pas d’exception, la taille de la liste est préservée.
    LinkedList.get(indice) est possible mais non adapté (parcours séquentiel de la liste). Préférer un ArrayList.

Les Sets et les Tables de Hashage

  • Méthode de stockage :
  • Calcul de la clef par sceau. Nombre de sceaux optimisé à 150% du nombre de valeurs et si possible en nombre premier.
    Facteur de charge optimisé à 75%. Ces deux paramètres peuvent être définis dans le constructeur.
    Par défaut, un HashSet a 101 sceaux et a un facteur de charge de 75%.

  • Accès aux valeurs par HashSet :
  • Parcours de la liste aléatoire.
    identifie les objets par code de hashage : le hashCode méthode de la classe Object. Par défaut, le hashCode est calculé en fonction de la place mémoire de l’objet. On peut donc avoir deux objets à contenu identique dans un HashSet.
    Utilise la méthode equals.

  • Accès aux valeurs par TreeSet :
  • Les éléments sont triés et l’accès n’est plus aléatoire.
    L’ajout est plus lent (log(n) comparaisons)
    Toujours définir un CompareTo ; (attention aux débordements sur des tests avec de grands nombres).
    Possibilité d’utiliser un Comparator pour comparer deux objets à la base non comparables, et les trier sur des critères particuliers.

  • Accès aux valeurs par HashMap, TreeMap :
  • keySet : énumère les clefs (crée une vue).
    entrySet : Enumère les couples de valeurs, collection de Map.Entry)

  • Les WeakHashMap :
  • Lorsque la clef est supprimée dans l’application, la valeur n’est plus récupérable.
    Cette valeur reste active. Le WeakHashMap travaille avec le GarbageCollector afin de supprimer toutes les entrées dont les clefs ne sont plus référencées.

Les classes les plus utilisées

Un ensemble de classes formant un outil de gestion, de contrôle optimisé des données s’appelle un Framework.

  • Quelques différences
  • L’ajout dans un Set n’est pas le même que dans une Collection (relation d’égalité et donc de remplacement) Pas de relation d’égalité défini pour les collections (ordre, égalité des éléments)

  • Quelques classes abstraites
  • AbstractCollection, AbstractList, AbstractSequentialList, AbstractSet, AbstractMap : Fournissent une vue (= un autre conteneur pour les mêmes éléments).

  • Quelques classes concrètes
  • LinkedList, ArrayList, HashSet, TreeSet, HashMap, TreeMap

  • Les classes appelées à disparaître
  • Vector, Stack, Hashtable, Properties, Dictionary

Vues synchronisées

  • Définition
  • Vue : Façon de représenter un ensemble de données, généralement accessible en lecture seule seulement. Le code est ainsi optimisé car on ne recrée pas de copie des objets. Une vue non modifiable déclenchera une UnsupportedException si on tente une modification.
    Vue synchronisée : Tout comme un Vector, il s’agit d’une vue dont toutes les méthodes sont synchronisées.

  • Créer une vue synchronisée
  • Par la classe Collections :

    Collections.synchronizedMap(hashMap)
    Collections.synchronizedList
    Collections.synchronizedSet
    Collections.synchronizedSortedSet
    Collections.synchronizedSortedMap
    

    Renvoie un wrapper : un emballage. A utiliser préférablement lors de la création de l’objet (en même temps que l’argument).
    Un wrapper emballe une interface et l’ensemble de ses méthodes (et uniquement celles-ci).
    un synchronized{} sur un objet vérouille le conteneur.
    Attention : l’appel à Collections.synchronizedXXX cache l’emploi d’une méthode equals sous-jacente.

  • Vues non modifiables
  • Collections.unmodifiableList(liste)
    Collections.unmodifiableSet(liste)
    ...
    

    Arrays.asList fournit un wrapper de List et non un ArrayList. Vue non modifiable

Tableaux et Collections

  • Le clonage des données
  • Collections.nCopies(int n, Object) : Fournit une vue immuable (sous forme de List).
    Collections.singleton(Object) : Fournit un Set d’un élément unique immuable.

  • Les tableaux
  • tableau.toArray() ne permet pas de reconvertir proprement les types de données.
    Utiliser alors préférablement tableau.toArray(Type[ destination);

  • Les Collections
  • A noter : sortshufflereverseOrderenumerations
    binarySearch : permet une recherche dichotomique sur une liste préalablement triée. En cas d’élément recherché non trouvé, l’index d’insertion à prévoir vaut -i-1 (i=code de retour). Non adapté aux LinkedList (parcours séquentiel).
    minmaxcopy(from, to), reverse
    Les collections sont plutôt utilisées pour des parcours séquentiels (contrairement aux listes).

  • Quelques vieilleries
  • Properties : getsetload(sourceStream, nom), save. Etend Hashtable. Manque de contrôle sur les clefs, qui doivent être des chaînes de caractères.
    Stack : poppushpeek
    BitSet : Opérations sur des listes de booléens.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *