[java] - hashmap duplicate keys

[Cavalera125]

Voor school ben ik bezig met een opdracht over hashmaps. Het gaat om het volgende, een opdracht om trefwoorden te koppelen aan een bestandsnaam. Zoals 'paard -> test1.doc', 'schaap -> test1.doc', 'paard->test3.doc'.

Zoals je ziet is het trefwoord de key in de map en de bestandsnaam de value. Het kan dus voorkomen dat een trefwoord bij meerdere bestandsnamen hoort. Hoe kan ik dit oplossen?

Zelf heb ik geprobeerd om voor iedere bestandsnaam een nieuwe map te maken en deze map dan in de hoofdmap als volgt in te voegen

code:

String key = "" + i;
map.put(i, nieuwemap);

Ik zit er nu al twee uur naar te kijken. En gegoogled, maar ik kom er echt niet meer uit.

[Zoijar]

Standaard oplossing is een linked list als values bij elke gehashde key. Er zijn meer geavanceerde oplossingen, maar ik denk dat je die niet nodig hebt...(ben zelf toevallig net bezig met hashes met false positives en negatives)

[voodooless]

ipv direct een bestandsnaam om je hashmap te frotten gebruik je een Vector, waar dan je bestandsnamen zet, en die link je dan aan terfwoord via de hashmap. Kun je altijd bestandsnamen toevoegen als je dat wil. super easy

dus:
paard -> Vector (en daar zitten test1.doc en test3 doc in)
schaap -> Vector (en daar zit dan alleen test1.doc in)

[ Voor 34% gewijzigd door voodooless op 22-06-2004 03:15 ]

[Alarmnummer]

deepspace schreef op 22 juni 2004 @ 03:13:
ipv direct een bestandsnaam om je hashmap te frotten gebruik je een Vector, waar dan je bestandsnamen zet, en die link je dan aan terfwoord via de hashmap. Kun je altijd bestandsnamen toevoegen als je dat wil. super easy

dus:
paard -> Vector (en daar zitten test1.doc en test3 doc in)
schaap -> Vector (en daar zit dan alleen test1.doc in)

Een andere collectie (een list bv) zoals zoijar beschrijft is een goeie oplossing, dit is een stuk geprutst.

Verder is het ook niet waar de topic starter om vraagt.

[voodooless]

Alarmnummer schreef op 22 juni 2004 @ 07:52:
[...]

Een andere collectie (een list bv) zoals zoijar beschrijft is een goeie oplossing, dit is een stuk geprutst.

Verder is het ook niet waar de topic starter om vraagt.

Hoezo is dat nu weer gepruts? Bij nader inzien is mijn oplossing niet veel anders dan die dan zoijar. Hij gebruikt een LinkedList, ik een Vector. Wat is er nu mis met een Vector? Ga nu niet zeggen performance, want ik geloof nooit dat dat bij dit proggie een issue zal zijn (en bovendien: http://www.onjava.com/pub...1/05/30/optimization.html )

En hoezo zou dit niet een oplossing bieden voor het probleem van de TS?

[ Voor 6% gewijzigd door voodooless op 22-06-2004 09:19 ]

[Alarmnummer]

deepspace schreef op 22 juni 2004 @ 09:16:
[...]
Hoezo is dat nu weer gepruts? Bij nader inzien is mijn oplossing niet veel anders dan die dan zoijar. Hij gebruikt een LinkedList, ik een Vector. Wat is er nu mis met een Vector? Ga nu niet zeggen performance, want ik geloof nooit dat dat bij dit proggie een issue zal zijn

Omdat je in een hashmap een constante zoektijd hebt en in een list een zoektijd hebt die afhankelijk is van het aantal elementen in de lijst. Verder is het de bedoeling dat onder 1 key, meerdere bestanden worden opgeslagen en dan kom je dus aan bij een map structuur. Echter een map kan per key maar 1 value hebben, dus daarom zet je op die value een lijst neer, en zet je de 'echte' values in die lijst. Hierdoor is het mogelijk om per key een collectie van values te hebben

[voodooless]

Alarmnummer schreef op 22 juni 2004 @ 09:22:
[...]

Omdat je in een hashmap een constante zoektijd hebt en in een list een zoektijd hebt die afhankelijk is van het aantal elementen in de lijst. Verder is het de bedoeling dat onder 1 key, meerdere bestanden worden opgeslagen en dan kom je dus aan bij een map structuur. Echter een map kan per key maar 1 value hebben, dus daarom zet je op die value een lijst neer, en zet je de 'echte' values in die lijst. Hierdoor is het mogelijk om per key een collectie van values te hebben

Dan heb je denk ik niet helemaal mijn oplossing gesnapt (het was al erg laat en ik heb waarschijnlijk duf zitten typen )...

Je moet die Hashmap ook gewoon houden natuurlijk, maar i.p.v dat je een bestandnaam terug krijgt als value, krijg je nu een Vector terug die alle bestandsnamen voor het beteffende terfwoord (de key dus) bevat. Is toch gewoon precies wat jullie ook bedoelen . Enigste verschil is dat ik meer een Vector fan ben dan een LinkedList fan

[Alarmnummer]

deepspace schreef op 22 juni 2004 @ 09:25:
[...]
Dan heb je denk ik niet helemaal mijn oplossing gesnapt (het was al erg laat en ik heb waarschijnlijk duf zitten typen )...

Ok.. dan zitten we wel op 1 lijn.

Enigste verschil is dat ik meer een Vector fan ben dan een LinkedList fan

Waarom gaan synchronizen als dat niet hoeft? Ik gebruik zelf meestal ArrayLists ipv Vectors. En verder gebruik ik deze specifieke structuur alleen bij het aanmaken:

List l = new ArrayList().

Na afloop hoeft niemand nog te weten dat ik daar een arraylist voor heb gebruikt.

Verder is het ook maar de vraag of de ts de functionaliteit van een List nodig heeft. Misschien is een Set ook al voldoende als de volgorde en het aantal keer dat een element erin staat er niet toe doen.

[ Voor 15% gewijzigd door Alarmnummer op 22-06-2004 09:35 ]

[Robtimus]

Alarmnummer schreef op 22 juni 2004 @ 09:31:
Verder is het ook maar de vraag of de ts de functionaliteit van een List nodig heeft. Misschien is een Set ook al voldoende als de volgorde en het aantal keer dat een element erin staat er niet toe doen.

Als de volgorde (alfabetisch, niet volgorde van invoegen) er wel toe doet kan TS natuurlijk ook voor een SortedSet gaan; zowel Strings als Files implementeren Comparable, dus dat is geen probleem.

[voodooless]

Alarmnummer schreef op 22 juni 2004 @ 09:31:
Ok.. dan zitten we wel op 1 lijn.

gelukkig dan maar

Waarom gaan synchronizen als dat niet hoeft? Ik gebruik zelf meestal ArrayLists ipv Vectors. En verder gebruik ik deze specifieke structuur alleen bij het aanmaken:

List l = new ArrayList().

Ik denk ik dat ik het altijd gewend ben om Vectors te gebruiken (aangezien ik ook nog wel eens wat mulithreaded maak). Ze hebben voor mij altijd prima gewerkt! Maar check die link maar eens uit in mijn eerdere post, is een interessant verhaal

Verder is het ook maar de vraag of de ts de functionaliteit van een List nodig heeft. Misschien is een Set ook al voldoende als de volgorde en het aantal keer dat een element erin staat er niet toe doen.

Tja, dat moet ie zelf uitmaken...

[Cavalera125]

Bedankt. Ik heb nu gebruik gemaakt van een Vector. Het gaat in dit geval puur om de functionaliteit en met een vector werken vind ik wel handig. Ik heb nu dus voor iedere key een vector als value met daarin de bestandsnamen. Nu kan ik dus met map.get(key) die vector ophalen. Nu ga ik nog even zoeken hoe ik die bestandsnamen in die vector kan sorteren op alfabetische volgorde.

[Robtimus]

Cavalera schreef op 22 juni 2004 @ 12:07:
Nu ga ik nog even zoeken hoe ik die bestandsnamen in die vector kan sorteren op alfabetische volgorde.

Als je geen duplicaten nodig hebt, gebruik een SortedSet (TreeSet). Heb je wel duplicaten nodig, Collections.sort(List) of Collections.sort(List, Comparator). Gezien de eerste op de natural ordening sorteert (bij Strings lexicografisch / alfabetisch) moet die voldoen.

[Cavalera125]

IceManX schreef op 22 juni 2004 @ 12:38:
[...]
Als je geen duplicaten nodig hebt, gebruik een SortedSet (TreeSet). Heb je wel duplicaten nodig, Collections.sort(List) of Collections.sort(List, Comparator). Gezien de eerste op de natural ordening sorteert (bij Strings lexicografisch / alfabetisch) moet die voldoen.

Ik had idd al Collections.sort gevonden. Hij werkt nu. Bedankt.

[Verwijderd]

deepspace schreef op 22 juni 2004 @ 09:44:
Ik denk ik dat ik het altijd gewend ben om Vectors te gebruiken (aangezien ik ook nog wel eens wat mulithreaded maak). Ze hebben voor mij altijd prima gewerkt! Maar check die link maar eens uit in mijn eerdere post, is een interessant verhaal

Ik gebruik(te) zelf ook altijd Vector totdat er mij op gewezen werd dat de Vector een overblijfsel is uit java 1.1 (en toendertijd de enige meegroeiende collectie klasse, en dus daarom populair!).

Om backwards compatible te zijn is de Vector behouden gebleven. Maar zou eigenlijk niet meer gebruikt moeten worden. Een goed alternatief (in dit geval) is zoals Alarmnummer zegt de ArrayList.

Just my 50cents