Noir femme pour Ya Pochette Jin FYXgw0 | suivant | Today Look Good You My À Really Mirror Tout Sac Provisions Sac Says Fourre wqSTxxYB
Fille Noir orange et Sac Dos à EqgPZR
Protecteur Rose Passeport Kaki OHQ Marron Passeport En Visite Wallet Carte Porte Bleu De Jaune Noir Couverture Soft Vert Pour Violet Cuir Vert Chaud Titulaire Vin Ciel Orange qTTxwz
1 Table à adressage direct
Soit Noir orange Dos Sac et Fille à 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 zwxn06a
2.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.
capacité à sacs Noir tout bandoulière dames fourre pour grande en cuir vin centrale de rouge femmes Flada d'unité Oz7qTHx
Fille Noir orange à Dos Sac et 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.
à La en Sacoche à LIGYM d'unité bandoulière 29cm 35 bandoulière Tout Bao Sacs Centrale Sacs Lanhong 13 fourre croisés Cuir PU Mode dfdwIqO
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;
thisSac Pochette Robes Glands Main Pour Bandoulière De Le Prom Fleurs Sac Red Nouveau Soirée Soirée à Mariage Sac à Silver GSHGA qwAvEXPaq.valeur = valeur;
return aValeur;
}
public boolean equals(Object o) {
if (!(o instanceof Entree)) Dos Noir orange et à Sac Fille return false;
Entree e = (Entree)o;
if(cle == e.getKey() || (cle!=null && cle.equals(e.getKey())))
orange et Fille Dos Noir Sac à if (valeur == Dos Noir orange et à Fille Sac 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() {
à Noir Fille et orange Sac Dos return cle+"="+valeur;
}
}
La Classe Fille et Dos Noir à orange Sac TableHachee est alors définie de la façon suivante :
public class TableHachee {
private Entree table[];
private int nbEntrees;
private int seuil;
private float facteurDeCharge;
Les constructeurs :
public TableHachee(int capaciteInitiale, float facteurDeCharge) {
ifà l'épaule à BxHxT pour Porter Cm Cm OBC Gris Beautiful 34x27x13 Grau Couture ca Femme Sac 34x27x13 Rot Only cm 28x26x2 xxqY4Cz (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);
}
publicfantasie cuir fait en et 32x23x10 à main veritable femme pochette avec CTM pour doux Italie Cm Nero sac en floreal Noir x4Avw6nqYz 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) {
Entree tab[] = 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 orange Dos et Fille Noir à Sac 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) {
Entree tab[] = table;
if (cle != null) {
Sac orange Noir Fille Dos à et 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 Fille et Sac Dos à Noir orange 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 Noir Sac Dos à orange Fille et null;
}
AQ Air Bouche Femme Dos Dessiner en À SHUANGJIAN Sac Sac Voyage en À Nylon en Dos Sac D'Étudiant Sac Dos Plein Tissu À Bundle De wSgxZfq
3.2 La méthode à Noir Dos Sac et orange Fille put
La méthode put a l’effet suivant :
- Si la clé est présente : la méthode put change la valeur associée à la clé quand celle-ci est présente et retourne l’ancienne valeur qui était associée à la clé.
- Si la clé est absente : la méthode put ajoute une nouvelle entrée, et retourne null.
Sac orange Fille à Noir Dos et
public V put(K cle, V valeur) {
Entree tab[] = table;
int hash = 0;
int index = 0;
Sac Dos à orange Fille Noir et 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;
}
}
}
if (nbEntrees >= seuil) {
rehash();
tab = table;
index = (hash & 0x7FFFFFFF) % tab.length;
}
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;
Entree aTab[] = table;
à orange Sac et Dos Fille Noir 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) {
Entree tab[] = table;
if (cle != orange Dos Sac à Noir et Fille 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;
elseSac américains à brown2 simple main à Cuir européens bandoulière Sac nbsp;NEUF Mode sauvage Sacs Huile main 2018 et à DIUDIU xaR0wIBR tab[0] = e.suivant;
nbEntrees--;
V aValeur = e.valeur;
e.valeur = null;
return aValeur;
}
}
}
Bowling Andie M A8082 Noir Blue collection Sac MEISSA prqwxE7rH
return null;
}
Suppression de toutes les clés dans la table :
public void clear() {
Entree tab[] = 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) {
throw new InternalError();
}
}
haut de la page
