[java] Long representatie van een string

[oogapp0ltje]

Momenteel sla ik objecten op als keys in een hashmap. Om te kijken of een object reeds bestaat in deze hashmap gebruik ik containsKey.

Het probleem is dat containsKey alleen werkt voor de instantie van het object zelf. Als ik een object opnieuw aanmaak met dezelfde eigenschappen als dit key-object werkt het niet met containsKey.

Ik heb bedacht om de (unieke) string representatie van dit object te vertalen naar een numerieke waarde (een long bijvoorbeeld). Deze longwaarde gebruik ik dan als key voor de hashmap, dit werkt ook sneller dan wanneer ik de string-representatie als key gebruik.

Ik weet alleen niet goed hoe ik een string kan converten naar een long (lees: een string die dus geen valide long-waarde bevat). Ik kan de charactercodes bij elkaar optellen, maar dit getal markeert niet de volgorde waarin deze karakters voorkomen, hoe kan ik dit het beste doen?

[truegrit]

misschien met een 32 of 64 bit hash waarde van de String?

[RayNbow]

Die String representatie die je maakt... is een String. Een String is een object en kent de hashCode() methode.

Simpel voorbeeldje:

Java:

public class MyClass {
    int eigenschap1;
    String eigenschap2;

    public boolean equals(Object other) {
        if (other instanceOf MyClass) {
            MyClass that = (MyClass) other;
            return (other.eigenschap1 == this.eigenschap1)
                && other.eigenschap2.equals(this.eigenschap1);
        }
        else
            return false;
    }

    public String toString() {
        return "MyClass<" + eigenschap1 + "," + eigenschap2 + ">";
    }
    
    public int hashCode() {
        return toString.hashCode();
    }
}

[Alarmnummer]

Mbv een hashcode kan je een object niet uniek identificeren. In principe zou een constante als hashcode ook correct zijn, alleen lopen je emmers dan over. Dus een key maken op basis van een hashcode gaat problemen opleveren.

[ Voor 62% gewijzigd door Alarmnummer op 01-07-2006 07:59 ]

[BalusC]

Momenteel sla ik objecten op als keys in een hashmap. Om te kijken of een object reeds bestaat in deze hashmap gebruik ik containsKey.

Het probleem is dat containsKey alleen werkt voor de instantie van het object zelf. Als ik een object opnieuw aanmaak met dezelfde eigenschappen als dit key-object werkt het niet met containsKey.

Ik gok dat je van elk object maar één instantie wil hebben? Zo ja, kijk dan eens naar het singleton pattern

[oogapp0ltje]

BalusC schreef op zaterdag 01 juli 2006 @ 09:26:
[...]
Ik gok dat je van elk object maar één instantie wil hebben? Zo ja, kijk dan eens naar het singleton pattern

juist niet, ik probeerde in bovenstaande situatie een exact duplicaat van een object na te bouwen met dezelfde eigenschappen om vervolgens te kijken of het origineel in de hashmap zit met containsKey. Dit werkt niet.

Dit wil ik nu oplossen door het duplicaatobject te vertalen naar een unieke code, het originele object staat ook opgeslagen onder deze code in de hashmap, immers hebben ze beide dezelfde eigenschappen.

Ik zoek dus een toLong() manier die een toString() kan vertalen in een Long. Ik zorg er dan voor dat de toString() methode een representatie teruggeeft van de eigenschappen van de klasse. HashCode is een goed idee, maar volgens mij geeft dit geen unieke code terug die bepalend is voor de eigenschappen in mijn object. Feitelijk zoek ik gewoon een soort encoding waarmee ik van String naar long kan en viceversa.

[oogapp0ltje]

De Python code op deze URL kan mijn probleem wel eens oplossen.
http://aspn.activestate.c...book/Python/Recipe/440627

eens kijken hoe de vertaling in Java hiervan zijn werk doet.

[NetForce1]

Volgens mij ben je op zoek naar de equals() metode die op Object gedefinieerd is. Als je een object als key wil gebruiken in een Map moet je equals en hashcode overriden, zie ook de API-docs van Map en aanverwanten.

[ Voor 4% gewijzigd door NetForce1 op 01-07-2006 12:39 ]

[MSalters]

Ravenof schreef op zaterdag 01 juli 2006 @ 10:43:
HashCode is een goed idee, maar volgens mij geeft dit geen unieke code terug die bepalend is voor de eigenschappen in mijn object.

Uiteraard niet. Als je een object hebt wat zelf twee Hashcodes bevat, dan kun je dat niet volledig beschrijven met 1 Hashcode.

Feitelijk zoek ik gewoon een soort encoding waarmee ik van String naar long kan en viceversa.

Onmogelijk, om dezelfde reden. Neem de verzameling van strings die je krijgt door twee longs.toString achter elkaar te zetten, dus beginnend met "0:0". Het moge duidelijk zijn dat er daar 2¹²⁸ van zijn. Als je die naar één long zou willen mappen, dan hou je er dus 2¹²⁸-2⁶⁴ over.

[misfire]

De standaard HashMap verzameling klasses van Java optimaliseren standaard al voor je op de manier die je graag wilt. De hashcode() van een String wordt gebruikt om de verzameling op te delen in buckets. Als je vervolgens gaat zoeken dan wordt eerst de hashcode gebruikt om een binary search naar de goede bucket te doen, vervolgens wordt met equals de String vergeleken. Als ik jou was zou ik eerst proberen of dit niet gewoon snel genoeg is.

Het uniek representeren van een String in een Long is onmogelijk vanwege de verschillen in range (een String kan meer verschillende waardes bevatten dan een Long), tenzij je beperkingen oplegt aan de String key waarde. Als je over de beperkingen hebt nagedacht is het op zich zelf redelijk triviaal om hierna een long-conversie op te stellen.

[oogapp0ltje]

misfire schreef op zaterdag 01 juli 2006 @ 13:16:
De standaard HashMap verzameling klasses van Java optimaliseren standaard al voor je op de manier die je graag wilt.

Betekend dit dat het qua performance niet uitmaakt of ik een long als key gebruik ipv. een String? Let wel dat het uiteindelijk om een zeer grote hashmap gaat (in de groote van tientallen tot honderden MB's).

[Daos]

De String die je maakt van inhoud kan je gewoon als Key gebruiken. De Hashcode van een String is afhankelijk van de inhoud. 2 gelijke Strings => dezelfde HashCode.

Als je het mooi wilt doen, dan override je de equals() en hashCode() van je object (je kan daarin ook die String gebruiken). Je kan dan gewoon je object als Key gebruiken.

[edit]
En dat staat dus hierboven al een paar keer:
[rml]RayNbow in "[ java] Long representatie van een string"[/rml]
[rml]NetForce1 in "[ java] Long representatie van een string"[/rml]
[rml]misfire in "[ java] Long representatie van een string"[/rml]


Ik had de draad niet goed gelezen.

[ Voor 39% gewijzigd door Daos op 01-07-2006 14:34 ]

[The - DDD]

@Ravenof
Lees gewoon even goed de API docs, dan wordt het helemaal duidelijk.

containsKey van Map zegt dat een true resultaat van equals een hit oplevert.
Als je vervolgens bij equals kijkt, zie je dat je wanneer je equals implementeert, je ook hashcode moet implementeren.

Belangrijk hierbij is om te onthouden dat wanneer equals true oplevert voor twee objecten deze beide objecten ook een gelijke hashcode dienen te hebben. Omgekeerd geldt dit echter niet.

Enne, hashcodes zijn nog altijd int's in Java.

[MSalters]

Afhankelijk van de inhoud van het object kun je de hascode method heel veel effectiever krijgen dan de default. Maar uiteraard is dat iets wat je - net als alle andere optimalisaties - pas doet op het moment dat duidelijk is dat het nodig is.

[misfire]

Ravenof schreef op zaterdag 01 juli 2006 @ 14:23:
[...]

Betekend dit dat het qua performance niet uitmaakt of ik een long als key gebruik ipv. een String? Let wel dat het uiteindelijk om een zeer grote hashmap gaat (in de groote van tientallen tot honderden MB's).

Qua geheugengebruik kan het iets uitmaken omdat een Long wat minder bytes beslaat dan een String, maar verder is het qua performance vergelijkbaar.

Als je het over een HashMap van honderden MB's hebt dan heb je echter zowieso een probleem, of je nu een Long of een String als key gebruikt. Het is helemaal niet handig om zulke grote verzamelingen actief in het geheugen te houden, dat is moordend voor de algemene performance van de applicatie. Heb je al eens gekeken naar cachen in een file, lazy (un)loading, of een embedded database oplossing?

[oogapp0ltje]

misfire schreef op zaterdag 01 juli 2006 @ 16:03:
[...]
Qua geheugengebruik kan het iets uitmaken omdat een Long wat minder bytes beslaat dan een String, maar verder is het qua performance vergelijkbaar.

Als je het over een HashMap van honderden MB's hebt dan heb je echter zowieso een probleem, of je nu een Long of een String als key gebruikt. Het is helemaal niet handig om zulke grote verzamelingen actief in het geheugen te houden, dat is moordend voor de algemene performance van de applicatie. Heb je al eens gekeken naar cachen in een file, lazy (un)loading, of een embedded database oplossing?

De toegangssnelheid tot gegevens uit het geheugen is veel groter dan wanneer deze informatie on-request uit een database / file gelezen moet worden, mits de tijd die het duurt om deze gegevens uit het geheugen te benaderen klein is. Een hashmap / B-Tree lijkt mij dan ook de meest efficiente manier om deze gegevens op te slaan.

[Soultaker]

Volgens mij worden er een aantal dingen door elkaar gehaald, en er staan wat rare suggesties waardoor de goede oplossing niet naar boven komt.

Ravenof schreef op zaterdag 01 juli 2006 @ 01:30:
Momenteel sla ik objecten op als keys in een hashmap. Om te kijken of een object reeds bestaat in deze hashmap gebruik ik containsKey.

Fair enough.

Het probleem is dat containsKey alleen werkt voor de instantie van het object zelf.

Nee, dat is onjuist. Het werkt ook voor 'andere' objecten die gelijk zijn aan de opgeslagen instantie, mits je equals() en hashCode() correct hebt geïmplementeert. Een belangrijke eis is dat a.equals(b) impliceert a.hashCode() == b.hashCode() -- in de praktijk betekent dat dus dat als je equals() override, je ook hashCode() moet overriden (en als je dat niet doet, werken objecten zoals HashMap die hashCode() gebruiken niet goed, zoals je gemerkt hebt).

De juiste oplossing voor je probleem is dus simpelweg hashCode() goed te implementeren. In plaats van je object een Long in je map stoppen is eigenlijk gewoon een slecht idee en de constructie met toString().hashCode() werkt niet omdat hashcodes niet gegarandeerd uniek zijn. Wel kun je toString().hashCode() 'misbruiken' om heel makkelijk hashCode() te implementeren; beter is natuurlijk om de conversie naar string over te slaan.

Betekend dit dat het qua performance niet uitmaakt of ik een long als key gebruik ipv. een String? Let wel dat het uiteindelijk om een zeer grote hashmap gaat (in de groote van tientallen tot honderden MB's).

Je moet noch die Long noch die String gebruiken, maar gewoon het object in kwestie, met een goede hashCode() implementatie. Pas als profiling uitwijst dat dat niet effecient zou ik wat anders overwegen. Denk eraan dat hashCode() maar één keer wordt aangeroepen als hasKey() aanroept; daarna wordt er alleen een aantal (vaak nul of één) keer equals uitgevoerd.

MSalters schreef op zaterdag 01 juli 2006 @ 15:08:
Afhankelijk van de inhoud van het object kun je de hascode method heel veel effectiever krijgen dan de default.

De default implementatie (Object.hashCode) returnt (in Sun's JVM tenminste) één of andere identifier gebaseerd op het interne adres. Effectiever wordt het echt niet. Het probleem met de default implementatie is niet dat 'ie niet efficiënt is, maar dat 'ie gewoon niet correct is voor objecten die equals() herdefiniëren.

[misfire]

Ravenof schreef op zaterdag 01 juli 2006 @ 16:25:
[...]
De toegangssnelheid tot gegevens uit het geheugen is veel groter dan wanneer deze informatie on-request uit een database / file gelezen moet worden, mits de tijd die het duurt om deze gegevens uit het geheugen te benaderen klein is. Een hashmap / B-Tree lijkt mij dan ook de meest efficiente manier om deze gegevens op te slaan.

Dat klopt voor deze situatie, maar je moet wel het grote plaatje in de gaten houden. Het programma dat je aan het maken bent doet als het goed is heel wat meer dan alleen wat objecten uit een HashMap plukken. Bij die andere operaties heb je nu veel minder werkgeheugen over. Afhankelijk hoe de HashMap gevuld wordt (write-once, of continu aanpassen in de Map) verstoort zoon grote Map ook de normale generationele garbage collection algoritmes, en krijg je dus meer full-gc's, ook slecht voor de performance. Ga je de applicatie draaien op een omgeving waar ook andere applicaties actief zijn? Dan hebben die andere applicaties nu te weinig geheugen, of nog erger, jouw applicatie wordt in het virtueel geheugen gedrukt en zit van de hard disk te swappen.

Wellicht is voor jouw toepassing een HashMap de meest geschikte oplossing, maar je stelt de vraag omdat je bezorgd bent over de prestaties. Een Long of een Key als String gebruiken is imho slechts gerommel in de marge, maar je zou kunnen meten in jouw situatie om te kijken of het ook echt effect heeft. Bij grote objectverzamelingen in het geheugen moet je ook rekening houden met de impact op de rest van je omgeving. En dan kan de keuze best anders uitpakken.

[oogapp0ltje]

misfire schreef op zondag 02 juli 2006 @ 11:07:

Dat klopt voor deze situatie, maar je moet wel het grote plaatje in de gaten houden. Het programma dat je aan het maken bent doet als het goed is heel wat meer dan alleen wat objecten uit een HashMap plukken. Bij die andere operaties heb je nu veel minder werkgeheugen over. Afhankelijk hoe de HashMap gevuld wordt (write-once, of continu aanpassen in de Map) verstoort zoon grote Map ook de normale generationele garbage collection algoritmes, en krijg je dus meer full-gc's, ook slecht voor de performance. Ga je de applicatie draaien op een omgeving waar ook andere applicaties actief zijn? Dan hebben die andere applicaties nu te weinig geheugen, of nog erger, jouw applicatie wordt in het virtueel geheugen gedrukt en zit van de hard disk te swappen.

Wellicht is voor jouw toepassing een HashMap de meest geschikte oplossing, maar je stelt de vraag omdat je bezorgd bent over de prestaties. Een Long of een Key als String gebruiken is imho slechts gerommel in de marge, maar je zou kunnen meten in jouw situatie om te kijken of het ook echt effect heeft. Bij grote objectverzamelingen in het geheugen moet je ook rekening houden met de impact op de rest van je omgeving. En dan kan de keuze best anders uitpakken.

De applicatie draait op een dedicated server die alleen bestemd is voor deze applicatie, de applicatie mag 80% van het memory gebruiken dat aan de VM is toegekend voor de datastorage in de hashmap. Natuurlijk kan ik met deze marge spelen mbv. profiling naderhand, ik denk dat het daarom te vroeg is om dit idee van de hand te wijzen. Gegevens die niet meer in het geheugen passen omdat 80% behaald is worden alsnog uit de database geladen.

misfire schreef op zondag 02 juli 2006 @ 11:07:

Ga je de applicatie draaien op een omgeving waar ook andere applicaties actief zijn? Dan hebben die andere applicaties nu te weinig geheugen, of nog erger, jouw applicatie wordt in het virtueel geheugen gedrukt en zit van de hard disk te swappen.

Ja dat is dus niet waar, in JBoss (of volgens mij welke appserver dan ook) kun je aangeven hoeveel memory je applicatie mag consumen.

[oogapp0ltje]

Soultaker schreef op zaterdag 01 juli 2006 @ 19:38:

Goede tips in je bericht, ik ga hier verder naar kijken. bedankt.

[misfire]

Ravenof schreef op maandag 03 juli 2006 @ 10:32:
[...]
Ja dat is dus niet waar, in JBoss (of volgens mij welke appserver dan ook) kun je aangeven hoeveel memory je applicatie mag consumen.

De geheugenlimiet die je in kunt stellen geldt voor de complete server instantie, dus JBoss plus alle EARS/WARS die er op draaien. Aangezien je al beschrijft een dedicated server te hebben is in jouw situatie alleen van belang dat JBoss/de rest van je eigen app genoeg geheugen heeft. Overigens is welke limiet dan ook geen oplossing: de applicatie zou dan crashen als de limiet wordt overschreden en dat lijkt me ook niet de bedoeling.

Het was niet mijn bedoeling om nu de hele applicatie ter discussie te stellen maar ik vroeg me alleen af of je al stilgestaan had bij dit soort issues. Blijkbaar had je hier dus al over nagedacht. Veel succes met de oplossing en we horen het verder wel.