Du bist nicht eingeloggt! Möglicherweise kannst du deswegen nicht alles sehen.
  (Noch kein mods.de-Account? / Passwort vergessen?)
Zur Übersichtsseite
Hallo anonymer User.
Bitte logge dich ein
oder registriere dich!
 Moderiert von: Irdorath, statixx, Teh Wizard of Aiz


 Thema: pOT-lnformatik, Mathematik, Physik XIII ( Completely Automated Public User Test To tell PIMP )
« vorherige 1 2 3 4 5 6 7 8 9 10 11 12 [13] 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 nächste »
erste ungelesene Seite | letzter Beitrag 
b4ckspin

tf2_medic.png
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
14.05.2013 20:16:42  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
Renga

renga
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.
14.05.2013 20:28:57  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
ChrisR

Leet
 
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]
14.05.2013 20:29:16  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
b4ckspin

tf2_medic.png
also sowas bauen : einfache Liste und dann noch die hashCode dazu oder..
14.05.2013 20:48:33  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
Redh3ad

AUP Redh3ad 11.10.2009
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.
14.05.2013 20:52:43  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
b4ckspin

tf2_medic.png
okay dann versuch ich das mal so
14.05.2013 20:54:52  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
csde_rats

AUP csde_rats 04.09.2021
Vielleicht noch der Hinweis, dass Java ja Hashable Objects eingebaut hat. Jedes Objekt muss hashCode() implementieren.
14.05.2013 21:09:02  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
Achsel-des-Bösen

AUP Achsel-des-Bösen 06.10.2009
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ß:

TeX:  h_{a,b}(x) = ((ax + b)~\bmod ~ p)~\bmod ~ m

- 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!
14.05.2013 21:34:46  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
Redh3ad

AUP Redh3ad 11.10.2009
Er soll aber keine Hashfunktion implementieren
14.05.2013 21:36:58  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
Achsel-des-Bösen

AUP Achsel-des-Bösen 06.10.2009
Oh...jetzt sehr ich es auch. Das ist ja voll langweilig traurig
14.05.2013 21:38:59  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
b4ckspin

tf2_medic.png
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]
14.05.2013 22:49:04  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
cms

AUP cms 14.11.2012
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? Breites Grinsen

 
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]
14.05.2013 23:12:37  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
Rufus

AUP Rufus 12.02.2008
 
Zitat von cms

 
Code:
beide Strings muessen nicht leer sein!

Ernsthaft? Breites Grinsen


Mit der Formulierung sind leere Strings erlaubt und die Funktion somit gerechtfertigt.
14.05.2013 23:16:59  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
Cru$her

AUP Cru$her 23.11.2009
Ich krieg langsam die Krise mit Visual Studio traurig. 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...
14.05.2013 23:26:13  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
b4ckspin

tf2_medic.png
fröhlich okay inwiefern komplett vorbei?
14.05.2013 23:27:12  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
cms

AUP cms 14.11.2012
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).
14.05.2013 23:38:42  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
Hyperdeath

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.

¤\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]
14.05.2013 23:43:16  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
cms

AUP cms 14.11.2012
 
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:

  • "".equals(String)
    kann unmöglich eine NullPointerException werfen, da "" immer ein String-Objekt ist.
  • Damit ist auch der Fall abgedeckt, dass matNr oder Name null sein können.
  • Das Äquivalent zu String.Empty ist "". Augenzwinkern
  • 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.
  • Die Länge zu prüfen ist unnötig, da equals das macht.
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von cms am 14.05.2013 23:51]
14.05.2013 23:50:23  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
Hyperdeath

hyperdeath
 
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
14.05.2013 23:57:57  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
B0rG*

Gordon
 
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]
14.05.2013 23:58:10  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
Redh3ad

AUP Redh3ad 11.10.2009
 
Zitat von Hyperdeath



== 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.
14.05.2013 23:58:33  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
Hyperdeath

hyperdeath
 
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]
15.05.2013 0:06:42  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
B0rG*

Gordon
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]
15.05.2013 0:17:25  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
b4ckspin

tf2_medic.png
hab grad rumgetestet und bemerkt das schon mehrere Werte in eine "Box" kommen.. :?
15.05.2013 0:22:42  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
csde_rats

AUP csde_rats 04.09.2021
 
Zitat von Redh3ad

 
Zitat von Hyperdeath



== 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 :-)
15.05.2013 0:28:28  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
Achsel-des-Bösen

AUP Achsel-des-Bösen 06.10.2009
 
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]
15.05.2013 0:31:54  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
b4ckspin

tf2_medic.png
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 ?
15.05.2013 0:34:18  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
cms

AUP cms 14.11.2012
 
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. Augenzwinkern

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]
15.05.2013 0:36:46  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
Achsel-des-Bösen

AUP Achsel-des-Bösen 06.10.2009
 
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.
15.05.2013 0:38:13  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
b4ckspin

tf2_medic.png
ja stimmt die delete ist nicht so nice fröhlich

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
15.05.2013 0:39:07  Zum letzten Beitrag
[ zitieren ] [ pm ] [ diesen post melden ]
 Thema: pOT-lnformatik, Mathematik, Physik XIII ( Completely Automated Public User Test To tell PIMP )
« vorherige 1 2 3 4 5 6 7 8 9 10 11 12 [13] 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 nächste »

mods.de - Forum » Public Offtopic » 

Hop to:  

Thread-Tags:
Mod-Aktionen:
09.08.2013 17:58:27 Rufus hat diesen Thread geschlossen.
08.04.2013 15:15:29 Teh Wizard of Aiz hat diesem Thread das ModTag 'pimp' angehängt.

| tech | impressum