Java

Différence entre les HashSet et les LinkedHashSet dans l'API Java

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : Différence entre les HashSet et les LinkedHashSet dans l'API Java

Giz

Je voudrais connaître la différence entre ces 2 structures de données : HashSet et LinkedHashSet.
Donc j'ai lu un peu les codes sources. Pour résumé :
- Un HashSet est une HashMap ayant comme clé et comme valeur le même objet. Les collisions sont gérées par des listes simplement chaînées.
- Un LinkedHashSet est une HashMap ayant comme clé et comme valeur le même objet. Les collisions sont gérées par des listes doublement chaînées. De plus, le parcours de la liste doublement chaîné est ordonné. C'est cet ordonnancement qui fait LA différence avec les HashSet...et c'est ce que je n'ai pas vraiment pigé (l'intérêt ? comment ça marche ?). Ils disent entre autre qu'il y a 2 types d'ordre : les "access order" et les "insertion order". Je n'ai pas compris le "access order"... citation des sources :

53 * In addition, this maintains a doubly-linked list which tracks either
54 * insertion or access order.
55 * <p>
56 *
57 * In insertion order, calling <code>put</code> adds the key to the end of
58 * traversal, unless the key was already in the map; changing traversal order
59 * requires removing and reinserting a key. On the other hand, in access
60 * order, all calls to <code>put</code> and <code>get</code> cause the
61 * accessed key to move to the end of the traversal list. Note that any
62 * accesses to the map's contents via its collection views and iterators do
63 * not affect the map's traversal order, since the collection views do not
64 * call <code>put</code> or <code>get</code>.
65 * <p>
66 *
67 * One of the nice features of tracking insertion order is that you can
68 * copy a hashtable, and regardless of the implementation of the original,
69 * produce the same results when iterating over the copy. This is possible
70 * without needing the overhead of <code>TreeMap</code>.
71 * <p>

Bref, quel est l'intérêt des LinkedHashSet et comment ça marche, comment c'est implementé ? dans quel cas les utiliser ? ... du hashing qui tient compte de l'ordre d'insertion .... c'est nouveau ça non ? :heink:

Publicité

Giz

Citation :

There are three non-abstract implementations of the Set interface: TreeSet, HashSet, and LinkedHashSet (new to J2SE 1.4). Set objects do not allow duplicates and are not required to maintain their objects in the order they are added. HashSet will maintain items in an order designed for fast lookup. LinkedHashSet will maintain the items in the order they are added while also maintaining a hash for fast lookup. TreeSet will maintain items in a sorted order.

On a donc bien de l'HashMap ordonnée ? :heink:

Citation :

New to J2SE 1.4, the LinkedHashSet class is used in exactly the same way as the HashSet class. It has no additional methods and has constructors that take identical parameters as the HashSet. The only difference is that the LinkedHashSet maintains the order of the items added to the Set. It does this by maintaining a doubly linked list containing the hash and the original order of the items. According to Sun, the LinkedHashSet should run nearly as fast as the HashSet.

la citation ci-dessus resqte encore floue...

Message édité par Giz le 27-11-2006 à 11:43:04

Giz

[:up]

Giz

:bounce:

---------------
Asus P5Q Pro | C2D E8400 3GHz@4GHz + Noctua NH-C12P | 2x2Go Patriot Extreme PC-8500 | GeForce GTX 460@Stock 1Go GLH | Crucial SSD M4 64Go Sata3

Giz

Alors personne ??

Moi ce qui me tracasse c'est qu'ils parlent que les éléments sont ordonnés par leur moment d'insertion (dernier inséré en fin de liste) dans les entrées de la table. Mais la table elle même ne contient pas les clés ordonnées par leur ordre d'insertion...je ne vois donc pas l'intérêt de cette structure de données pseudo-ordonnée en fin de compte .

J'ai pu lire sur le site de Sun :

LinkedHashSet is in some sense intermediate between HashSet and TreeSet

...donc ce serait bien du pseudo-ordonné...

Message édité par Giz le 28-11-2006 à 11:12:33

benou

Je vois pas trop quel problème de concience tu te poses : une LinkedHashSet est au HashSet ce que le LinkedHashMap est à la hasmap : une structure de donnée basée sur un algo de hashage qui retient l'ordre d'insertion des éléments ce qui permet d'itérer dessus de façon prévisible.

si tu veux voir comment c'est implémenter, regarde le code ...

benou

mais j'imagine qu'à côté de la valeur, il doit y avoir 2 références vers l'élément suivant et précédent ... une liste doublement chainée, quoi ...

Giz

Oui ok, c'est ce que j'avais compris...mais c'est quoi l'intérêt de cette chose, c'est du pseudo ordonné après tout : les clés sont hashées quelque part dans la table et les entrées sont triées par ordre d'insertion. Si on itère sur la LinkedHashMap (avec un iterator) on ne récupèrera pas l'ordre d'insertion DE TOUTES les entrées au final ... non :??:
...je m'intéresse à la raison de cette structure de données, car elle apparaît dans un code que je debug.

Message édité par Giz le 28-11-2006 à 19:50:51

FORUM HardWare.fr

Programmation

Java

Différence entre les HashSet et les LinkedHashSet dans l'API Java

Sujets relatifs
[jedit] compiler .java ok, executer comment faire ?	JAVA, XML, Excel je suis perdu
JNI, C => JAVA	Besoin d'aide, conseil Jsp, java
Aide pour un Java Script	[Java][Swing] Ajouter une colonne editable à une jtable non editable
[Java] Comment ralentir une boucle Java ?	Probleme avec un script java sur une page html
[PHP] difference d'accès a un site par rapport au model	java executer commande systeme
Plus de sujets relatifs à : Différence entre les HashSet et les LinkedHashSet dans l'API Java

Page générée en 0.064 secondes