P9: Kettung

baerchen
Computerversteher
Computerversteher
Beiträge: 382
Registriert: 24. Okt 2006 15:42

P9: Kettung

Beitrag von baerchen »

hab ein wenig ein problem mit der implementierung von kettungen wie auf den vl-folien beschrieben, und zwar, dass objekte für h0 und h1 ja nicht umbedingt in der gleichen kollisionsklasse liegen müssen. zb ich füge in eine liste der größe 5 nacheinander folgende werte ein:

e1: k = 2, h0 = 2
Kein Problem da ht[2] frei ist

e2: k = 12, h0 = 2, h1 = 0
auch kein Problem, da ht[0] frei,
zusätzlich füge ich jetzt bei kettung[2] einen verweis auf e2 bzw einfach die 0 ein

e3: k = 7, h0 = 2, h1 = 4
ht[4] ist zwar frei, ich kann aber bei kettung[2] nix mehr einfügen, wenn ich jetzt e1 und e2 lösche, dann hängt mein drittes element gewissermaßen "in der luft", dh ich finde es nicht mehr wieder

ich denke mal das hat was mit diesem verdrängen zu tun aber das hab ich noch ned ganz verstanden.
We can do this the hard way or my way ...which is basically the same thing!

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Beitrag von Christoph B »

hm, da gibts denk ich 2 möglichkeiten:
1. du setzt den Verweis von ht[2] auf ht[0] so um, das ht[2] auf ht[4] verweist, und ht[4] auf ht[0] (sozusagen dazwischen drängeln, die idee is mir jetz grad erst gekommen - von daher vllt falsch ^^) oder du setzt deinen verweis auf ht[4] bei ht[2]

Verdrängt wird nur wenn du z.B. bei h0 ne adresse rauskriegst die von einem Element blockiert wird, das durch Kollision da gelandet ist (also nen andren h0 wert hat als die adresse auf der es liegt)

baerchen
Computerversteher
Computerversteher
Beiträge: 382
Registriert: 24. Okt 2006 15:42

Beitrag von baerchen »

anscheinend is kettung bei vertretbaren aufwand mit doppeltem hashen nicht möglich, habs jetzt mit gelöscht-markierung implementiert. wer will kann das gegenteil behaupten, muss mir dann aber auch meine frage beantworten ^^
We can do this the hard way or my way ...which is basically the same thing!

nieswand
Mausschubser
Mausschubser
Beiträge: 60
Registriert: 28. Apr 2007 15:13

Beitrag von nieswand »

Also, erstmal: Wenn's bei dir mit Markieren jetzt klappt ist ja super.

Ich meine, dass es mit Kettung aber eigentlich schon klappen müsste.

Wenn du für dein Array kettung[] eine Liste von Listen nimmst. Also z. B.:

ArrayList<ArrayList<Integer>> Kettung;

Dann kannst du bei der Kettung an der Stelle 2, zwei Zahlen als Verweise einfügen. Also in deinem Fall einmal die 0 und einmal die 4.

Beim Suchen eines Objekts läufst du halt die Liste durch und kannst auch ohne Probleme ein Objekt löschen. Wenn du z.B. das zweite Objekt löschst, findest du das dritte immer noch durch die 4 in der Liste. Wenn du das erste Element löschst, das wirklich an der Stelle 2 steht, nimmst du ein beliebiges Element aus der Verweisliste und fügst es stattdessen an der Stelle ein.

Könnte das so gehen oder übersehe ich da was?

yourmaninamsterdam
Nerd
Nerd
Beiträge: 681
Registriert: 26. Okt 2006 14:04
Kontaktdaten:

Beitrag von yourmaninamsterdam »

Dann würde ich aber gleiche in der Hashtable keinen Array von IHashObjects sondern einen von ArrayList<IHashObject>s verwenden und mir das sondieren sparen.

Ich nehme daher stark an, dass es so nicht gemacht werden soll.

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Beitrag von Christoph B »

hm, wie wärs einfach mit nem int array der genauso groß is wie die HashTable
wenn du an der Adresse 5 ne Kollision hast und deshalb nen ELement bei 7 einfügen musst, setzte bei dem kettungs array die 5 stelle = 7;
wenn danach noch ein Element in der gleichen Kollisions klasse is un du das auf position 9 haust setzte bei der kettung an stelle 7 halt ne 9.
damit haste jetz eine Kollisionkette 5 -> 7 -> 9 an der du entlang gehn kannst um ein Element mit dem entsprechenden HashWert zu finden
Wenn du ein element löschen willst, kannstes einfach so wie im skript machen:
du gehst in die ganze Kollisionskette entlang bis zum letzten Eintrag, den vertauschste dann mit dem zu löschenden Objekt und passt die verweise an.
Das is denk ich schon ziemlich effizient ^^

Benutzeravatar
Martin K
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 110
Registriert: 13. Okt 2006 17:56

Beitrag von Martin K »

Ich glaube nicht, dass das so funktioniert, oder habe ich deinen Vorschlag falsch verstanden?
Also angenommen du hast diese Kollisionskette:
5 -> 7 -> 9

Jetzt fügst du ein neues Element hinzu, was auf die Stelle 9 käme.
Da diese besetzt ist, schreibst du das Element z.B. an Stelle 13.
Würdest du jetzt auch bei 9 einen Verweis auf 13 in den Array schreiben?
Angenommen du löschst die 5, dann würdest du die 13 doch in die 5 schreiben, obwohl sie eigentlich in die 9 gehört!
Sehe ich das richtig?
Gäbe es die letzte Minute nicht,
so würde niemals etwas fertig.

- Mark Twain

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Beitrag von Christoph B »

ne, da kommt jetz die verdrängung ins spiel:
da die Position 9 von einem Element besetzt ist, das durch Kollision da gelandet ist, wird dieses Element einfach wechgehaun (geht auch recht einfach eben dank den verweisen) un das Element mit h0 Hash Funktion = 9 wird bei der 9 reingehauen.

edit:
nochmal anschlaulicher:

Kollisionskette
5 -> 7 -> 9

wir fügen ein Element ein, das h0 = 9 als Hash Wert hat.

d.h. wir suchen für das bisherige Element an Stelle 9 einen neuen Platz zum schlafen, z.B. landen wir bei 11, kollisionskette wird dann geändert:
5 -> 7 -> 11

an Stelle 9 haun wir dann unser h0 = 9 Element rein und alle sind zufrieden.
Zuletzt geändert von Christoph B am 5. Jul 2007 20:28, insgesamt 1-mal geändert.

MaxPayne
Neuling
Neuling
Beiträge: 6
Registriert: 28. Jun 2007 13:10

Beitrag von MaxPayne »

War da nicht noch was mit Verdrängung, falls eine Hausnummer von einem Objekt belegt ist, was nur durch Kollision dorthin gekommen ist und ein Objekt auf diese Hausnummer gelegt werden will, welches vom Initial-Hashwert wirklich dorthin gehört?
Dann müsste man doch lediglich das zu verdrängende Objekt in der Kollision eins nach hinten schieben und den Kollisions-Verweis im vorhergehenden Objekt anpassen - oder sehe ich das falsch?

Alles etwas tricky ... ;)

Edit: Shit, einen Moment zu spät ... :P

Benutzeravatar
Martin K
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 110
Registriert: 13. Okt 2006 17:56

Beitrag von Martin K »

Nun gut, aber in der Aufgabenstellung steht nix von Verdrängung oder hab ich da was überlesen?

Ach ja, dann müsste man bei diesem Ansatz aber noch die Vorgänger in der Kollisionskette speichern, also bei der 9 muss die 7 als Vorgänger gespeichert werden, richtig?
Also nen zweidimensionales Array:
für jedes Element einen Vorgänger und einen Nachfolger in der Kette...
Gäbe es die letzte Minute nicht,
so würde niemals etwas fertig.

- Mark Twain

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Beitrag von Christoph B »

nö, vorgänger brauchste nich, eindimensionaler array reicht, eben genauso wie im Skript / vorlesung besprochen.
und in der Aufgabenstellung steht auch nichts von als gelöschen Markieren etc

das sind einfach verschiedene Ansätze wie man seine HashTable aufbaut, du musst dich selbst entscheiden welche zu wählst.

Alexis1987
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 29. Apr 2007 16:58

Beitrag von Alexis1987 »

Hy,

wollte nur mal schnell was anmerken zu folgendem:
yourmaninamsterdam hat geschrieben:Dann würde ich aber gleiche in der Hashtable keinen Array von IHashObjects sondern einen von ArrayList<IHashObject>s verwenden
Also um ehrlich zu sein würde ich gar nicht mit dem Interface arbeiten.
Man nehme an das T, das das Interface implementiert, auch noch andere "Dinge" außer nur getKey() kann.
Wenn man mit ArrayList<IHashObject> oder IHashObject[] arbeitet und ein Objekt vom Typ T in die Liste bzw das Array gespeichert wird, verliert es die zusätzlichen Funktionen, die T hat aber IHashObject nicht.

Beispiel:

IHashObject bietet nur getKey()

HashObject implementiert IHashObject und kann daher getKey. Zusätzlich kann es aber auch getValue();

HashObject ho = new HashObject();
IHashObject[] aoho = new IHashObject[10];
aoho[0] = ho;
ho.getValue(); <= GEHT!
aoho[0].getValue; <= GEHT NICHT!

Ich hoffe es wurde klar was ich meine.

Gruss Alexis
Der Tofu-Burger schmeckt ausgezeichnet, wenn man ihn Kurz vor dem Verzehr durch ein saftiges T-Bone-Steak austauscht.

yourmaninamsterdam
Nerd
Nerd
Beiträge: 681
Registriert: 26. Okt 2006 14:04
Kontaktdaten:

Beitrag von yourmaninamsterdam »

Es ist klar, was gemeint ist, obwohl es nicht der Kern meiner Aussage war. Du kannst den Typ da ändern zu was du willst.

Ich würde übrigens unabhängig davon trotzdem mit dem Interface arbeiten. Das ist designtechnisch deutlich geschickter (ganz unabhängig davon, dass man keinen T[]-array instanziieren kann). Wieso solltest du in deiner Hashtable jemals irgendwas anderes als die Funktionalität aus dem IHashObject Interface benutzen?
Im Rahmen der Abstraktion sollte man immer auf Interfaces arbeiten und nicht auf konkreten Implementierungen.
Und ja, bei Projekten vom Ausmaß dieses Praktikums ist es egal.

Alexis1987
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 29. Apr 2007 16:58

Beitrag von Alexis1987 »

Hy,

das war ja nicht direkt an dich gerichtet sondern eher an alle die das sehen und denken es dann genau so machen zu müssen.
yourmaninamsterdam hat geschrieben:Wieso solltest du in deiner Hashtable jemals irgendwas anderes als die Funktionalität aus dem IHashObject Interface benutzen?
Innerhalb der Hashtabelle brauchst und solltest du bestimmt keine Funktionen benutzten von denen du nicht sicher bist ob sie existieren, allerdings würde ich als Benutzter dieser Hashtabelle gerne ein Objekt aus der Tabelle bekommen das die gleichen Funktionen bietet wie das Objekt das ich rein gesteckt habe.

Und wenn jetzt Einer fragt wieso überhaupt eine Implementierung eines Interfaces mehr können soll als das Interface anbietet, frage ich ihn wieso den nicht.

Konkret, denke ich das eine getValue() funktion innerhalb eines HashObjekt Sinn macht (Man will die Objekte ja nicht nur an Hand der Referenz unterscheiden). Sie wird zwar nicht innerhalb der HashTabelle gebraucht aber ich hätte sie trotzdem gerne immernoch wenn ich das Objekt aus der Tabelle hole.

Gruß Alexis
Der Tofu-Burger schmeckt ausgezeichnet, wenn man ihn Kurz vor dem Verzehr durch ein saftiges T-Bone-Steak austauscht.

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Beitrag von Christoph B »

dank dem Interface system verlierst du keine Funktionalität ;)

bei getElement musste eh ein Object der Klasse T zurück liefern, d.h. man muss IHashObject auf T casten, dabei bleibt die Funktionalität deiner T Klasse völlig erhalten (du hast ya auch ne T Klasse reingesteckt)

also z.B. hashmap.getElement(x).getValue funktioniert problemlos un gibt das zurück, wasses zurück geben soll

und wenns nötig ist kannste das natürlich auch intern in deiner HashTable machen.

Antworten

Zurück zu „Archiv“