Jeg har lavet en klasse Cell, der på samme måde som Point-klassen gemmer en værdi x og y. Yderligere har jeg et HashSet, der som bekendt ikke tillader to objekter, der returnerer samme hashCode(), at være indeholdt i Set'et.
Problemet er nu følgende: Hvordan sikrer jeg at mit hashset ikke indeholder to cell-objekter, der har samme x og y værdi?.
Løsningen burde jo blot være at overskrive hashCode()-metoden i min Cell-klasse, men det kræver, at jeg finder en måde at beregne et unikt ID udelukkende ud fra cellens x og y værdier, velatmærke på en sådan måde, at ingen anden celle med andre x og y værdier kan have samme ID. Naivt kunne man konstruere følgende hashCode()-metode:
public int hashCode(){ return x+y; }
Anvender vi denne metode, kan vi med få eksempler se, at den ikke duer. Beregner vi hashCode() får følgende punkter får vi så: (2,3):5, (5,4):9, (1,3):4, (1,4):5
Vi ser straks, at hashCode()-værdien for det første og sidste punkt er den samme, selvom de har forskellige koordinatsæt.
Jeg efterlyser altså en hashCode()-metode, der fungerer, så ingen punkter med forskellige koordinatsæt kan give den samme hash-værdi! Måske er løsningen enkel.. jeg har nemlig lagt mærke til, at Point-objekter, der har det samme koordinatsæt (x,y) returnerer den samme hashCode. Hvordan gør Point-klassen dette?
class Cell { private static int cellenummer = 0; private static final int MAX_ANTAL_CELLER = 1000; // eller hvormange du synes private x, y; public Cell ( int x, int y ) { cellenummer++; // ændres ingen andre steder this.x = zx; this.y = y; } public long hashcode() { return ((long)x*y*1000)+cellenummer; } ...
jakoba> Jeg har også tænkt på den metode, men programmet skal kunne håndtere et vilkårligt antal celler, og må derfor kun beregne hashCode()'en ud fra x og y...
rasmusbg: tak - umiddelbart forstår jeg dog ikke helt præcist, hvordan hashCode'en beregnes, men kan du forsikre mig om, at der ikke findes to koordinatsæt (x,y), der kan returnere den samme hashCode() med den metode?
rasmusbg> Umiddelbart siger min intuition mig, at der GODT kan være to punkter, der returnerer den samme hashCode, men med de operationer, de laver på tallene x og y, ser det ud som om, at det er utroligt sjældent at det sker.... det vil jeg så overveje om jeg kan leve med .. hehe.. hvis du vil have nogle points må du lige smide et svar
det var egentlig også en fjoget måde at gøre det. En nemmere og enklere måde er: class Cell { private static int cellenummer = 0; private x, y; public Cell ( int x, int y ) { cellenummer++; // ændres ingen andre steder this.x = zx; this.y = y; } public long hashcode() { return cellenummer; } ...
nu kan du lave 2^32 celler og de vil allesammen have forskellig 'hashkode'.
jakoba> Jeg tror, du har misforstået mig lidt.... det er ret væsentligt at to Celler, der har samme koordinatsæt ikke er indeholdt i mit HashSet. Din metode er jo ikke bedre end den hashCode()-metoden, der nedarves efter Object(), som jo beregner hash-værdien ud fra den enkelte instans adresse(mener jeg da), og derfor også gør alle celler unikke... Jeg håber, du forstår
Man må formode, at hvis der laves to Celle objekter (kald dem celle1 og celle2), hvor de begge har (x,y) sat til det samme (f.eks. (2,3)), så er de ens, derfor burde celle1.equals(celle2) returnere true. Ifølge Java's definition af hashCode(), så SKAL celle1.hashCode() == celle2.hashCode(). Med din hashCode() vil dette ikke være tilfældet.
Desværre kan jeg ikke overbevise mig selv rent matematisk om, at Point's hashCode rent faktisk returnerer en unik hashkode hver eneste gang - der bliver jeg nødt til at stole på Sun's udvikler-team ;)
rasmusbg: jeg stoler ikke på solskinsgutterne før jeg har set et matematisk bevis, men indtil videre forlader jeg mig på deres autoritet (Hehe). Jeg har dog stadig i sinde at sende problemet videre til min matematiklærer... Jeg takker dog stort alligevel (-:
1) Din hashcode skal aflevere nogenlunde pænt fordelte tal. Der må gerne være ens hashværdier for forskellige x og y 2) Du *skal* også definere equals()-funktionen - den bliver nemlig kaldt hvis der er to hashværdier der er ens.
Det er naturligvis bedst at få fordelt hashværdierne så godt som muligt, men det er ikke nødvendigt, og yderst sjældent at man kan sikre de er unikke.
men nu jeg læser grundigt så fatter jeg alligevel ikke. Er du 100% på at et hashset ikke tillader 2 objekter med samme hashcode at være indeholdt i settet? Hele fidusen med hashkoder er jo at de ikke behøver at være unikke, bare de er rimeligt spredt.
public int hashCode() { long bits = java.lang.Double.doubleToLongBits(x); bits ^= java.lang.Double.doubleToLongBits(y) * 31; return (((int) bits) ^ ((int) (bits >> 32))); }
Det, du siger omkring kravene til hashCode() er også enormt fornuftigt. Du har selvfølgelig ret i, at det er vigtigt, at den er spredt således, at equals() næsten aldrig bliver kaldt. Samtidig vil equals jo sikre, at der aldrig er nogen ens koordinatsæt i mit hashset, så det er jo alletiders. Jeg betragter mit problem som løst (-:
erikjacobsen og rasmusbq smid lige et svar, så deler jeg pointene ud...
og med hensyn til, at den skal være effektiv betyder det ikke det store... mit codesnippet er nemlig ikke helt korrekt.. jeg tilskriver den som final i konstruktøren, da både x og y er final for hver celle... (-: Jeg takker endnu en gang
Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.
