Oui, ou alors un HashSet qui ne différencie pas la clé et l'objet.
Ah oui, le HashSet, sympathique, justement, j'ai pas besoin de couple clé/objet. merci de ton aide.
MiXAO
Johann Burkard
MiXAO wrote:
.. pour contenir plusieurs dizaines de milliers de petites chaines de caractères. Hashtable ?
Le but de ce conteneur sera d'être utilisé pour tester l'existence d'une chaine ou non. Un dictionnaire en gros.
J'ai écrit une classe appellée HashCache [1] qui t'aide peut-être:
-- 8< -- The HashCache is a collision-free hash table that only stores hash codes from Objects, not the actual Objects themselves. This is useful when the most frequent operation is <code>contains</code> (a O(1) operation in the HashCache). [...] Performance results for 1 million <code>contains</code> invocations (@ 2.4 GHz, Sun SDK 1.4.1_01) on around 25 Strings:
HashCache: ~ 80 ms java.util.TreeSet: ~ 265 ms java.util.HashSet: ~ 350 ms java.util.Hashtable: ~ 625 ms java.util.ArrayList: ~ 850 ms java.util.Vector: ~ 930 ms -- >8 --
Je sais pas si ca marche très bien avec beaucoup d'objets, mais tu peux essayer.
Johann -- X-Post über de.soc.netzkultur.umgangsformen und de.soc.netzkultur.umgangsformen, Fup2 de.soc.netzkultur.umgangsformen (*Tönnes in <b9c3pq$9ke$03$)
MiXAO wrote:
.. pour contenir plusieurs dizaines de milliers de petites chaines de
caractères.
Hashtable ?
Le but de ce conteneur sera d'être utilisé pour tester l'existence d'une
chaine ou non. Un dictionnaire en gros.
J'ai écrit une classe appellée HashCache [1] qui t'aide peut-être:
-- 8< --
The HashCache is a collision-free hash table that only stores hash codes
from Objects, not the actual Objects themselves. This is useful when the
most frequent operation is <code>contains</code> (a O(1) operation in
the HashCache).
[...]
Performance results for 1 million <code>contains</code> invocations (@
2.4 GHz, Sun SDK 1.4.1_01) on around 25 Strings:
HashCache: ~ 80 ms
java.util.TreeSet: ~ 265 ms
java.util.HashSet: ~ 350 ms
java.util.Hashtable: ~ 625 ms
java.util.ArrayList: ~ 850 ms
java.util.Vector: ~ 930 ms
-- >8 --
Je sais pas si ca marche très bien avec beaucoup d'objets, mais tu peux
essayer.
Johann
--
X-Post über de.soc.netzkultur.umgangsformen und
de.soc.netzkultur.umgangsformen, Fup2 de.soc.netzkultur.umgangsformen
(*Tönnes in <b9c3pq$9ke$03$9@news.t-online.com>)
.. pour contenir plusieurs dizaines de milliers de petites chaines de caractères. Hashtable ?
Le but de ce conteneur sera d'être utilisé pour tester l'existence d'une chaine ou non. Un dictionnaire en gros.
J'ai écrit une classe appellée HashCache [1] qui t'aide peut-être:
-- 8< -- The HashCache is a collision-free hash table that only stores hash codes from Objects, not the actual Objects themselves. This is useful when the most frequent operation is <code>contains</code> (a O(1) operation in the HashCache). [...] Performance results for 1 million <code>contains</code> invocations (@ 2.4 GHz, Sun SDK 1.4.1_01) on around 25 Strings:
HashCache: ~ 80 ms java.util.TreeSet: ~ 265 ms java.util.HashSet: ~ 350 ms java.util.Hashtable: ~ 625 ms java.util.ArrayList: ~ 850 ms java.util.Vector: ~ 930 ms -- >8 --
Je sais pas si ca marche très bien avec beaucoup d'objets, mais tu peux essayer.
Johann -- X-Post über de.soc.netzkultur.umgangsformen und de.soc.netzkultur.umgangsformen, Fup2 de.soc.netzkultur.umgangsformen (*Tönnes in <b9c3pq$9ke$03$)
Nico
"Johann Burkard" a écrit dans le message de news:41fd36fe$0$18561$
MiXAO wrote:
.. pour contenir plusieurs dizaines de milliers de petites chaines de caractères. Hashtable ?
Le but de ce conteneur sera d'être utilisé pour tester l'existence d'une chaine ou non. Un dictionnaire en gros.
J'ai écrit une classe appellée HashCache [1] qui t'aide peut-être:
-- 8< -- The HashCache is a collision-free hash table that only stores hash codes from Objects, not the actual Objects themselves. This is useful when the most frequent operation is <code>contains</code> (a O(1) operation in the HashCache). [...] Performance results for 1 million <code>contains</code> invocations (@ 2.4 GHz, Sun SDK 1.4.1_01) on around 25 Strings:
HashCache: ~ 80 ms java.util.TreeSet: ~ 265 ms java.util.HashSet: ~ 350 ms java.util.Hashtable: ~ 625 ms java.util.ArrayList: ~ 850 ms java.util.Vector: ~ 930 ms -- >8 --
Je sais pas si ca marche très bien avec beaucoup d'objets, mais tu peux essayer.
Désolé, mais je comprends pas comment ca peut marcher. Il me semble que ce n'est parce que deux objets ont le même hashcode qu'ils sont égaux. Tu peux m'expliquer ?
Nicolas
"Johann Burkard" <johannburkard@nexgo.de> a écrit dans le message de
news:41fd36fe$0$18561$9b4e6d93@newsread4.arcor-online.net...
MiXAO wrote:
.. pour contenir plusieurs dizaines de milliers de petites chaines de
caractères.
Hashtable ?
Le but de ce conteneur sera d'être utilisé pour tester l'existence d'une
chaine ou non. Un dictionnaire en gros.
J'ai écrit une classe appellée HashCache [1] qui t'aide peut-être:
-- 8< --
The HashCache is a collision-free hash table that only stores hash codes
from Objects, not the actual Objects themselves. This is useful when the
most frequent operation is <code>contains</code> (a O(1) operation in
the HashCache).
[...]
Performance results for 1 million <code>contains</code> invocations (@
2.4 GHz, Sun SDK 1.4.1_01) on around 25 Strings:
HashCache: ~ 80 ms
java.util.TreeSet: ~ 265 ms
java.util.HashSet: ~ 350 ms
java.util.Hashtable: ~ 625 ms
java.util.ArrayList: ~ 850 ms
java.util.Vector: ~ 930 ms
-- >8 --
Je sais pas si ca marche très bien avec beaucoup d'objets, mais tu peux
essayer.
Désolé, mais je comprends pas comment ca peut marcher.
Il me semble que ce n'est parce que deux objets ont le même hashcode qu'ils
sont égaux.
Tu peux m'expliquer ?
"Johann Burkard" a écrit dans le message de news:41fd36fe$0$18561$
MiXAO wrote:
.. pour contenir plusieurs dizaines de milliers de petites chaines de caractères. Hashtable ?
Le but de ce conteneur sera d'être utilisé pour tester l'existence d'une chaine ou non. Un dictionnaire en gros.
J'ai écrit une classe appellée HashCache [1] qui t'aide peut-être:
-- 8< -- The HashCache is a collision-free hash table that only stores hash codes from Objects, not the actual Objects themselves. This is useful when the most frequent operation is <code>contains</code> (a O(1) operation in the HashCache). [...] Performance results for 1 million <code>contains</code> invocations (@ 2.4 GHz, Sun SDK 1.4.1_01) on around 25 Strings:
HashCache: ~ 80 ms java.util.TreeSet: ~ 265 ms java.util.HashSet: ~ 350 ms java.util.Hashtable: ~ 625 ms java.util.ArrayList: ~ 850 ms java.util.Vector: ~ 930 ms -- >8 --
Je sais pas si ca marche très bien avec beaucoup d'objets, mais tu peux essayer.
Désolé, mais je comprends pas comment ca peut marcher. Il me semble que ce n'est parce que deux objets ont le même hashcode qu'ils sont égaux. Tu peux m'expliquer ?
Nicolas
Johann Burkard
Nico wrote:
Il me semble que ce n'est parce que deux objets ont le même hashcode qu'ils sont égaux.
Oui, normal, mais tu peux t'écrire une meilleure méthode hashCode() si tu as trop de collisions.
En plus, dans ce cas, tu veux qu'un petit test si un objet se trouve dans un Collection. Ou bien c'est ce que je pense.
Johann -- X-Post über de.soc.netzkultur.umgangsformen und de.soc.netzkultur.umgangsformen, Fup2 de.soc.netzkultur.umgangsformen (*Tönnes in <b9c3pq$9ke$03$)
Nico wrote:
Il me semble que ce n'est parce que deux objets ont le même hashcode qu'ils
sont égaux.
Oui, normal, mais tu peux t'écrire une meilleure méthode hashCode() si
tu as trop de collisions.
En plus, dans ce cas, tu veux qu'un petit test si un objet se trouve
dans un Collection. Ou bien c'est ce que je pense.
Johann
--
X-Post über de.soc.netzkultur.umgangsformen und
de.soc.netzkultur.umgangsformen, Fup2 de.soc.netzkultur.umgangsformen
(*Tönnes in <b9c3pq$9ke$03$9@news.t-online.com>)
Il me semble que ce n'est parce que deux objets ont le même hashcode qu'ils sont égaux.
Oui, normal, mais tu peux t'écrire une meilleure méthode hashCode() si tu as trop de collisions.
En plus, dans ce cas, tu veux qu'un petit test si un objet se trouve dans un Collection. Ou bien c'est ce que je pense.
Johann -- X-Post über de.soc.netzkultur.umgangsformen und de.soc.netzkultur.umgangsformen, Fup2 de.soc.netzkultur.umgangsformen (*Tönnes in <b9c3pq$9ke$03$)
Nico
"Johann Burkard" a écrit dans le message de news:41fd4d8b$0$18553$
Nico wrote:
Il me semble que ce n'est parce que deux objets ont le même hashcode qu'ils
sont égaux.
Oui, normal, mais tu peux t'écrire une meilleure méthode hashCode() si tu as trop de collisions.
En plus, dans ce cas, tu veux qu'un petit test si un objet se trouve dans un Collection. Ou bien c'est ce que je pense.
D'accord, mais ta classe HashCache ne teste que si elle contient un hashcode donné.
Si tu ajoutes un seul objet A dans HashCache et que tu appelles ensuite la méthode contains() avec un autre objet B (différent de A), il y a une très faible chance (1 sur 2^64) que cette méthode retourne true. Donc il y a des cas ou ta méthode ne marche pas.
Nicolas
"Johann Burkard" <johannburkard@nexgo.de> a écrit dans le message de
news:41fd4d8b$0$18553$9b4e6d93@newsread4.arcor-online.net...
Nico wrote:
Il me semble que ce n'est parce que deux objets ont le même hashcode
qu'ils
sont égaux.
Oui, normal, mais tu peux t'écrire une meilleure méthode hashCode() si
tu as trop de collisions.
En plus, dans ce cas, tu veux qu'un petit test si un objet se trouve
dans un Collection. Ou bien c'est ce que je pense.
D'accord, mais ta classe HashCache ne teste que si elle contient un hashcode
donné.
Si tu ajoutes un seul objet A dans HashCache et que tu appelles ensuite la
méthode contains() avec un autre objet B (différent de A), il y a une très
faible chance (1 sur 2^64) que cette méthode retourne true.
Donc il y a des cas ou ta méthode ne marche pas.
"Johann Burkard" a écrit dans le message de news:41fd4d8b$0$18553$
Nico wrote:
Il me semble que ce n'est parce que deux objets ont le même hashcode qu'ils
sont égaux.
Oui, normal, mais tu peux t'écrire une meilleure méthode hashCode() si tu as trop de collisions.
En plus, dans ce cas, tu veux qu'un petit test si un objet se trouve dans un Collection. Ou bien c'est ce que je pense.
D'accord, mais ta classe HashCache ne teste que si elle contient un hashcode donné.
Si tu ajoutes un seul objet A dans HashCache et que tu appelles ensuite la méthode contains() avec un autre objet B (différent de A), il y a une très faible chance (1 sur 2^64) que cette méthode retourne true. Donc il y a des cas ou ta méthode ne marche pas.
Nicolas
Johann Burkard
Nico wrote:
D'accord, mais ta classe HashCache ne teste que si elle contient un hashcode donné.
Mais si:
-- 8< -- protected boolean add(int code) { int pos = Math.abs(code) % array.length; if (array[pos] == code) {
/* Value is already in array, resizing not required. */
return false; }
while (array[pos] != 0) {
/* * Worst-case scenario: There is another element at the computed position, * the array needs resizing because we do not allow collisions in the * HashCache. * * Find out at which size of the array all current hash codes can be mapped * to new buckets without producing collisions. */
Si tu ajoutes un seul objet A dans HashCache et que tu appelles ensuite la méthode contains() avec un autre objet B (différent de A), il y a une très faible chance (1 sur 2^64) que cette méthode retourne true.
Euh, la chance est 1/2^32, pas 1/2^64 (_int_ hashCode()). En fait, c'est que 1/2^31 (Math.abs(code)) dans le HashCache. Mais je peux pas éviter ca - un HashCache ne contient les objets.
Mais comme j'ai dit - c'est qu'un petit test. Tu peux avoir un HashCache pour éliminer quelques percents des appels d'un autre Collection.
Johann -- X-Post über de.soc.netzkultur.umgangsformen und de.soc.netzkultur.umgangsformen, Fup2 de.soc.netzkultur.umgangsformen (*Tönnes in <b9c3pq$9ke$03$)
Nico wrote:
D'accord, mais ta classe HashCache ne teste que si elle contient un hashcode
donné.
Mais si:
-- 8< --
protected boolean add(int code) {
int pos = Math.abs(code) % array.length;
if (array[pos] == code) {
/* Value is already in array, resizing not required. */
return false;
}
while (array[pos] != 0) {
/*
* Worst-case scenario: There is another element at the computed
position,
* the array needs resizing because we do not allow collisions in the
* HashCache.
*
* Find out at which size of the array all current hash codes can be
mapped
* to new buckets without producing collisions.
*/
Si tu ajoutes un seul objet A dans HashCache et que tu appelles ensuite la
méthode contains() avec un autre objet B (différent de A), il y a une très
faible chance (1 sur 2^64) que cette méthode retourne true.
Euh, la chance est 1/2^32, pas 1/2^64 (_int_ hashCode()). En fait, c'est
que 1/2^31 (Math.abs(code)) dans le HashCache. Mais je peux pas éviter
ca - un HashCache ne contient les objets.
Mais comme j'ai dit - c'est qu'un petit test. Tu peux avoir un HashCache
pour éliminer quelques percents des appels d'un autre Collection.
Johann
--
X-Post über de.soc.netzkultur.umgangsformen und
de.soc.netzkultur.umgangsformen, Fup2 de.soc.netzkultur.umgangsformen
(*Tönnes in <b9c3pq$9ke$03$9@news.t-online.com>)
D'accord, mais ta classe HashCache ne teste que si elle contient un hashcode donné.
Mais si:
-- 8< -- protected boolean add(int code) { int pos = Math.abs(code) % array.length; if (array[pos] == code) {
/* Value is already in array, resizing not required. */
return false; }
while (array[pos] != 0) {
/* * Worst-case scenario: There is another element at the computed position, * the array needs resizing because we do not allow collisions in the * HashCache. * * Find out at which size of the array all current hash codes can be mapped * to new buckets without producing collisions. */
Si tu ajoutes un seul objet A dans HashCache et que tu appelles ensuite la méthode contains() avec un autre objet B (différent de A), il y a une très faible chance (1 sur 2^64) que cette méthode retourne true.
Euh, la chance est 1/2^32, pas 1/2^64 (_int_ hashCode()). En fait, c'est que 1/2^31 (Math.abs(code)) dans le HashCache. Mais je peux pas éviter ca - un HashCache ne contient les objets.
Mais comme j'ai dit - c'est qu'un petit test. Tu peux avoir un HashCache pour éliminer quelques percents des appels d'un autre Collection.
Johann -- X-Post über de.soc.netzkultur.umgangsformen und de.soc.netzkultur.umgangsformen, Fup2 de.soc.netzkultur.umgangsformen (*Tönnes in <b9c3pq$9ke$03$)
fg
Mais comme j'ai dit - c'est qu'un petit test. Tu peux avoir un HashCache pour éliminer quelques percents des appels d'un autre Collection.
Au lieu de cela, je pense que tu peux modifier un peu ta classe : -au lieu d'un tableau d'int, tu fais 1 tableau d'objets -au lieu de stocker les hashcode (que tu ré-utilises dans ta méthode grow() j'imagine, j'ai juste lu les messages, pas ta source), tu stockes les objets (je ne pense pas que tout cela n'implique un important ralentissement, si oui, oubliez mon message... mais ta classe restera approximative...) -pour le test du "contains", tu vas à l'endroit concerné, s'il y a un objet, tu testes cetObjet.equals(leParametre)
(en gros, tu refais la Hashtable, mais sans les LinkedList ;-) )
Je pense que tu peux retrouver exactement le même comportement avec la Hashtable en jouant sur ses deux paramètres de constructeur.
Fred.
Mais comme j'ai dit - c'est qu'un petit test. Tu peux avoir un HashCache
pour éliminer quelques percents des appels d'un autre Collection.
Au lieu de cela, je pense que tu peux modifier un peu ta classe :
-au lieu d'un tableau d'int, tu fais 1 tableau d'objets
-au lieu de stocker les hashcode (que tu ré-utilises dans ta méthode grow()
j'imagine, j'ai juste lu les messages, pas ta source), tu stockes les objets
(je ne pense pas que tout cela n'implique un important ralentissement, si
oui, oubliez mon message... mais ta classe restera approximative...)
-pour le test du "contains", tu vas à l'endroit concerné, s'il y a un objet,
tu testes cetObjet.equals(leParametre)
(en gros, tu refais la Hashtable, mais sans les LinkedList ;-) )
Je pense que tu peux retrouver exactement le même comportement avec la
Hashtable en jouant sur ses deux paramètres de constructeur.
Mais comme j'ai dit - c'est qu'un petit test. Tu peux avoir un HashCache pour éliminer quelques percents des appels d'un autre Collection.
Au lieu de cela, je pense que tu peux modifier un peu ta classe : -au lieu d'un tableau d'int, tu fais 1 tableau d'objets -au lieu de stocker les hashcode (que tu ré-utilises dans ta méthode grow() j'imagine, j'ai juste lu les messages, pas ta source), tu stockes les objets (je ne pense pas que tout cela n'implique un important ralentissement, si oui, oubliez mon message... mais ta classe restera approximative...) -pour le test du "contains", tu vas à l'endroit concerné, s'il y a un objet, tu testes cetObjet.equals(leParametre)
(en gros, tu refais la Hashtable, mais sans les LinkedList ;-) )
Je pense que tu peux retrouver exactement le même comportement avec la Hashtable en jouant sur ses deux paramètres de constructeur.
Fred.
burma
MiXAO wrote:
.. pour contenir plusieurs dizaines de milliers de petites chaines de caractères. Hashtable ?
Le but de ce conteneur sera d'être utilisé pour tester l'existence d'une chaine ou non. Un dictionnaire en gros.
MiXAO
Dans jazzy, (correcteur orthographique dispo sur sourceforge), j'ai écris une classe qui mappe, avec les nio, toutes les chaines dans un fichier sur le disque et permet ensuite de les retrouver par dichotomie.
Cela nécessite une jdk 1.4+, c'est surement moins rapide qu'un hashset, mais ca consomme également beaucoup moins de mémoire...
Emmanuel D.
MiXAO wrote:
.. pour contenir plusieurs dizaines de milliers de petites chaines de
caractères.
Hashtable ?
Le but de ce conteneur sera d'être utilisé pour tester l'existence d'une
chaine ou non. Un dictionnaire en gros.
MiXAO
Dans jazzy, (correcteur orthographique dispo sur sourceforge), j'ai
écris une classe qui mappe, avec les nio, toutes les chaines dans un
fichier sur le disque et permet ensuite de les retrouver par dichotomie.
Cela nécessite une jdk 1.4+, c'est surement moins rapide qu'un hashset,
mais ca consomme également beaucoup moins de mémoire...
.. pour contenir plusieurs dizaines de milliers de petites chaines de caractères. Hashtable ?
Le but de ce conteneur sera d'être utilisé pour tester l'existence d'une chaine ou non. Un dictionnaire en gros.
MiXAO
Dans jazzy, (correcteur orthographique dispo sur sourceforge), j'ai écris une classe qui mappe, avec les nio, toutes les chaines dans un fichier sur le disque et permet ensuite de les retrouver par dichotomie.
Cela nécessite une jdk 1.4+, c'est surement moins rapide qu'un hashset, mais ca consomme également beaucoup moins de mémoire...
