RE: hashset contains wtf
Vidis, dvakrat jsem to precetl, ale napsal jsem to presne tak, jak jsem vubec nechtel - znate to, hlavne to takhle nenapsat... Presne tak = kolize a proto je dle meho nazoru ten equals v JavaDocu spravne. A z navrhu Object vypadavaji implementace jakou double hashing a jedna z mala (mozna jedina mozna) implementace mne vychazi seznam kolidujicich objectu, ktery se projede cely pomoci equals. a k tematu - v Javoveske impl chybi copy constructor - v STL by se volal pri put (vim jmenuje se to jinak) copy constructor, takze kontrakt by se dodrzel, ale jinak nez tazatel by chtel. On ??t, 2007-05-24 at 17:36 +0200, lukas wrote: On Thu, 24 May 2007 17:10:03 +0200, Karel Tejnora wrote Opomenuti obecnych pravidel hashCode musi odpovidat chovani equals tj. A.equals(B)== true pak A.hashCode()==B.hashCode() a zaroven A.equals(B) == false pak A.hashCode()!=B.hashCode() Ta druha podminka prae platit nemusi. A.equals(B)==false neznamena, ze maji ruzne hashovani. Tj. muzou existovat kolize :-) Doporucuji precist nejakou teorii k hashovani :-) Lukas
Re: hashset contains wtf
Rudolf PECINOVSKÝ wrote:
Děkuji za objasnění, už rozumím (naprosto dokonale).
Jednoznačně je to chyba v javadoc.
Možná se moje odpověď nebude někomu líbit, ale podle mne v javadoc chyba
není. Toto chování vyplývá z vlastností hešových tabulek a měla by to proto
vysvětlit učebnice (nebo lektor) jako obecnou vlastnost všech objektů
využívajících hešových tabulek. Jestli k vám takováto informace ještě
nepronikla, spílejte svým učitelům a autorům učebnic, z nichž jste se Javu
učili.
Dovolil bych si nesouhlasit. Javadoc tvrdí, že metoda contains()
u HashSet používá pouze equals(), což není pravda, a proto
je to chyba dokumentace. To, že používá hashovací tabulku,
přece neznamená, že contains() nemůže hrubou silou projít
všechny položky. Sice by to nebylo moc efektivní, ale
neporušovalo by to kontrakt zděděný z Set.
Čili javadoc naznačuje, že implementace contains vypadá
nějak takto:
boolean contains(Object o) {
for(Iterator i = this.iterator();i.hasNext();) {
Object e = i.next();
if(o==null) {
if( e==null) return true;
} else {
if(o.equals(i.next())) return true;
}
}
return false;
}
což není pravda.
Makub
--
~~
Supercomputing Center Brno Martin Kuba
Institute of Computer Scienceemail: [EMAIL PROTECTED]
Masaryk University http://www.ics.muni.cz/~makub/
Botanicka 68a, 60200 Brno, CZ mobil: +420-603-533775
--
smime.p7s
Description: S/MIME Cryptographic Signature
Re: hashset contains wtf
Dovolil bych si nesouhlasit ... protoze pak by metoda contains byla treba v
rozporu s metodou remove, protoze contains
by vracela true a remove false, protoze objekt se zmenenym hashem z hashset
nesmazete ...
Jirka
Martin Kuba napsal(a):
Rudolf PECINOVSKÝ wrote:
Děkuji za objasnění, už rozumím (naprosto dokonale).
Jednoznačně je to chyba v javadoc.
Možná se moje odpověď nebude někomu líbit, ale podle mne v javadoc chyba
není. Toto chování vyplývá z vlastností hešových tabulek a měla by to proto
vysvětlit učebnice (nebo lektor) jako obecnou vlastnost všech objektů
využívajících hešových tabulek. Jestli k vám takováto informace ještě
nepronikla, spílejte svým učitelům a autorům učebnic, z nichž jste se Javu
učili.
Dovolil bych si nesouhlasit. Javadoc tvrdí, že metoda contains()
u HashSet používá pouze equals(), což není pravda, a proto
je to chyba dokumentace. To, že používá hashovací tabulku,
přece neznamená, že contains() nemůže hrubou silou projít
všechny položky. Sice by to nebylo moc efektivní, ale
neporušovalo by to kontrakt zděděný z Set.
Čili javadoc naznačuje, že implementace contains vypadá
nějak takto:
boolean contains(Object o) {
for(Iterator i = this.iterator();i.hasNext();) {
Object e = i.next();
if(o==null) {
if( e==null) return true;
} else {
if(o.equals(i.next())) return true;
}
}
return false;
}
což není pravda.
Makub
--
Jiří Mareš (mailto:[EMAIL PROTECTED])
ČSAD SVT Praha, s.r.o. (http://www.svt.cz)
Czech Republic
Re: hashset contains wtf
Mo?n? se moje odpov?? nebude n?komu l?bit, ale podle mne v javadoc chyba nen?. Toto chov?n? vypl?v? z vlastnost? he?ov?ch tabulek a m?la by to proto vysv?tlit u?ebnice (nebo lektor) jako obecnou vlastnost v?ech objekt? vyu??vaj?c?ch he?ov?ch tabulek. Jestli k v?m takov?to informace je?t? nepronikla, sp?lejte sv?m u?itel?m a autor?m u?ebnic, z nich? jste se Javu u?ili. Rozli?ujte javadoc a u?ebnici. Kdyby se m?ly d?vat do javadoc i takov?to v?ci, tak tam za chv?li n?kdo bude cht?t vysv?tlit, jak funguje interface nebo jin? jazykov? konstrukt. Pro javadoc by m?lo sta?it prohl??en?, ?e dan? kontejner je definov?n pomoc? he?ov?ch tabulek, a to tam je. T?m nechci ??st, ?e by javadoc n?jakou drobnou zm?nku na toto t?ma nesnesl, ale ch?pu, pro? se Sun?m nechce do n?j d?vat v?ci, kter? maj? b?t prim?rn? vysv?tleny jinde. J? bych jim sp?? vy??tal, ?e tuto informaci nedali do tutori?lu (leda bych ji tam ve sv? slepot? nena?el) - tam podle mne pat??. J? bych tam za?adil kapitolku o he?ov?ch tabulk?ch, na kterou by se pak odvol?valy v?echny kapitoly pojedn?vaj?c?ch o kontejnerech, kter? jsou na he?ov?ch tabulk?ch zalo?eny. ^-- To by bolo vsetko pekene, keby sa javadoc uspokojil so vseobecnym tvrdenim, ze contains() vracia true, ak sa objekt v mnozine nachadza; v tom pripade je na javadoc-u triedy HashSet oznamit ze ako backend pouziva HashMap a ze treba vziat na zretel z toho plynuce konsekvencie (co javadoc triedy HashSet robi), ked hned aj z toho plynuce konsekvencie maju byt priemernemu programatorovi zname. Zasadna chyba je, ze javadoc triedy contains() ODHALUJE IMPLEMENTACIU, zial taku, ktoru samotna metoda neimplementuje. Javadoc metody contains() v triede HashSet JE chybny. J.
RE: hashset contains wtf
To neni pravda, Javadoc o implementaci vubec nic nehovori. Pouze zcela presne definuje, co mini pojmem obsahuje a jak se prvky porovnavaji s predanym parametrem. Naopak, ona definice s equals je tam zcela nutna - plyne z ni, ze pokud se zmeni vysledek hashCode() a equals(), tak se jiz nejedna o stejny objekt! Jak jiz v diskusi padlo, do mnoziny byl totiz vlastne pridan jiny objekt nez ktery je potom porovnavan pomoci contains(). Co tam chybi je jen upozorneni na vyse zmineny fakt - ze implementace Map/Set si muze identitu cachovat a pokud se objekt promeni na jiny, chovani je obecne nepredvidatelne. Kamil Podlesak -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Behalf Of Jozef Babjak Sent: Thursday, May 24, 2007 11:34 AM To: Java Subject: Re: hashset contains wtf Zasadna chyba je, ze javadoc triedy contains() ODHALUJE IMPLEMENTACIU, zial taku, ktoru samotna metoda neimplementuje. Javadoc metody contains() v triede HashSet JE chybny. J.
Re: hashset contains wtf
Tak mi to nedalo a koukl jsem se na javadoc. K JDK 5: Returns true if this set contains the specified element. a k JDK 6: Returns true if this set contains the specified element. More formally, returns true if and only if this set contains an element e such that (o==null ? e==null : o.equals(e)). Rekl bych ze formulace je diky if and olny if skutecne zavadejici. Ale jak bych rekl jiz po Xte, zdrojak hovori jasnou reci! Jirka Jozef Babjak napsal(a): Mo�n� se moje odpov�� nebude n�komu l�bit, ale podle mne v javadoc chyba nen�. Toto chov�n� vypl�v� z vlastnost� he�ov�ch tabulek a m�la by to proto vysv�tlit u�ebnice (nebo lektor) jako obecnou vlastnost v�ech objekt� vyu��vaj�c�ch he�ov�ch tabulek. Jestli k v�m takov�to informace je�t� nepronikla, sp�lejte sv�m u�itel�m a autor�m u�ebnic, z nich� jste se Javu u�ili. Rozli�ujte javadoc a u�ebnici. Kdyby se m�ly d�vat do javadoc i takov�to v�ci, tak tam za chv�li n�kdo bude cht�t vysv�tlit, jak funguje interface nebo jin� jazykov� konstrukt. Pro javadoc by m�lo sta�it prohl�en�, �e dan� kontejner je definov�n pomoc� he�ov�ch tabulek, a to tam je. T�m nechci ��st, �e by javadoc n�jakou drobnou zm�nku na toto t�ma nesnesl, ale ch�pu, pro� se Sun�m nechce do n�j d�vat v�ci, kter� maj� b�t prim�rn� vysv�tleny jinde. J� bych jim sp� vy��tal, �e tuto informaci nedali do tutori�lu (leda bych ji tam ve sv� slepot� nena�el) - tam podle mne pat��. J� bych tam za�adil kapitolku o he�ov�ch tabulk�ch, na kterou by se pak odvol�valy v�echny kapitoly pojedn�vaj�c�ch o kontejnerech, kter� jsou na he�ov�ch tabulk�ch zalo�eny. ^-- To by bolo vsetko pekene, keby sa javadoc uspokojil so vseobecnym tvrdenim, ze contains() vracia true, ak sa objekt v mnozine nachadza; v tom pripade je na javadoc-u triedy HashSet oznamit ze ako backend pouziva HashMap a ze treba vziat na zretel z toho plynuce konsekvencie (co javadoc triedy HashSet robi), ked hned aj z toho plynuce konsekvencie maju byt priemernemu programatorovi zname. Zasadna chyba je, ze javadoc triedy contains() ODHALUJE IMPLEMENTACIU, zial taku, ktoru samotna metoda neimplementuje. Javadoc metody contains() v triede HashSet JE chybny. J. -- Jiří Mareš (mailto:[EMAIL PROTECTED]) ČSAD SVT Praha, s.r.o. (http://www.svt.cz) Czech Republic
Re: hashset contains wtf
Jiri Mares wrote: Dovolil bych si nesouhlasit ... protoze pak by metoda contains byla treba v rozporu s metodou remove, protoze contains by vracela true a remove false, protoze objekt se zmenenym hashem z hashset nesmazete ... Nebyla. Javadoc k contains() i remove() se dedi ze Set, a o hashCode() v obojim neni ani zminka. Tedy pokud by se obe chovaly podle javadocu, musely by projit celou kolekci prvku, aby hledany prvek nasly. Problem IMHO spociva v tom, ze HashSet dedi javadoc ze Set, ktera mluvi pouze o equals(). A kdyz si prectete javadoc k Object.equals() a Object.hashCode(), tak se tam rika, ze pokud dva objekty davaji equals() true, tak musi davat i stejny hashCode(), ale zmeny v case se tam neresi. Tento kontrakt equals() a hashCode() vkladane mutovatelne kolekce v kazdem okamziku splnuji. Tedy to, ze HashSet hleda objekty podle hodnoty hashCode() v okamziku vlozeni, a nikoliv prohledanim vsech prvku kolekce, je implementacni detail HashSet, kterym se lisi od Set, a nemela by tedy od ni dedit javadoc. Makub -- ~~ Supercomputing Center Brno Martin Kuba Institute of Computer Scienceemail: [EMAIL PROTECTED] Masaryk University http://www.ics.muni.cz/~makub/ Botanicka 68a, 60200 Brno, CZ mobil: +420-603-533775 -- smime.p7s Description: S/MIME Cryptographic Signature
Re: hashset contains wtf
Martin Kuba napsal(a): A kdyz si prectete javadoc k Object.equals() a Object.hashCode(), tak se tam rika, ze pokud dva objekty davaji equals() true, tak musi davat i stejny hashCode(), ale zmeny v case se tam neresi. A co teda rika prvni bod tady: http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Object.html#hashCode() ? Je fakt ze casti: ..., provided no information used in equals comparisons on the object is modified prakticky nerozumim. Ale rekl bych, ze to pozadavek na chovani v case popisuje. -- S pozdravem, Tomas Zverina Multimedia atelier s.r.o. Na Dolinách 4 147 00 Praha 4 IČO: 25127071 tel.: 241 433 120 e-mail: [EMAIL PROTECTED] http://www.m-atelier.cz/ Společnost Multimedia atelier s.r.o. je zapsána u rejstříkového soudu v Praze, oddíl C, vložka 51961.
Re: hashset contains wtf
Pozor, spor je zrejme nad javadoc k jdk6 ... Tomas Zverina napsal(a): Martin Kuba napsal(a): A kdyz si prectete javadoc k Object.equals() a Object.hashCode(), tak se tam rika, ze pokud dva objekty davaji equals() true, tak musi davat i stejny hashCode(), ale zmeny v case se tam neresi. A co teda rika prvni bod tady: http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Object.html#hashCode() ? Je fakt ze casti: ..., provided no information used in equals comparisons on the object is modified prakticky nerozumim. Ale rekl bych, ze to pozadavek na chovani v case popisuje. -- Jiří Mareš (mailto:[EMAIL PROTECTED]) ČSAD SVT Praha, s.r.o. (http://www.svt.cz) Czech Republic
Re: hashset contains wtf
Javadoc k contains() i remove() se dedi ze Set,
To neni pravda. Vynatek ze zdrojaku JDK6 k tride HashSet:
/**
* Returns tttrue/tt if this set contains the specified element.
* More formally, returns tttrue/tt if and only if this set
* contains an element tte/tt such that
* tt(o==nullnbsp;?nbsp;e==nullnbsp;:nbsp;o.equals(e))/tt.
*
* @param o element whose presence in this set is to be tested
* @return tttrue/tt if this set contains the specified element
*/
public boolean contains(Object o) {
return map.containsKey(o);
}
/**
* Removes the specified element from this set if it is present.
* More formally, removes an element tte/tt such that
* tt(o==nullnbsp;?nbsp;e==nullnbsp;:nbsp;o.equals(e))/tt,
* if this set contains such an element. Returns tttrue/tt if
* this set contained the element (or equivalently, if this set
* changed as a result of the call). (This set will not contain the
* element once the call returns.)
*
* @param o object to be removed from this set, if present
* @return tttrue/tt if the set contained the specified element
*/
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
Ja tu nic o dedeni javadocu nevidim.
--
Jiří Mareš (mailto:[EMAIL PROTECTED])
ČSAD SVT Praha, s.r.o. (http://www.svt.cz)
Czech Republic
RE: hashset contains wtf
Opomenuti obecnych pravidel hashCode musi odpovidat chovani equals tj. A.equals(B)== true pak A.hashCode()==B.hashCode() a zaroven A.equals(B) == false pak A.hashCode()!=B.hashCode() a vysledek hashCode() se pro stejny objekt se nemeni od spusteni JVM. Nekde v archivu konference je odkaz na Bloch Effective programming in Java (nebo jak se to jmenuje), kde se Bloch venuje efektivni metode pro hash a equals. karel On ??t, 2007-05-24 at 11:47 +0200, Podlesak Kamil wrote: hashCode() a equals()
RE: hashset contains wtf
Zdravim,
To je proste: Map#hashCode() presne definuje ze vysledek musi byt vypocitan
jako soucet hashcode vsech zaznamu. Pridanim noveho prvku se tedy zmeni hodnota
hashCode.
Jenomze HashSet (resp. HashMap, kterou interne pouziva) zarazuje i hleda
zaznamy podle hashCode(). Jakmile se hashCode zmeni, tak hleda jinde a nenajde.
Plati obecne pravidlo:
Objekty vkladane do hash mapy NESMI MENIT svuj hashCode()! Tedy alespon po
dobu, co jsou v mape.
Konkretne pak plati:
Kolekce (Map, Collection) vlozene do hash mapy se NESMI MODIFIKOVAT.
Pokud potrebujete mit v mnozine kolekce ktere bezne modifikujete, pouzijte
IdentityHashMap.
-Original Message-
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] Behalf Of Tomas Zverina
Sent: Wednesday, May 23, 2007 11:24 AM
To: Java
Subject: hashset contains wtf
Zdravim,
nekdo do me prosim vase kopnete, a vysvetlete mi, proc je vystup
nasledujiciho programu:
import java.util.*;
public class HashSetPokus {
public static void main(String[] args) {
{
// Experiment s HashSet
Map element1 = new HashMap();
SetMap container1 = new HashSetMap();
container1.add(element1);
System.out.println(1a: +container1.contains(element1));
container1.iterator().next().put(a, 123);
System.out.println(1b: +container1.contains(element1));
}
{
// Experiment s ArrayList
Map element2 = new HashMap();
ListMap container2 = new ArrayListMap();
container2.add(element2);
System.out.println(2a: +container2.contains(element2));
container2.iterator().next().put(a, 123);
System.out.println(2b: +container2.contains(element2));
}
}
}
takovyhle:
1a: true
1b: false
2a: true
2b: true
misto ocekavaneho:
1a: true
1b: true
2a: true
2b: true
Ja jsem z toho zverina.
--
S pozdravem,
Tomas Zverina
Multimedia atelier s.r.o.
Na Dolinách 4
147 00 Praha 4
IČO: 25127071
tel.: 241 433 120
e-mail: [EMAIL PROTECTED]
http://www.m-atelier.cz/
Společnost Multimedia atelier s.r.o. je zapsána u
rejstříkového soudu v
Praze, oddíl C, vložka 51961.
Re: hashset contains wtf
Podlesak Kamil wrote: Zdravim, To je proste: Map#hashCode() presne definuje ze vysledek musi byt vypocitan jako soucet hashcode vsech zaznamu. Pridanim noveho prvku se tedy zmeni hodnota hashCode. Jenomze HashSet (resp. HashMap, kterou interne pouziva) zarazuje i hleda zaznamy podle hashCode(). Jakmile se hashCode zmeni, tak hleda jinde a nenajde. Plati obecne pravidlo: Objekty vkladane do hash mapy NESMI MENIT svuj hashCode()! Tedy alespon po dobu, co jsou v mape. Konkretne pak plati: Kolekce (Map, Collection) vlozene do hash mapy se NESMI MODIFIKOVAT. Pokud potrebujete mit v mnozine kolekce ktere bezne modifikujete, pouzijte IdentityHashMap. Jen pro upresneni, nesmi se menit vysledek volani hashCode() u objektu pouzivanych jako *klice* v *HashMap*, pripadne ukladanych do HashSet (ktera interne pouziva HashMap). U objektu vkladanych jako *hodnoty* v HashMap je to jedno. U objektu vkladanych do implementaci Set a Map zalozenych na jinem principu nez hashovaci tabulce by to melo byt taky jedno, protoze hashCode() nevolaji. Napr. TreeSet. Makub -- ~~ Supercomputing Center Brno Martin Kuba Institute of Computer Scienceemail: [EMAIL PROTECTED] Masaryk University http://www.ics.muni.cz/~makub/ Botanicka 68a, 60200 Brno, CZ mobil: +420-603-533775 -- smime.p7s Description: S/MIME Cryptographic Signature
RE: hashset contains wtf
Děkuji za objasnění zajímavé vlastnosti těchto objektů, které jsem si prozatím
nebyl vědom. Jenom mi není jasné následující:
1/ Set.contains(Object o)
Returns true if this set contains the specified element. More formally, returns
true if and only if this set contains an element e such that (o==null ? e==null
: o.equals(e)).
Tento obecný kontrakt musí splňovat i HashSet, který používáme v příkladě.
2/ Z toho plyne, že metoda contains() v uvedeném příkladě volá metodu
Map.equals. U té je uvedeno:
Compares the specified object with this map for equality. Returns true if the
given object is also a map and the two Maps represent the same mappings. More
formally, two maps t1 and t2 represent the same mappings if
t1.entrySet().equals(t2.entrySet()). This ensures that the equals method works
properly across different implementations of the Map interface.
Tento obecný kontrakt musí splňovat HashMap, který používáme v příkladě.
Ať čtu jak čtu, to co jste uvedl (že měnit hashcode objektu v mapě nelze) tam
nevidím. Je pravda, že HashMap.hashCode() se zmení, ale pokud je i nadále
splněn obecný kontrakt hashCode() (tj. že musí být v souladu s equals(), a to
je), obecné kontrakty by měly platit jak před změnou, tak po změně.
Mohl bych poprosit o objasnění?
Mirek
-Original Message-
From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Podlesak Kamil
Sent: Wednesday, May 23, 2007 11:39 AM
To: Java
Subject: RE: hashset contains wtf
Zdravim,
To je proste: Map#hashCode() presne definuje ze vysledek musi byt vypocitan
jako soucet hashcode vsech zaznamu. Pridanim noveho prvku se tedy zmeni hodnota
hashCode.
Jenomze HashSet (resp. HashMap, kterou interne pouziva) zarazuje i hleda
zaznamy podle hashCode(). Jakmile se hashCode zmeni, tak hleda jinde a nenajde.
Plati obecne pravidlo:
Objekty vkladane do hash mapy NESMI MENIT svuj hashCode()! Tedy alespon po
dobu, co jsou v mape.
Konkretne pak plati:
Kolekce (Map, Collection) vlozene do hash mapy se NESMI MODIFIKOVAT.
Pokud potrebujete mit v mnozine kolekce ktere bezne modifikujete, pouzijte
IdentityHashMap.
-Original Message-
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] Behalf Of Tomas Zverina
Sent: Wednesday, May 23, 2007 11:24 AM
To: Java
Subject: hashset contains wtf
Zdravim,
nekdo do me prosim vase kopnete, a vysvetlete mi, proc je vystup
nasledujiciho programu:
import java.util.*;
public class HashSetPokus {
public static void main(String[] args) {
{
// Experiment s HashSet
Map element1 = new HashMap();
SetMap container1 = new HashSetMap();
container1.add(element1);
System.out.println(1a: +container1.contains(element1));
container1.iterator().next().put(a, 123);
System.out.println(1b: +container1.contains(element1));
}
{
// Experiment s ArrayList
Map element2 = new HashMap();
ListMap container2 = new ArrayListMap();
container2.add(element2);
System.out.println(2a: +container2.contains(element2));
container2.iterator().next().put(a, 123);
System.out.println(2b: +container2.contains(element2));
}
}
}
takovyhle:
1a: true
1b: false
2a: true
2b: true
misto ocekavaneho:
1a: true
1b: true
2a: true
2b: true
Ja jsem z toho zverina.
--
S pozdravem,
Tomas Zverina
Multimedia atelier s.r.o.
Na Dolinách 4
147 00 Praha 4
IČO: 25127071
tel.: 241 433 120
e-mail: [EMAIL PROTECTED]
http://www.m-atelier.cz/
Společnost Multimedia atelier s.r.o. je zapsána u rejstříkového soudu
v Praze, oddíl C, vložka 51961.
RE: hashset contains wtf
Jen pro upresneni, nesmi se menit vysledek volani hashCode() u objektu pouzivanych jako *klice* v *HashMap*, pripadne ukladanych do HashSet (ktera interne pouziva HashMap). U objektu vkladanych jako *hodnoty* v HashMap je to jedno. Ano, samozrejme, jen klice. U objektu vkladanych do implementaci Set a Map zalozenych na jinem principu nez hashovaci tabulce by to melo byt taky jedno, protoze hashCode() nevolaji. Napr. TreeSet. Tam je obdobny problem s komparatoram ci compareTo(): vysledek porovnani se nesmi menit po dobu co je objekt v TreeSet/TreeMap. Makub -- ~~ Supercomputing Center Brno Martin Kuba Institute of Computer Scienceemail: [EMAIL PROTECTED] Masaryk University http://www.ics.muni.cz/~makub/ Botanicka 68a, 60200 Brno, CZ mobil: +420-603-533775 --
Re: hashset contains wtf
Ahojte, On 5/23/07, Stöhr Miroslav RNDr. Ph.D. [EMAIL PROTECTED] wrote: Ať čtu jak čtu, to co jste uvedl (že měnit hashcode objektu v mapě nelze) tam nevidím. Je pravda, že HashMap.hashCode() se zmení, ale pokud je i nadále splněn obecný kontrakt hashCode() (tj. že musí být v souladu s equals(), a to je), obecné kontrakty by měly platit jak před změnou, tak po změně. Mohl bych poprosit o objasnění? Sun nemá dost dokumentátorů, aby to fixnul v JavaDocu :-) (radši změní stav na: Closed, not a bug) http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4459681 Mirek -- pepa cacek
RE: hashset contains wtf
Uvedene kontrakty plati pouze tehdy, pokud se hashCode() u klice v hasmape
(HashMap, Hashtable, HashSet) nemeni.
Zcela jasne to plyne z implementace a vubec principu fungovani.
Pokud to neni uvedeno v javadocu (take jsem nenasel, ale zas tolik jsem
nehledal), tak je to BUG v javadocu a asi by se mel reportovat.
Kamil Podlesak
-Original Message-
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] Behalf Of Stöhr
Miroslav RNDr. Ph.D.
Sent: Wednesday, May 23, 2007 12:05 PM
To: Java
Subject: RE: hashset contains wtf
Děkuji za objasnění zajímavé vlastnosti těchto objektů, které
jsem si prozatím nebyl vědom. Jenom mi není jasné následující:
1/ Set.contains(Object o)
Returns true if this set contains the specified element. More
formally, returns true if and only if this set contains an
element e such that (o==null ? e==null : o.equals(e)).
Tento obecný kontrakt musí splňovat i HashSet, který
používáme v příkladě.
2/ Z toho plyne, že metoda contains() v uvedeném příkladě
volá metodu Map.equals. U té je uvedeno:
Compares the specified object with this map for equality.
Returns true if the given object is also a map and the two
Maps represent the same mappings. More formally, two maps t1
and t2 represent the same mappings if
t1.entrySet().equals(t2.entrySet()). This ensures that the
equals method works properly across different implementations
of the Map interface.
Tento obecný kontrakt musí splňovat HashMap, který používáme
v příkladě.
Ať čtu jak čtu, to co jste uvedl (že měnit hashcode objektu v
mapě nelze) tam nevidím. Je pravda, že HashMap.hashCode() se
zmení, ale pokud je i nadále splněn obecný kontrakt
hashCode() (tj. že musí být v souladu s equals(), a to je),
obecné kontrakty by měly platit jak před změnou, tak po změně.
Mohl bych poprosit o objasnění?
Mirek
-Original Message-
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] On Behalf Of Podlesak Kamil
Sent: Wednesday, May 23, 2007 11:39 AM
To: Java
Subject: RE: hashset contains wtf
Zdravim,
To je proste: Map#hashCode() presne definuje ze vysledek musi
byt vypocitan jako soucet hashcode vsech zaznamu. Pridanim
noveho prvku se tedy zmeni hodnota hashCode.
Jenomze HashSet (resp. HashMap, kterou interne pouziva)
zarazuje i hleda zaznamy podle hashCode(). Jakmile se
hashCode zmeni, tak hleda jinde a nenajde.
Plati obecne pravidlo:
Objekty vkladane do hash mapy NESMI MENIT svuj hashCode()!
Tedy alespon po dobu, co jsou v mape.
Konkretne pak plati:
Kolekce (Map, Collection) vlozene do hash mapy se NESMI MODIFIKOVAT.
Pokud potrebujete mit v mnozine kolekce ktere bezne
modifikujete, pouzijte IdentityHashMap.
-Original Message-
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] Behalf Of Tomas Zverina
Sent: Wednesday, May 23, 2007 11:24 AM
To: Java
Subject: hashset contains wtf
Zdravim,
nekdo do me prosim vase kopnete, a vysvetlete mi, proc je vystup
nasledujiciho programu:
import java.util.*;
public class HashSetPokus {
public static void main(String[] args) {
{
// Experiment s HashSet
Map element1 = new HashMap();
SetMap container1 = new HashSetMap();
container1.add(element1);
System.out.println(1a: +container1.contains(element1));
container1.iterator().next().put(a, 123);
System.out.println(1b: +container1.contains(element1));
}
{
// Experiment s ArrayList
Map element2 = new HashMap();
ListMap container2 = new ArrayListMap();
container2.add(element2);
System.out.println(2a: +container2.contains(element2));
container2.iterator().next().put(a, 123);
System.out.println(2b: +container2.contains(element2));
}
}
}
takovyhle:
1a: true
1b: false
2a: true
2b: true
misto ocekavaneho:
1a: true
1b: true
2a: true
2b: true
Ja jsem z toho zverina.
--
S pozdravem,
Tomas Zverina
Multimedia atelier s.r.o.
Na Dolinách 4
147 00 Praha 4
IČO: 25127071
tel.: 241 433 120
e-mail: [EMAIL PROTECTED]
http://www.m-atelier.cz/
Společnost Multimedia atelier s.r.o. je zapsána u
rejstříkového soudu
v Praze, oddíl C, vložka 51961.
RE: hashset contains wtf
Děkuji za objasnění, už rozumím (naprosto dokonale). Jednoznačně je to chyba v javadoc. Mirek -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Josef Cacek Sent: Wednesday, May 23, 2007 12:11 PM To: Java Subject: Re: hashset contains wtf Ahojte, On 5/23/07, Stöhr Miroslav RNDr. Ph.D. [EMAIL PROTECTED] wrote: Ať čtu jak čtu, to co jste uvedl (že měnit hashcode objektu v mapě nelze) tam nevidím. Je pravda, že HashMap.hashCode() se zmení, ale pokud je i nadále splněn obecný kontrakt hashCode() (tj. že musí být v souladu s equals(), a to je), obecné kontrakty by měly platit jak před změnou, tak po změně. Mohl bych poprosit o objasnění? Sun nemá dost dokumentátorů, aby to fixnul v JavaDocu :-) (radši změní stav na: Closed, not a bug) http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4459681 Mirek -- pepa cacek
Re: hashset contains wtf
Ale HashMap tento kontrakt splňuje. Do Setu vložíte nejprve prázdnou mapu, a
následně jí porovnáváte s mapou s jedním prvkem. V kontraktu není nikde
uvedeno, zda se bude hodnota porovnávat s aktuální hodnotou, nebo s vloženou
hodnotou. Pokud tedy prvky kolekce měníte za běhu (což obecně není dobrý
nápad), musíte se podívat, jak se chová konkrétní implementace. A každá
implementace založená na hash bude prvky srovnávat podle hodnoty hashe v
okamžiku vložení (jinak by ten hash neměl žádný význam).
Filip Jirsák
23.5.07, Stöhr Miroslav RNDr. Ph.D. [EMAIL PROTECTED]:
Děkuji za objasnění zajímavé vlastnosti těchto objektů, které jsem si
prozatím nebyl vědom. Jenom mi není jasné následující:
1/ Set.contains(Object o)
Returns true if this set contains the specified element. More formally,
returns true if and only if this set contains an element e such that
(o==null ? e==null : o.equals(e)).
Tento obecný kontrakt musí splňovat i HashSet, který používáme v příkladě.
2/ Z toho plyne, že metoda contains() v uvedeném příkladě volá metodu
Map.equals. U té je uvedeno:
Compares the specified object with this map for equality. Returns true if
the given object is also a map and the two Maps represent the same mappings.
More formally, two maps t1 and t2 represent the same mappings if
t1.entrySet().equals(t2.entrySet()). This ensures that the equals method
works properly across different implementations of the Map interface.
Tento obecný kontrakt musí splňovat HashMap, který používáme v příkladě.
Ať čtu jak čtu, to co jste uvedl (že měnit hashcode objektu v mapě nelze)
tam nevidím. Je pravda, že HashMap.hashCode() se zmení, ale pokud je i
nadále splněn obecný kontrakt hashCode() (tj. že musí být v souladu s
equals(), a to je), obecné kontrakty by měly platit jak před změnou, tak po
změně.
Mohl bych poprosit o objasnění?
Mirek
-Original Message-
From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On
Behalf Of Podlesak Kamil
Sent: Wednesday, May 23, 2007 11:39 AM
To: Java
Subject: RE: hashset contains wtf
Zdravim,
To je proste: Map#hashCode() presne definuje ze vysledek musi byt
vypocitan jako soucet hashcode vsech zaznamu. Pridanim noveho prvku se tedy
zmeni hodnota hashCode.
Jenomze HashSet (resp. HashMap, kterou interne pouziva) zarazuje i hleda
zaznamy podle hashCode(). Jakmile se hashCode zmeni, tak hleda jinde a
nenajde.
Plati obecne pravidlo:
Objekty vkladane do hash mapy NESMI MENIT svuj hashCode()! Tedy alespon
po dobu, co jsou v mape.
Konkretne pak plati:
Kolekce (Map, Collection) vlozene do hash mapy se NESMI MODIFIKOVAT.
Pokud potrebujete mit v mnozine kolekce ktere bezne modifikujete, pouzijte
IdentityHashMap.
-Original Message-
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] Behalf Of Tomas Zverina
Sent: Wednesday, May 23, 2007 11:24 AM
To: Java
Subject: hashset contains wtf
Zdravim,
nekdo do me prosim vase kopnete, a vysvetlete mi, proc je vystup
nasledujiciho programu:
import java.util.*;
public class HashSetPokus {
public static void main(String[] args) {
{
// Experiment s HashSet
Map element1 = new HashMap();
SetMap container1 = new HashSetMap();
container1.add(element1);
System.out.println(1a: +container1.contains(element1));
container1.iterator().next().put(a, 123);
System.out.println(1b: +container1.contains(element1));
}
{
// Experiment s ArrayList
Map element2 = new HashMap();
ListMap container2 = new ArrayListMap();
container2.add(element2);
System.out.println(2a: +container2.contains(element2));
container2.iterator().next().put(a, 123);
System.out.println(2b: +container2.contains(element2));
}
}
}
takovyhle:
1a: true
1b: false
2a: true
2b: true
misto ocekavaneho:
1a: true
1b: true
2a: true
2b: true
Ja jsem z toho zverina.
--
S pozdravem,
Tomas Zverina
Multimedia atelier s.r.o.
Na Dolinách 4
147 00 Praha 4
IČO: 25127071
tel.: 241 433 120
e-mail: [EMAIL PROTECTED]
http://www.m-atelier.cz/
Společnost Multimedia atelier s.r.o. je zapsána u rejstříkového soudu
v Praze, oddíl C, vložka 51961.
--
Filip Jirsák
[EMAIL PROTECTED]
Re: hashset contains wtf
Ahoj, pokud vim, tak se da proti javadoc zadat buga, minimalne ja jsem uz neco zadaval. Takze pokud tam neco chybi, muzes to zadat: http://bugs.sun.com/bugdatabase Vyvojari JDK maji vic bug nez muzou zpracovat, ale treba se tomu nekdo bude venovat, ted kdyz je java open source je ta pravdepodobnost vetsi nez drive. -Roman Tomas Zverina wrote: Diky vsem za vysvetleni. Jestli to tu jeste nikdo nerikal, tak jsem nasel: Zadny hashCode by se za behu nemel menit: http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Object.html#hashCode() Ovsem tady se vyslovne nepise, ze by se menil: http://java.sun.com/j2se/1.5.0/docs/api/java/util/AbstractMap.html#hashCode() Ono by to asi slo korektne vyresit jedine tak, ze by hashCode libovolne HashMap byla napr. 0 - po celou dobu behu. Tim by se sice ztratilo hodne vykonu :-), ale chodilo by to spravne. Nebo tedy upozornit v Javadoc na to, ze se meni.
RE: hashset contains wtf
Děkuji za objasnění, už rozumím (naprosto dokonale). Jednoznačně je to chyba v javadoc. Možná se moje odpověď nebude někomu líbit, ale podle mne v javadoc chyba není. Toto chování vyplývá z vlastností hešových tabulek a měla by to proto vysvětlit učebnice (nebo lektor) jako obecnou vlastnost všech objektů využívajících hešových tabulek. Jestli k vám takováto informace ještě nepronikla, spílejte svým učitelům a autorům učebnic, z nichž jste se Javu učili. Rozlišujte javadoc a učebnici. Kdyby se měly dávat do javadoc i takovéto věci, tak tam za chvíli někdo bude chtít vysvětlit, jak funguje interface nebo jiný jazykový konstrukt. Pro javadoc by mělo stačit prohlášení, že daný kontejner je definován pomocí hešových tabulek, a to tam je. Tím nechci říst, že by javadoc nějakou drobnou zmínku na toto téma nesnesl, ale chápu, proč se Sunům nechce do něj dávat věci, které mají být primárně vysvětleny jinde. Já bych jim spíš vyčítal, že tuto informaci nedali do tutoriálu (leda bych ji tam ve své slepotě nenašel) - tam podle mne patří. Já bych tam zařadil kapitolku o hešových tabulkách, na kterou by se pak odvolávaly všechny kapitoly pojednávajících o kontejnerech, které jsou na hešových tabulkách založeny.
