Elemente einer HashTabelle gezielt ansprechen

[ZGoten]

Hallo,
ich bin Student der Informatik im ersten Semester und neu hier im Forum.

Ich habe ein Verständnisprblem das Hashing betrifft, konnte aber mittels Suchfunktion und Lesen der FAQs keine Antwort darauf finden.

Folgendes Problem:

Beim Hashing kann es zu Kollsionen kommen, wenn verschiedene Schlüssel an der selben Stelle gespeichert werden (dem selben Bucket). Um solche Kollisionen zu vermeiden gibt es die Methode des Sondierens. Das habe ich in der Theorie soweit verstanden.
Beim Umsetzen in die Praxis tritt das Problem auf.

Hashtable h = new Hashtable (10);

Mit dieser Hashtable arbeite ich. In einer Aufgabe wird verlangt, eine Sondiermethode zu programmieren, um Kollisionen zu vermeiden.
Jedoch frage ich mich, wie es mit solch einer Hashtable in Java überhaupt zu einer Kollision kommen kann, da jeder Schlüssel automatisch an einer neuen Stelle gespeichert wird.
Gibt es einen Weg, die einzelnen "Buckets" der Hashtable anzusprechen?

 

[SlaterB]

auf die interne Implementierung einer Klasse kannst du selbstverständlich so gut wie gar nicht zugreifen,
weder bei Hashtable, noch bei ArrayList, String, JButton, oder sonst einer Klasse,

dein Vorhaben scheint nicht sinnvoll, ist es nicht vielleicht eher deine Aufgabe, eine komplett eigene ähnliche Klasse zu schreiben?

 

[ThreadPool]

Jedoch frage ich mich, wie es mit solch einer Hashtable in Java überhaupt zu einer Kollision kommen kann, da jeder Schlüssel automatisch an einer neuen Stelle gespeichert wird.

Wenn du deine Hashtabelle nur mit einer Größe von 10 Initialisierst und 100 Werte reinpackst wird es garantiert zu Kollisionen kommen. Wann Java die Hashtabelle von selbst vergrößert kannst du etwas über den "loadfactor" steuern, dafür gibts einen extra Konstruktor.

 

[ZGoten]

Hmm, eine neue Klasse zu schreiben, die HashTable ähnelt scheint mir doch etwas viel zu sein für die mickrigen 60 Punkte.
Allerdings würde das Sinn ergeben, weil ich dann erst die Sondierungsfunktion einbauen kann (die ja mit der vordefinierten Klasse HashTable bereits ausgeführt wird).

Vielleicht hilft es, wenn ich die Aufgabenstellung einmal zitiere:

In dem ADT HashTable sollen String-Objekte verwaltet werden. In der Hashtable selbst werden Paare (key, String) gespeichert. Der key (vom Typ int) wird aus dem zu speichernden String-Objekt berechnet. Für die Berechnung eines Schlüssels aus einem String gibt es eine Vielzahl von Verfahren. Man muss auch nicht den gesamten String zur Berechnung heranziehen. FÜr die Berechnung von Key nehmen Sie die Summe des ASCII-Werts des ersten und des letzten Buchstabens.

Implementieren Sie für den ADT HashTable folgende Operationen:

put Hashtable x key x String -> String
get Hashtable x key -> String
[...]usw.

Bislang dachte ich, die Aufgabe wäre eine Art Benutzerumgebung zu kreieren, die mit Hashtable als vordefinierter Klasse arbeitet und mit der der Benutzer die Table beliebig verändern kann.

 

[ThreadPool]

Vielleicht hilft es, wenn ich die Aufgabenstellung einmal zitiere:

Sieht nach selber schreiben aus die Aufgabe, zumal der built-in Java Typ "Hashtable" geschrieben wird und du eine "HashTable" implementieren sollst. Eine total unspektakuläre Hashtabelle (und ich sehe da nix spektakuläres in der Aufgabe) braucht nicht viel an Code.

 

[ZGoten]

Sieht nach selber schreiben aus die Aufgabe, zumal der built-in Java Typ "Hashtable" geschrieben wird und du eine "HashTable" implementieren sollst. Eine total unspektakuläre Hashtabelle (und ich sehe da nix spektakuläres in der Aufgabe) braucht nicht viel an Code.

Ich habs befürchtet. Naja ok, vielen Dank.
Zum Abschluss vielleicht noch ein kleiner Tipp:

Am besten gehe ich so vor, dass ich ein Interface mit allen gewünschten Operationen (Methoden) erstelle, eine Klasse, in denen diese Methoden geschrieben werden, und zuletzt die eigentliche Hashtable-Klasse, die das Interface implementiert und die Eigentliche Tabelle mit 2 Arrays darstellt - eins das die Key-Value Paare speichert und eins, das den jeweiligen Index zu einem Key speichert, oder?

 

[Sekundentakt]

Ich lese aus der Aufgabenstellung heraus, dass Du einfach die Ascii-Darstellung des ersten und letzten Zeichens deines Strings nehmen sollst.

Der String lautet
"Sekundentakt".

groß S -> Ascii -> 83
klein t -> Ascii -> 116

Das Hashverfahren von Dir soll Ascii(S) + Ascii(t) lauten:
83 + 116 = 199

Dein Hashwert (bzw. Key) für den String "Sekundentakt" lautet 199.

Der erste Eintrag deiner Hashtable könnte also

199, Sekundentakt

lauten.

EDIT:
Warum zwei Arrays?
Wenn Du ein zweidimensionales hast, reicht das doch, oder?
Ich würde daher - falls erlaubt - auf ArrayMap zurückgreifen.
Ansonsten wie Du schon sagtest: Key-Array mit [HASH][Index] und ein Value-Array mit [Index][Value].

 

[ZGoten]

Ich lese aus der Aufgabenstellung heraus, dass Du einfach die Ascii-Darstellung des ersten und letzten Zeichens deines Strings nehmen sollst.

Der String lautet
"Sekundentakt".

groß S -> Ascii -> 83
klein t -> Ascii -> 116

Das Hashverfahren von Dir soll Ascii(S) + Ascii(t) lauten:
83 + 116 = 199

Dein Hashwert (bzw. Key) für den String "Sekundentakt" lautet 199.

Der erste Eintrag deiner Hashtable könnte also

199, Sekundentakt

lauten.

So weit war ich schon. Aber mit der Aufgabenstellung geht es noch weiter. Den jeweiligen Key zu einem String zu berechnen ist nur ein kleiner Teil der Aufgabe. Mir ging es darum, ob ich eine eigene Hashtable-ähnliche Klasse schreiben, oder mit der bereits vordefinierten arbeiten soll.

 

[Sekundentakt]

Im obigen Beitrag stehen noch ein paar Anmerkungen zu deiner Idee.

Deine Aufgabenstellung sagt eindeutig: selber machen!

 

[ZGoten]

Ok, dann schreib ich eine neue Klasse, danke Leute.

/edit:
Hat alles geklappt, musste nicht mal zwei Arrays benutzen um die Keys extra zu speichern, da die sich jederzeit ausreichnen lassen.

 

[Sekundentakt]

Ok, dann schreib ich eine neue Klasse, danke Leute.

/edit:
Hat alles geklappt, musste nicht mal zwei Arrays benutzen um die Keys extra zu speichern, da die sich jederzeit ausreichnen lassen.

Könntest Du das Ganze mal posten?
Mich würde interessieren, wie Du dieses String-Array dynamisch gefüllt hast bzw. wie Du das mit dem Key gemeint hast.

m.E. nach würde das mit vielem (z.B. int-Array), nur nicht mit einem String-Array laufen. Daher die Neugier.