|
|
|
|
Hab ein Problem die Angabe richtig zu deuten ..
-> Angabe
Zur Realisierung ist Hashing mit Kollisionsverwaltung durch Listen zu verwenden.
Gibts für das eingebaute Klassen die ich verwenden kann?
Wäre es sinnvoll hastable zu verwenden? andere?
mfg
|
|
|
|
|
|
|
Aufgabenstellung nur überfolgen, aber du sollst dir ne Hashtable bauen. Also prinzipiell willst du Strings in ein Array hashen (mit der gegebenen hash-Funktion). Dabei kann es allerdings zu Kollisionen kommen, wodurch du in jedem Array Index eine Liste bereit hältst, in welche neue Werte beim hashen eingefügt werden.
|
|
|
|
|
|
|
| Zitat von b4ckspin
Hab ein Problem die Angabe richtig zu deuten ..
-> Angabe
Zur Realisierung ist Hashing mit Kollisionsverwaltung durch Listen zu verwenden.
Gibts für das eingebaute Klassen die ich verwenden kann?
Wäre es sinnvoll hastable zu verwenden? andere?
mfg
| |
Ich glaub der Sinn der Sache ist, dass du das selber programmieren sollst?!
/edit: Also ich weiß nicht ob ihr evtl. Klassen aus der Javabibliothek verwenden dürft! Wir durften das im Studium meistens nicht (zumindest nicht in AlgoDat). Außerdem ist die Java Liste ne doppelt verkettete und in der Aufgabenstellung steht man soll eine einfach verkettete verwenden?!
Nur zum Effizienztest sollst du dann die hashtable benutzen?! So les ich das zumindest raus?
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von ChrisR am 14.05.2013 20:32]
|
|
|
|
|
|
also sowas bauen : einfache Liste und dann noch die hashCode dazu oder..
|
|
|
|
|
|
|
Nicht nötig, ich bin mir ziemlich sicher, dass du für die Listen vorhandene Klassen (LinkedList, whatever) nutzen darfst. Bei der Aufgabe geht es um die Hashs.
|
|
|
|
|
|
|
okay dann versuch ich das mal so
|
|
|
|
|
|
|
Vielleicht noch der Hinweis, dass Java ja Hashable Objects eingebaut hat. Jedes Objekt muss hashCode() implementieren.
|
|
|
|
|
|
|
Um eine gescheite Hashfunktion für Integer zu bauen, empfehle ich dir einen Block hierauf. Nicht von dem vielen gedöns abschrecken lassen, im wesentlich brauchst du bloß:
- p ist eine Primzahl größer |U| (Mächtigkeit deines zu hashenden Universums). Eine solche kannst du dir mit BigInteger erzeugen
- m ist die Anzahl der Hashbuckets
- a und b zwei zufällige Zahlen modulo p
Und wenn du voll Porno seien willst, implementierst du noch Kuckukshashing for the lulz!
|
|
|
|
|
|
|
Er soll aber keine Hashfunktion implementieren
|
|
|
|
|
|
|
Oh...jetzt sehr ich es auch. Das ist ja voll langweilig
|
|
|
|
|
|
|
habs glaub ich fast fertig. die Frage ist jetzt brauch ich ne verdoppel Methode für das Listen Array oder nicht..
Stehen würde ja nix .. :/
myProg
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von b4ckspin am 14.05.2013 22:59]
|
|
|
|
|
|
Was mir so beim Überfliegen aufgefallen ist:
|
Code: |
public boolean isEmpty (){
if(hashCount == 0){
return true;
}
return false;
} |
|
-->
|
Code: |
public boolean isEmpty (){
return hashCount == 0;
} |
|
|
Code: |
beide Strings muessen nicht leer sein! |
|
Ernsthaft?
|
Code: |
public void getList(String matNr){
System.out.println(theLists[myhash(matNr)]);
} |
|
Nenn sowas printList. Ein Getter sollte immer etwas zurückgeben (ergo niemals void sein).
|
Code: |
if(matNr == "" || name == "") |
|
Abgesehen davon, dass man in einem solchen Fall "".equals(String) machen sollte: Wenn du sowas machst, dann kann es immer noch sein, dass matNr oder name null sein können. Das würde die Abfrage durchwinken.
/: Und wenn ich mir das genauer angucke: Das funktioniert vll. aber das geht mal komplett am Prinzip einer Hashtable vorbei, bzw. hast du da etwas komplett falsch verstanden hast. :P
|
[Dieser Beitrag wurde 2 mal editiert; zum letzten Mal von cms am 14.05.2013 23:17]
|
|
|
|
|
|
| Zitat von cms
|
Code: |
beide Strings muessen nicht leer sein! |
|
Ernsthaft?
| |
Mit der Formulierung sind leere Strings erlaubt und die Funktion somit gerechtfertigt.
|
|
|
|
|
|
|
Ich krieg langsam die Krise mit Visual Studio . Jemand ne Ahnung, warum beim Debug-Modus Dateien im Eingabeparameter nicht gefunden werden, selbst wenn man diese via absolutem Pfad angibt? Im Release Mode klappt alles reibungslos, aber sobald ich auf Debug umstelle geht es nicht. Aber im Release Mode kann ich nicht angemessen debuggen .
Netbeans Installation läuft schon, aber vielleicht gibt's ja doch noch ne Lösung. Es schwärmen doch immer alle so von Visual Studio...
|
|
|
|
|
|
|
okay inwiefern komplett vorbei?
|
|
|
|
|
|
|
Also eine Hashtabelle (oder Hashmap) speichert ist so gedacht, dass mehrere Boxen/Eimer/wasauchimmer (in deinem Falle als Listen dargestellt) hat. Wenn man nun ein Element in die Hashtabelle einfügt, dann entscheidet der Hashwert, in welche Box dieses Element eingefügt wird. Es können, bedingt durch die Hashfunktion, auch mehrere unterschiedliche Elemente in derselben Box liegen. Um ein Element auszulesen muss man in die dem Hashwert entsprechende Box gehen und durch diese durchiterieren, bis man das Element hat.
Ein Bsp.:
Du willst nur Matrikelnummern speichern. Einfachheitshalber sagen wir, dass du 10 Boxen hast. Außerdem ist die Hashfunktion MatNr % 10 . Dann fügst du die Mat.-Nummern 123450, 123460 und 123455 ein. Die ersten beiden liegen nun in derselben Box (die, die mit MatNr % 10 == 0 adressiert wird).
|
|
|
|
|
|
|
| Zitat von cms
|
Code: |
if(matNr == "" || name == "") |
|
Abgesehen davon, dass man in einem solchen Fall "".equals(String) machen sollte: Wenn du sowas machst, dann kann es immer noch sein, dass matNr oder name null sein können. Das würde die Abfrage durchwinken.
| |
Geht 's dir um die Reihenfolge oder um das equals? Falls letzteres, warum? Wäre das nicht eigentlich eine Form von Yoda-Conditions?
Abgesehen davon, prüfe ich immer, ob der String eine Länge größer Null hat. Weiß nicht, ob das besser ist - ich mache es einfach so. Habe zudem gehört, dass man, wenn man schon auf "" prüfen will, doch lieber String.Empty nehmen sollte - allerdings bin ich auch im .Net - weiß nicht, ob Java, außerhalb .Net, ein Äquivalent dazu anbietet.
¤\Ach, equals prüft mit auf null ab.
Hyp
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von Hyperdeath am 14.05.2013 23:49]
|
|
|
|
|
|
| Zitat von Hyperdeath
| Zitat von cms
|
Code: |
if(matNr == "" || name == "") |
|
Abgesehen davon, dass man in einem solchen Fall "".equals(String) machen sollte: Wenn du sowas machst, dann kann es immer noch sein, dass matNr oder name null sein können. Das würde die Abfrage durchwinken.
| | Geht 's dir um die Reihenfolge oder um das equals? Falls letzteres, warum? Wäre das nicht eigentlich eine Form von Yoda-Conditions?
Abgesehen davon, prüfe ich immer, ob der String eine Länge größer Null hat. Weiß nicht, ob das besser ist - ich mache es einfach so. Habe zudem gehört, dass man, wenn man schon auf "" prüfen will, doch lieber String.Empty nehmen sollte - allerdings bin ich auch im .Net - weiß nicht, ob Java, außerhalb .Net, ein Äquivalent dazu anbietet.
Hyp
| | Beides. Das hat mehrere Gründe:
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von cms am 14.05.2013 23:51]
|
|
|
|
|
|
| Zitat von cms
Java hat eine interne Liste über Strings. Sprich "" zeigt immer auf dasselbe Objekt. Bei anderen Strings ist das ebenfalls so. Deswegen funktioniert ein Vergleich mit == auch meistens. Meistens deswegen, weil "test" == new String("test") false ergibt. Mit new wird hier wirklich ein neues Objekt erzeugt.
| |
Wieder was gelernt.
Hyp
|
|
|
|
|
|
|
| Zitat von Hyperdeath
Abgesehen davon, prüfe ich immer, ob der String eine Länge größer Null hat. | |
Wenn die Auswertung nicht lazy ist verwendest du hier einen Linearzeitalgorithmus für etwas, was in konstanter Zeit implementiert werden kann.
e/ Wenn ich so drüber nachdenke weiß ich garnicht ob Lazyness groß helfen würde.
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von B0rG* am 15.05.2013 0:00]
|
|
|
|
|
|
== prüft in Java auf Identität, das klappt mit primitiven Typen noch ganz gut, aber bei Objekten sollte man .equals nehmen, das auf Gleichheit prüft. Bei C# habt ihr glaube ich == und === dafür.
|
|
|
|
|
|
|
| Zitat von B0rG*
| Zitat von Hyperdeath
Abgesehen davon, prüfe ich immer, ob der String eine Länge größer Null hat. | |
Wenn die Auswertung nicht lazy ist verwendest du hier einen Linearzeitalgorithmus für etwas, was in konstanter Zeit implementiert werden kann.
e/ Wenn ich so drüber nachdenke weiß ich garnicht ob Lazyness groß helfen würde.
| |
Mir war so, als hätte ich da mal was gelesen. War das http://msdn.microsoft.com/en-us/library/ms182279%28v=vs.100%29.aspx Hat natürlich bezüglich Java nichts zu heißen.
IsNullOrEmpty hatte ich schon wieder vergessen, weil ich 's selten brauche.
Hyp
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von Hyperdeath am 15.05.2013 0:07]
|
|
|
|
|
|
Ah, wenn die Strings ihre Länge kennen dann ist das natürlich trotzdem O(1) und ich will nichts gesagt haben.
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von B0rG* am 15.05.2013 0:18]
|
|
|
|
|
|
hab grad rumgetestet und bemerkt das schon mehrere Werte in eine "Box" kommen.. :?
|
|
|
|
|
|
|
| Zitat von Redh3ad
== prüft in Java auf Identität, das klappt mit primitiven Typen noch ganz gut, aber bei Objekten sollte man .equals nehmen, das auf Gleichheit prüft. Bei C# habt ihr glaube ich == und === dafür.
| |
jau, das hatten wir letztens afair schonmal. Könnte auch im LT gewesen sein.
Bei Integer, Double etc. hängt das Ergebnis "==" dann vom Werterebereich in dem man sich bewegt ab und so Späße :-)
|
|
|
|
|
|
|
| Zitat von cms
Also eine Hashtabelle (oder Hashmap) speichert ist so gedacht, dass mehrere Boxen/Eimer/wasauchimmer (in deinem Falle als Listen dargestellt) hat. Wenn man nun ein Element in die Hashtabelle einfügt, dann entscheidet der Hashwert, in welche Box dieses Element eingefügt wird. Es können, bedingt durch die Hashfunktion, auch mehrere unterschiedliche Elemente in derselben Box liegen. Um ein Element auszulesen muss man in die dem Hashwert entsprechende Box gehen und durch diese durchiterieren, bis man das Element hat.
| |
Genau. Du brauchst noch eine Wrapperklasse wie z.B.:
|
Code: |
class Entry<K,V> {
public final K key;
public final V value;
public Entry(K key, V, value) {
this.key = key;
this.value = value;
}
} |
|
Deine giveName Funktion sieht dann so aus:
|
Code: |
public String giveName (String matNr) {
// use hash to get the correct bucket
List<Entry<String, String>> whichList = theLists[myhash(matNr)];
// see if this bucket has a entry with the given key and return if found
for(Entry<String, String> entry : whichList) {
if(matNr.equals(entry.key)) {
return entry.value;
}
}
// fall throught if nothing is found
return null;
} |
|
Insert und delete müssten dir damit klarer werden, oder? Dieser Punkt macht auch klar, warum HashMaps (wenn sie auf Listen basieren) nur gescheit schnell sind, wenn sie nicht zu voll sind (wenn also der load factor gering ist). Wenn fast alle Buckets voll sind (= die Liste an dieser Stelle hat mindestens ein Element), dann muss beim holen der Inhalte zum einen Key eine Liste durchsucht werden. Da benötigt Linearzeit und ist damit unschön ist. Hält man den Loadfactor gering hält kommt man (aromtisiert) auf konstante Zugriffszeit.
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von Achsel-des-Bösen am 15.05.2013 0:36]
|
|
|
|
|
|
Die Matrikelnummer besteht aus 7 Ziffern (wobei die ersten beiden das Jahr der Erstanmeldung angeben) und wird als Schlüssel verwendet.
also dann this.key = Matrikelnummer ?
|
|
|
|
|
|
|
| Zitat von b4ckspin
hab grad rumgetestet und bemerkt das schon mehrere Werte in eine "Box" kommen.. :?
| | Stimmt, hab mir die insert-Methode noch mal angeguckt. Aber guck dir noch mal deine delete-Methode an. Das kann so nicht passen.
Außerdem: Das ist gaaaaanz schlechter Stil, die Einträge derart in die Liste einzufügen. Und du sollst sogar eine eigene (innere) Klasse schreiben, mit der die Datensätze gespeichert werden.
/: Multitasking macht langsam. Ich brauch mehrere Prozessoren in meinem Kopf. Und wo ich dabei bin: Eine GPU fürs Matheverständnis wäre geil!
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von cms am 15.05.2013 0:38]
|
|
|
|
|
|
| Zitat von b4ckspin
Die Matrikelnummer besteht aus 7 Ziffern (wobei die ersten beiden das Jahr der Erstanmeldung angeben) und wird als Schlüssel verwendet.
also dann this.key = Matrikelnummer ?
| |
Genau. Und der Hashwert des Schlüssels bestimmt in welches Bucket (welche Liste) der Eintrag einsortiert wird.
|
|
|
|
|
|
|
ja stimmt die delete ist nicht so nice
hab ich gelesen aber keinen Plan gehabt wie ich das mache deshalb bin ich auf diese Lösung gekommen.
Hast nen Tipp wie das mit der inneren Klasse geht?
Mir fehlt da irgendwie der Zusammenhang
|
|
|
|
|
|
Thema: pOT-lnformatik, Mathematik, Physik XIII ( Completely Automated Public User Test To tell PIMP ) |