datastructures.adoc

Structures de données en Java

Structure de données

A data structure is a particular way of organizing data in a computer so that it can be used efficiently

— Wikipedia
https://en.wikipedia.org/wiki/Data_structure

Quelques structures de données Java

• Tableau

• Liste

• Set

• Dictionnaire

Tableau

• Taille fixe

• Eléments stockés de manière continue en mémoire

!

int[] a0;
int[] a1 = new int[2];
int[] a2 = { 1, 2, 3 };
int a3[] = { 1, 2, 3 };
Object[] a4 = { new Object(), Boolean.TRUE, 1 };
int[][] a5 = new int[3][3];

Accès

• Accès à un élément par son index

  • Opérateur []

  • ArrayIndexOutOfBoundsException si l’index n’existe pas

• Accès à la taille

  • Attribut length

!

int[] a = { 1, 2, 3 };
int first = a[0];
int size = a.length;

int[] b = new int[3];
b[0] = 1;
b[2] = 3;

java.util.Arrays

• Recherche d’élément

• Test d’égalité

• Tri

• Remplissage

• Copie

• etc.

Liste

Collection ordonnée d’éléments

!

Iterator

• Permet le parcours séquentiel des éléments d’une collection

• Concept similaire à celui de curseur

!

List list = Arrays.asList("apple", "orange", "pear");
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
    Object o = iterator.next();
    String s = (String) o;
    // Do something with s
}

For-each

• Pour les classes qui implémentent Iterable

List list = Arrays.asList("apple", "orange", "pear");
for (Object o : list) {
    String s = (String) o;
    // Do something with s
}

Implémentations de List

Implémentations de List

ArrayList

Basée sur un tableau

LinkedList

Basée sur des noeuds liés parcourables dans les deux sens

Liste doublement chaînée

Ajout d’un élément en fin de liste

Ajout d’élément

Complexité algorithmique

La théorie de la complexité est un domaine des mathématiques qui étudie formellement la quantité de ressources (temps et/ou espace mémoire) nécessaire pour résoudre un problème algorithmique au moyen de l’exécution d’un algorithme.

— Wikipedia
http://bit.ly/2wdY0fF

!

http://bigocheatsheet.com/#data-structures

Liste basée sur un tableau

Ajout d’un élément en fin de liste

Ajout d’élément

Tri

A sorting algorithm is an algorithm that puts elements of a list in a certain order.

— Wikipedia
https://en.wikipedia.org/wiki/Sorting_algorithm

Ordre

• Ordre "naturel" des éléments

• Ordre explicite

!

Quel algorithme de tri ?

• Dépend du JRE

• Tim Sort

!

http://bigocheatsheet.com/#sorting

Comparable

Compare l’objet courant this avec un autre objet that et retourne :

• Un entier négatif si this < that

• Un entier positif si this > that

• 0 si this = that

Classes comparables

• String

• Number (Integer, Float, etc.)

• Date

• File

• etc.

Comparateur

Compare deux arguments x et y et retourne :

• Un entier négatif si x < y

• Un entier positif si x > y

• 0 si x = y

Comparateur d’entiers

public class IntegerComparator implements Comparator {

  @Override
  public int compare(Object x, Object y) {
    if (!(x instanceof Integer)) {
      throw new IllegalArgumentException("x must be an int");
    }
    if (!(y instanceof Integer)) {
      throw new IllegalArgumentException("y must be an int");
    }
    int xInt = (Integer) x;
    int yInt = (Integer) y;
    return xInt - yInt;
  }
}

Set

Collection dé-doublonnée d’éléments

!

Exemple

Collection collection = Arrays.asList("One", "One", "Two");
Set set = new HashSet(collection);
System.out.println(set.size());

Un autre exemple

public class Wrapper {

    private final int id;

    public Wrapper(int id) {
        this.id = id;
    }
}

Collection collection = Arrays.asList(new Wrapper(1),
                                      new Wrapper(1),
                                      new Wrapper(2));
Set set = new HashSet(collection);
System.out.println(set.size());

Définition de doublon

Deux objets a et b sont considérés des doublons si a.equals(b)

Méthode equals

Reflexive	∀ x != null, x.equals(x) == true
Symmetric	∀ x, y != null, x.equals(y) == true ⇔ y.equals(x) == true

!

Transitive	∀ x, y, z != null, x.equals(y) == true AND y.equals(z) == true ⇒ x.equals(z) == true
Consistent
Null	∀ x != null, x.equals(null) == false

Application

Object a = new Object();
Object b = new Object();
System.out.println(a == a);
System.out.println(a == b);
System.out.println(a.equals(a));
System.out.println(a.equals(b));

Cas particulier des String

String one1 = "One";
String one2 = "One";
String two = "Two";
System.out.println(one1 == one1);
System.out.println(one1 == one2);
System.out.println(one1 == two);
System.out.println(one1.equals(one1));
System.out.println(one1.equals(one2));
System.out.println(one1.equals(two));

Implémentation d’equals()

public class Wrapper { // Attribute & constructor

 @Override
 public boolean equals(Object o) {
  return o instanceof Wrapper && this.id == ((Wrapper) o).id;
 }
}

Wrapper w1 = new Wrapper(1);
Wrapper w11 = new Wrapper(1);
Wrapper w2 = new Wrapper(2);
System.out.println(w1.equals(w1));
System.out.println(w1.equals(w11));
System.out.println(w1.equals(w2));

Et avec le set ?

Collection collection = Arrays.asList(new Wrapper(1),
                                      new Wrapper(1),
                                      new Wrapper(2));
Set set = new HashSet(collection);
System.out.println(set.size());

Méthode hashCode()

• Consistent (during the same run of the JVM)

• a.equals(b) ⇒
  a.hashCode() == b.hashCode()

Implémentation d’hashCode()

public class Wrapper { // Attribute & constructor

 @Override public int hashCode() { return this.id; }

 @Override
 public boolean equals(Object o) {
  return o instanceof Wrapper && this.id == ((Wrapper) o).id;
 }
}

Collection coll = Arrays.asList(
    new Wrapper(1), new Wrapper(1), new Wrapper(2));
Set set = new HashSet(coll);
System.out.println(set.size());

Dictionnaire

Un dictionnaire est une structure de données associant à un ensemble de clefs un ensemble correspondant de valeurs. Chaque clef est associée à une valeur.

— https://fr.wikipedia.org/wiki/Tableau_associatif

!

!

Hash Map

Capacité initiale & facteur de chargement