[Java] hashcode voor int[]

[Alarmnummer]

hoe kan ik een unieke hashcode maken voor een array van integers? Ik heb dit namelijk nodig omdat ik hashtable wil gebruiken voor zoeken ipv dom door array heen te lopen.

ben nu aan het kijken hoeveel performance winst ik kan halen door andere geheugen structuren.

ik zit dit moment al op 3.5 keer de orginele snelheid (eerst arraylisten en nu arrays).


[edit]
mogelijke opl. maak er allemaal even lange strings van.. dus als string lengte = 8 dan zal 10 00000010 opleveren en 1000 zal 00001000 opleveren. Door ze allemaal aan elkaar vast te plakken krijg je een uni eke string en dezen maken per def een unieke hashcode. Maar er is vast wel een betere manier.

[Alarmnummer]

zo`n functie is volgens mij verdomde praktisch omdat je nu heel eenvoudig op een combinatie van objecten kan zoeken en doordoor met een enkele hashcode berekening ieder object kan vinden.

[Alarmnummer]

Hmmm.. foutje..

als je een getal hebt gevorm door 2 16bits getallen

bv FFFF.FFFF (32 bits getal)

en je zou in een 16 bits systeem zitten

dan kun je maximaal FFFF combinaties maken (en dus FFFF elementen kunnen aanspeken), en zeker geen FFFF.FFFF verschillende elementen. En als je 10 16bits getallen zou combineren zou je ook 16*10 bits nodig hebben Een 160 bits systeem en voor n 16 bits getallen heb je een n*16 bits systeem nodig....

aaarrggghhhhh

[Alarmnummer]

en hoe zit het dan bij een string. String maakt gebruik van unicode, dat betekend dat er voor elk character 16 bits is gereserveerd. Laten we er van uitgaan dat een string verder geen ruimte kost dan hebben voor een string van 30 characters 30 * 16 bits nodig. Dit kan dus duidelijk niet. Het is dus mogelijk dat er meerdere string zijn( 29d*FFFFh stuks zelfs) die dezelfde hashcode opleveren. Dus een hashcode is niet voldoende om je element te identificeren. Hmmmm... moet ik mijn hashcode kennis maar eens goed gaan opfrissen

Ze gaan natuurlijk alle buckets bij langs om alle elementen te controleren of ze werkelijk gelijk zijn.

stom stom

[.oisyn]

leuk he, zo'n monoloog

[Alarmnummer]

Op zaterdag 19 januari 2002 02:32 schreef Alarmnummer het volgende:
en hoe zit het dan bij een string. String maakt gebruik van unicode, dat betekend dat er voor elk character 16 bits is gereserveerd. Laten we er van uitgaan dat een string verder geen ruimte kost dan hebben voor een string van 30 characters 30 * 16 bits nodig. Dit kan dus duidelijk niet. Het is dus mogelijk dat er meerdere string zijn die dezelfde hashcode opleveren. Dus een hashcode is niet voldoende om je element te identificeren. Hmmmm... moet ik mijn hashcode kennis maar eens goed gaan opfrissen

Ze gaan natuurlijk alle buckets bij langs om alle elementen te controleren of ze werkelijk gelijk zijn.

stom stom

Maarja.. ik kan wel zoiets gebruiken om snel mijn elementen te vinden, hoef alleen de equals aan te passen (er kunnen in mijn systeem meerdere objecten zijn die eigelijk hetzelde zijn). En ik hoef niet eens moeilijk te doen met die vaste lengtes hoef alleen te garanderen Ik ben er uit

[edit]
altijd leuk om je eigen post`s te beantwoorden

[Alarmnummer]

Op zaterdag 19 januari 2002 02:34 schreef OiSyN het volgende:
leuk he, zo'n monoloog

Ik vind het erg fijn, ik ben het altijd met mezelf eens

[.oisyn]

heb je er niet al eens over zitten denken om naar zo'n praatgroep te gaan voor schizofrenie?

"iemand anders nog koffie?"

[mbravenboer]

Hum, vaag topic . Kijk anders eens naar de manier waarop hashdcodes voor lists worden uitgerekend. Ik heb het weleens gejat. Het was wel een inventief truckje .

[Tomatrix]

Deze werkt ook maar is niet erg efficient:

code:

public static int hashCode (int[] array) {
StringBuffer sb = new StringBuffer ();

for (int i = 0; i < array.length; i++) {
sb.append (String.valueOf (array [i]);
}
return sb.toString ().hashCode ();
}

[Alarmnummer]

Ik heb net even die hashtables erin gezet, en ik zit nu 11.1 keer de orginele snelheid. Het aantal zoekacties is dramatisch afgenomen.

Maar ik weet nog een enorme logische optimalisatie te zitten, die neem ik straks wel even te pakken.

en de abstractList vermenigvuldigd de hashcodes van ieder element met 31 en telt die allemaal bij elkaar op. Ook lekker snel En ik cache natuurlijk ook alles