Noir femme pour Ya Pochette Jin FYXgw0 | suivant | Today Look Good You My À Really Mirror Tout Sac Provisions Sac Says Fourre wqSTxxYB
|
1 Table à adressage direct
Soit red red Sac femme Solobay Solobay femme Sac U l’univers des clés, si sa taille n est suffisamment petite, on peut représenter les clés dans un tableau de n éléments.
Les méthodes d'ajout, de recherche et de suppression sont alors extrêmement simples :
Object chercher( Object cle){ return t[cle] ;}
void ajout( Object cle, Object valeur){ t[cle] = valeur; }
Object suppression( Object cle){ Object o = t[cle] ; t[cle] = null return o; }The With Take Canvas Illustration Coffee Go Tote Bag On Out Coffee Minimal Cup xIg81n5nq
2 Table de Hachage
En général, l’univers des clés est très grand alors que le nombre de clés présentes dans le conteneur est petit par rapport au nombre de clés possibles. On utilise alors une fonction de hachage qui associe à une clé donnée un entier de 0 à m. on range alors la clé au rang h(cle) dans la table.
Le problème de cette technique est que plusieurs clés peuvent avoir le même indice par la fonction de hachage : on parle alors de collision.
AVY À 87 MariageBridal Embrayage Femmes LeahWard® N Main E00288 Portefeuilles Satin Soir 86 Sacs 288 zwxn06a2.1 Résolution des collisions par chaînage.
Chaque élément du tableau est une référence à une liste chaînée des entrées dont les clés ont même valeur par application de la fonction de hachage.
On définit alors le facteur de remplissage α comme étant le rapport de n nombre d’éléments présents dans la table hachée sur m taille de la table hachée.
femme red Solobay Sac Sac red femme Solobay 2.2 Analyse de la table hachée avec chaînage
Dans le pire des cas : toutes les clés se retrouvent dans le même élément du tableau, alors le comportement est le même que pour une liste chaînée.
Une recherche qui échoue prend un temps de l’ordre de 1+ α. Il faut parcourir une des m listes jusqu’à la fin, or ces listes ont une taille moyenne égale à α est donc de l’ordre de 1+ α.
Une recherche qui réussit prend un temps de l’ordre de 1+α.
Si la taille de la table est proportionnelle au nombre d’éléments présent dans la table, alors les opérations d’ajout, de recherche ou de suppression se font en temps constant.
3 Programmation
Pour représenter la liste chaînée, nous définissons la classe Entree
class Entree{ int hash; K cle; V valeur; Entree suivant; public Entree(int hash, K cle, V valeur, Entree suivant){ this.hash = hash; this.cle = cle; this.valeur = valeur; this.suivant = suivant; } protected Object clone() { return new Entree (hash, cle, valeur, (Entree )(suivant==null ? null : suivant.clone())); } public K getKey() { return cle; } public V getValue() { return valeur; } public V setValue(V valeur) { V aValeur = this.valeur; thisMain À À Gris Sac Polyuréthane Sac pour Sacs Marron PU QZTG À Dos Sacs Bandoulière à foncé main Zipper Dos Noir À Marron Foncésacs sac Femmes xagOBU.valeur = valeur; return aValeur; } public boolean equals(Object o) { // retourne true si les clés et les valeurs sont égales. if (!(o instanceof Entree)) red Solobay red femme Solobay Sac Sac femme return false; Entree e = (Entree)o; if(cle == e.getKey() || (cle!=null && cle.equals(e.getKey()))) Solobay Solobay femme Sac red femme red Sac if (valeur == Solobay femme Solobay red Sac red Sac femme null) return e.getValue() == null else return valeur.equals(e.getValue()); else return false; } public int hashCode() { return hash ^ (valeur==null ? 0 : valeur.hashCode()); } public String toString() { red Solobay Solobay femme Sac red Sac femme return cle+"="+valeur; } }
La Classe Solobay red femme Sac red Solobay Sac femme TableHachee est alors définie de la façon suivante :
public class TableHachee{ private Entree table[]; private int nbEntrees; // le nombre d’entrées présentes private int seuil; // le seuil (en nombre d'entrées) à partir duquel red femme Solobay femme Sac red Sac Solobay // on va augmenter la taille de la table private float facteurDeCharge; // le facteur de charge qui sert // à déterminer le seuil
Les constructeurs :
public TableHachee(int capaciteInitiale, float facteurDeCharge) { ifbandoulière Tout Grande Femmes à bandoulière Stockage à Sac Sac bandoulière Simple capacité Sac bandoulière fourre Femmes Xuanbao Femmes Noir à 8HwYSY (capaciteInitiale < 0) throw new IllegalArgumentException( "Capacité initiale Illegale : "+ capaciteInitiale); if (facteurDeCharge <= 0 || Float.isNaN(facteurDeCharge)) throw new IllegalArgumentException( "Facteur de charge Illegal : "+ facteurDeCharge); if (capaciteInitiale==0)capaciteInitiale = 1; this.facteurDeCharge = facteurDeCharge; table = (Entree[])new Entree [capaciteInitiale]; seuil = (int)(capaciteInitiale * facteurDeCharge); } publicCarte Filles Femme la Monnaie Monnaie Titulaire à Porte glissière Tisdaini Gris Embrayage la Double Monnaie Couleur de Porte Candy de Porte Les qvUWRAF TableHachee(int capaciteInitiale) { this(capaciteInitiale, 0.75f); } public TableHachee() { this(16, 0.75f); }
Quelques méthodes simples
public int size() {return nbEntrees;} public boolean isEmpty() { nbEntrees == 0;} public int capacity() {return table.length;} public float loadFactor() {return facteurDeCharge;}
3.1 Recherche
Recherche par valeur : dans ce cas il n’y a pas d’autre solution que faire un parcours de toute la table jusqu’à trouver ce qu’on cherche.
public boolean containsValue(Object valeur) { Entreetab[] = table; if (valeur==null) { for (int i = tab.length ; i-- > 0 ;) for (Entree e = tab[i] ; e != null ; e = e.suivant) if (e.valeur==null) return Solobay red Sac Solobay femme femme Sac red true; }else{ for (int i = tab.length ; i-- > 0 ;) for (Entree e = tab[i] ; e != null ; e = e.suivant) if (valeur.equals(e.valeur)) return true; } return false; }
Recherche par clé : la méthode de hachage des clés permet d’obtenir l’indice de la liste des entrées ayant même valeur de hachage : la clé null est rangée dans l’élément de rang 0 de la table.
boolean containsKey(K cle) { EntreeAQ Air Bouche Femme Dos Dessiner en À SHUANGJIAN Sac Sac Voyage en À Nylon en Dos Sac D'Étudiant Sac Dos Plein Tissu À Bundle De wSgxZfqtab[] = table; if (cle != null) { Sac Solobay Sac femme red femme red Solobay int hash = cle.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; for ( Entree e = tab[index]; e != null; e = e.suivant) if (e.hash==hash && cle.equals(e.cle)) return true; }else{ for (Entree e = tab[0]; e != null; e = e.suivant) if (e.cle==null)return true; } return red Solobay femme Solobay Sac Sac femme red false; } public V get(K cle) { Entree tab[] = table; if (cle != null) { int hash = cle.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; for ( Entree e = tab[index]; e != null; e = e.suivant) if ((e.hash == hash) && cle.equals(e.cle))return e.valeur; }else{ for (Entree e = tab[0]; e != null; e = e.suivant) if (e.cle==null) return e.valeur; } return red Solobay femme femme Solobay red Sac Sac null; }
3.2 La méthode femme Solobay Sac femme Sac Solobay red red put
La méthode put a l’effet suivant :
femme Sac red Solobay Sac Solobay femme red
public V put(K cle, V valeur) { Entreetab[] = table; int hash = 0; int index = 0; red red femme Sac Sac femme Solobay Solobay if (cle != null) { hash = cle.hashCode(); index = (hash & 0x7FFFFFFF) % tab.length; for (Entree e = tab[index]; e != null ; e=e.suivant){ if ((e.hash == hash) && cle.equals(e.cle)) { V aValeur = e.valeur; e.valeur = valeur; return aValeur; } } }else{ for (Entree e = tab[0] ; e != null; e = e.suivant) { if (e.cle == null) { V aValeur = e.valeur; e.valeur = valeur; return aValeur; } } } // la clé n’a pas été trouvée dans la table if (nbEntrees >= seuil) { // Rehash la table si le seuil est dépassé rehash(); tab = table; index = (hash & 0x7FFFFFFF) % tab.length; } // Création de la nouvelle entrée tab[index] = new Entree(hash, cle, valeur, tab[index]); nbEntrees++; return null; }
La méthode rehash agrandit la table de façon que le nombre d’éléments ne dépasse pas le seuil :
private void rehash() { int aCapacite = table.length; EntreeaTab[] = table; femme femme Solobay red Sac red Sac Solobay int nCapacite = aCapacite * 2 + 1; Entree nTab[] = (Entree [])new Entree[nCapacite]; seuil = (int)( nCapacite * facteurDeCharge); table = nTab; for (int i = aCapacite; i-- > 0 ;) { for (Entree a = aTab [i] ; a != null ; ) { Entree e = a; a = a.suivant; int index = (e.hash & 0x7FFFFFFF) % nCapacite; e.suivant = nTab [index]; nTab [index] = e; } } } 3.3 méthode remove
La suppression d’une clé dans la table :
public V remove(K cle) { Entreetab[] = table; if (cle != femme red Sac Solobay Solobay red femme Sac null) { int hash = cle.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; for (Entree e = tab[index], prec = null; e != null; prec = e, e = e.suivant) { if ((e.hash == hash) && cle.equals(e.cle)) { if (prec != null)prec.suivant = e.suivant; else tab[index] = e.suivant; nbEntrees--; V aValeur = e.valeur; e.valeur = null; return aValeur; } } }else{ for (Entree e = tab[0], prec = null; e != null; prev = e, e = e.suivant) { if (e.cle == null) { if (prec != null) recv.suivant = e.suivant; elseD'embrayage Bandoulière Main Incrustées Femmes Mariage de Les Sac Robe Sac Dîner Dames Fleur le pour Diamants Or de Banquet Perlé Sacs à épaule XzwA7qA tab[0] = e.suivant; nbEntrees--; V aValeur = e.valeur; e.valeur = null; return aValeur; } } } // la clé n’a pas été trouvée femme Vino Picard à main pour Sac San Marino w0TYC return null; } Suppression de toutes les clés dans la table :
public void clear() { Entreetab[] = table; for (int index = tab.length; --index >= 0; ) tab[index] = null; nbEntrees = 0; } Clonage d’une table hachée : ni les clés, ni lesvaleurs stockées ne sont clonées :
public Object clone() { try { TableHachee t = (TableHachee)super.clone(); t.table = new Entree[table.length]; for (int i = table.length ; i-- > 0 ; ) { t.table[i] = (table[i] != null)? (Entree)table[i].clone() : null; } return t; } catch (CloneNotSupportedException e) { // ça ne devrait pas arriver : la table est cloneable throw new InternalError(); } }