Rehasing: Was ist, wenn es den Hash auch schon gibt?

Also wenn bei der normalen Hashfunktion eine Kollision auftritt nehmen wir ja die Rehashfunktion und springen entsprechend ein paar Felder weiter. Was ist, wenn dieses Feld auch belegt ist? Nochmal genau so weit springen oder was anders?

Und wenn ich zufällig unten ankomme obwohl oben noch Platz wäre, was dann?

3 Antworten

hayday675

14.07.2020, 18:40

immer weiter hashen

helpmewismath

Fragesteller

14.07.2020, 19:10

Aber wie?

uchimuchipuchi

14.07.2020, 18:57

Ich gehe davon aus, dass du von einer Art Hashmap redest?

Wenn ja, hast du da etwas missverstanden.

Man nutzt Rehashing NICHT wenn es zu Kollisionen kommt, sondern wenn ein sog. Loadfactor überschritten ist.

Für eine Hashmap mit nur 5 Buckets wäre das hier völlig OK und noch kein Grund zum rehashen:

0: foo, bar, baz
1:
2:
3: qux
4:

Wenn du von einer perfekten Hashmap ohne Kollisionen ausgehst, kannst du lange rehashen und dabei tonnenweise sinnlos Speicher verbraten.

Es gibt aber Werkzeuge, die dir für einen bestimmten Satz an Objekten einen perfekten Hashalgorithmus (bzw. IV) generieren, aber das dauert bei großen Datenmengen gerne mal mehrere Stunden und ist sowieso nur in Sonderfällen notwendig.

Beim Hashen musst du immer mit Kollisionen rechnen. Und diese können natürlich auch mehrfach bzw. wiederholt auftreten.

Ein Problem ist das i. d. R. aber nicht. :)

Woher ich das weiß:Berufserfahrung

helpmewismath

Fragesteller

14.07.2020, 19:03

Ja ich meine eine Hashmap :)

Also wir haben eben 3 Möglichkeiten gelernt, Kollisionen zu handlen

Dein 0er Hash würde ja Chaining verwenden, aber angenommen ich muss in der Prüfung halt mit Rehashing arbeiten.

0:
1:foo
2:
3:bar
4:

jetzt will ich baz einfügen: hash(baz) = 1, rehash(baz) = 2

Sowohl 1 als auch 3 sind belegt. Wie geht es nun weiter?

uchimuchipuchi

14.07.2020, 19:17

@helpmewismath

Solange rehashen, bis es keine Kollisionen mehr gibt.

Das führt aber potentiell zu Endlosschleifen, also sei in der Praxis bitte sehr vorsichtig, falls du so etwas implementieren solltest. :)

helpmewismath

Fragesteller

14.07.2020, 19:18

@uchimuchipuchi

Alles klar, danke! Also würde ich hier immer 2er Schritte vorwärts machen und wenn ich unten bin wieder oben los legen. Hier würde ich dann bei der 0 landen?

KarlRanseierIII

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Computer, Technik, programmieren

14.07.2020, 22:28

Cuckoohashing?

Das wäre zumindest ad hoc das einzige, was mit mit Rehashing einfiele...

Ähnliche Fragen

Bewegungsfelder im RPG-Maker?

Hey,

Ich habe im RPG Maker (MZ, falls das interessiert) so Bewegungsfelder gemacht, die einen automatisch über das Feld bewegen.

Also, die Goldenen Felder sind die Felder, wo der Spieler rübergeschubst wird (Felder haben Kollision, vor dem Bewegen des Spielers wird ihm das Laufen durch Wände ermöglicht, und danach wieder weg genommen).

Die Goldenen Felder mit dem Kreis drinnen sind normale Felder, wo der Spieler drauf laufen kann (keine Kollision).

Die Felder mit den Pfeilen, wo die Events drauf sind, sind die Bewegungsfelder (keine Kollision). Wenn man auf die Läuft, soll man so lange in die gezeigte Richtung geschubst werden, bis man auf ein Belaufbares Feld (ein weiteres Bewegungsfeld, oder ein goldenes mit Kreis drinnen). Um das zu erreichen, habe ich für jedes Feld einzeln die Länge zum nächsten belaufbaren Feld eingestellt.

Problem jetzt: wird man von einem Bewegungsfeld auf ein anderes geschubst, wird das zweite Bewegungsfeld nicht aktiwiert, was ja aber sein soll.

Frage: Wie mache ich, dass die Felder sich automatisch gegenseitig aktivieren? (Aktuell sind die Felder: Pririty: Below Characters / Trigger: Player Touch)

...zur Frage

Javascript - leere Variable prüfen?

Ich habe die letzten Tage angefangen, mich mit Programmierung in HTML und Javascript zu befassen, die ersten Dinge sind auch gelaufen, aber jetzt stehe ich vor einem Problem, wo mir weder youtube noch Google Suche ein Ergebnis liefern konnten, das funktionierte, wahrscheinlich ist es trotzdem einfach aber ich komme nicht drauf:

Ich möchte eine Art Checkliste erstellen, aus einem Eingabefeld soll ein Text ins nächste freie Feld eingefügt werden, dazu muss ich (nach meinem Kenntnissstand, was ich bisher gemacht habe, und was funktionierte, ohne mich dazu zusätzlich belesen zu haben), über if... else Bedingungen nacheinander prüfen ob die vorherigen Felder (text1, text2, text3... jeweils eine eigene Variable) leer sind, um das dann entweder in das Feld einzufügen oder das nächste zu prüfen...
Wenn alle verfügbaren Felder gefüllt sind, soll beim Versuch, die Eingabe zu machen in einem extra Feld eine Meldung kommen "Liste voll", bei meinen bisherigen Versuchen, obwohl kein Feld belegt ist, springt das Programm sofort zu diesem Punkt, stellt also offensichtlich nicht fest, dass die Variablen der vorherigen Felder noch NICHT belegt sind

(Das gleiche soll dann passieren, wenn ein Punkt erledigt ist, jeweils über einen Button soll dieser Punkt entfernt werden und falls nachfolgende Felder belegt sind, diese jeweils nachrücken (also wenn das nachfolgende Feld belegt ist, den Inhalt dieser Variable übernehmen, sonst Variable leeren))

...zur Frage

Tic Tac Toe Programm Unentschieden auswerten wird falsch gemacht?

Hallo, ich habe bei meinem selbst Programmierten Java TicTacToe Spiel eine Methode geschrieben, mit der man überprüft wer/ob jemand gewonnen hat.Die funktioniert auch gut, in der "else if" Verzweigung prüfe ich ob alle Felder belegt sind.Aber wenn ich zum Beispiel Feld[1] beim spielen belege, dann wird trotzdem Unentschieden ausgegeben.

else if (Feld[1].equals ("x") || Feld[1].equals ("o") &&
                      Feld[2].equals ("x") || Feld[2].equals ("o") &&
                      Feld[3].equals ("x") || Feld[3].equals ("o") &&
                      Feld[4].equals ("x") || Feld[4].equals ("o") &&
                      Feld[5].equals ("x") || Feld[5].equals ("o") &&
                      Feld[6].equals ("x") || Feld[6].equals ("o") &&
                      Feld[7].equals ("x") || Feld[7].equals ("o") &&
                      Feld[8].equals ("x") || Feld[8].equals ("o") &&
                      Feld[9].equals ("x") || Feld[9].equals ("o")) {
                      
                      System.out.println("Unentschieden");
                    }

Über jede Hilfe/Tipps würde ich mich gewaltig freuen.

...zur Frage

Caldera Forms (WordPress)?

Kennt sich zufällig jemand mit dem Plugin Caldera Forms aus?

Wenn ich normalerweise eine Eingabe, von bspw. einem Textfeld überprüfen will, kann ich vor dem Absenden eine Datenvalidierung durchführen, bspw. mit document.getElementById().value.

Aber ich verstehe die Syntax bzw. die Logik bei Caldera Forms nicht wirklich. Ich habe mich versucht einzulesen und was ich an Informationen mitgenommen habe ist, dass ich einen Preprocessor brauche, oder?

Ich muss in der functions.php-Datei addfilter oder addfunction hinzufügen und dort meine Funktion schreiben. Aber wie genau hole ich dort aus meinem Formular die Werte meiner Felder? Oder wie kann ich eine Fehlermeldung in einem Feld ausgeben, wenn ein falscher Wert in einem anderen Feld eingegeben wurde?Oder wie kann ich von dort aus auf meine Datenbank zugreifen um mit diesen Daten eine Überprüfung durchzuführen?

Wäre wirklich über jede Hilfe dankbar.

...zur Frage

Ist es möglich einen Base64 String zu verkürzen?

Moin,

in PHP würde ich gerne den Base64 String verkürzen... Als Beispiel nehme ich folgenden Code:

$str1 = 'Hallo';
$str2 = 'Dieser Satz ergibt eine längere Base64-Zeichenkette';
base64_encode($str1); //OUTPUT: SGFsbG8=
base64_encode($str2); //OUTPUT: RGllc2VyIFNhdHogZXJnaWJ0IGVpbmUgbMOkbmdlcmUgQmFzZTY0LVplaWNoZW5rZXR0ZQ==

Wie also könnte ich hier den zweiten String so verkürzen, dass ich ihn auch wieder "entschlüsseln" kann?

Danke im Voraus!

...zur Frage

Hash Code entschlüsseln?

Bei einem hash code benötigt man ja einen bestimmten key um eine z.b nachricht zu verschlüsseln und zu entschlüsseln. Jetzt ist aber meine Frage wie bekommt der empfänger einer nachricht den key? der kann ja nicht einfach so zugeschickt werden, weil dadurch ja dritte den key auch bekämen und dadurch der hash keinen sinn mehr machen würde

...zur Frage

Beschwörung auf gegnerische Spielfeldseite, wenn alle Monsterzonen belegt sind?

Einmal angenommen ich habe 5 Monster nacheinander in meine Monsterzonen beschworen. Nun sage ich eine Xyz-Beschwörung an. Ziel: Alle 5 Monster als Xyz-Material anhängen. Mein Gegner möchte das mit 'Fliegendes "C"' verhindern. Frage: Geht das, und wann müsste er sich ggf. anketten? In dem Moment, wo ich meine Beschwörung ansage, ist ja im Grunde kein Platz in meinen Monsterzonen. Wie kann er mir da was aufs Feld beschwören?

...zur Frage

Wie kann ich die Formel für die Gleitzeitliste in Excel anpassen?

Aloah! Ich habe wie im Bild zu sehen ist eine Gleitzeitliste erstellt. Was nicht zu sehen ist ist, dass in A1 "08:00" drin steht. Ich hätte gerne, dass das Plus oder eben das Minus nicht wie hier in zwei unterschiedlichen, sondern in nur EINER Spalte berechnet wird. Ich habe soweit mal folgende Formel geschaffen:

=WENN(D2>A1;D2-A1;WENN(D2<A1;A1-D2;0))

Allerdings kommt da bei einem Minus nichts raus, sondern füllt das Feld mit lauter Raute Zeichen. Wie kann ich nun die Formel entsprechend anpassen? Die Felder sind btw als "Uhrzeit" formatiert.

...zur Frage

Php passwort verschlüsseln?

Hab mir ein Video angesehen das schon von 2016 ist und der Youtuber meinte selber das es eine bessere Methode geben kann als sha512.

$passwort = "einwichtigespasswort";
echo  hash("sha512", $passwort);

Was ist das aktuellste heutzutage ?

...zur Frage

Mein Instagram Hash Passwort herausfinden?

Wie kann ich die Hash von meinem Instagram passwort herrausfinden

...zur Frage

Wie springt man zum Anfang der main Methode in Java?

Ich habe einen Rechner in Java geschrieben und möchte den Nutzer des Programms fragen ob er noch etwas ausrechnen möchte bevor sich das programm schließt. Und ich bekomme es nicht hin zum Anfang der main Methode zu springen. Ist das überhaupt möglich? Oder gibt es auch einen anderen weg. Vielen dank im voraus.

...zur Frage

Wie kann ich den String hashen?

Ich code derzeit was in Java. Ich bekomme das Password als String vom User und hätte vorgehabt das bei der Registrierung dann mit diesem SQL command zu speichern:

String command = "INSERT INTO userdata(username, password)VALUES ('" + username + "', 'HASHBYTES('SHA2_256', "+user_password+")')";

Vorerst mal, Stimmt das so? Kann das funktionieren? Direkt in Java will ich den hash nicht generieren weil mir das unnötig aufwendig vorkommt.

Beim login habe ich vor den (schon gehashten) String des echten passwords mit dem hash der usereingabe des login passwords zu vergleichen. Doch wie mach ich das in SQL? Dass ich keine Daten in die Tabelle schreibe sondern nur verhashen lasse und dann den hash direkt zurückbekomme..

Vielen Dank im Voraus!

...zur Frage

Php Hashen mit "Salz" / PASSWORD_DEFAULT?

$password = "passwort";
$hashed = password_hash($password, PASSWORD_DEFAULT);
if(password_verify($password, $hashed)){
    echo $hashed;
}

Also so würde ich jetzt den string "passwort" hashen mit etwas vollkommen zufälligem / salz und es zb auf meiner datenbank speicher, alles schön und gut.

Jetzt kommt das große aber, wenn ich die Seite von irgendwo anders aufrufe. Dann mich einloggen will wird das eingegebene wieder gehasht mit einem salz um es mit der sql datenbank abzugleichen.

Das geht aber garnicht weil dieses Salz doch immer ein anderer ist wenn ihr versteht was ich meine.

Hashes ohne salz vergleichen kriege ich schonmal ohne probleme hin.

zum beispiel so würde mein login/abgleich mit der datenbank aussehen :

if(isset($_POST["username"]) && isset($_POST["password"])){

$hash = hash("sha512", $_POST["password"]);

$mysqli1 = new mysqli($servername, $user, $pw, $db);
$result = $mysqli1->query('SELECT id FROM user WHERE username = "'. $_POST["username"]. '"  ');
$result1 = $mysqli1->query('SELECT id FROM user WHERE password = "'. $hash. '"  ');

if($result->num_rows == 1 and $result1->num_rows == 1 ) {
  echo "Login erfolreich"; 
} else {
    echo "Falsches Passwort oder Nutzername";
}
$mysqli1->close();
}

Hab jetzt mysqli benutzt weil es irgendwie übersichtlicher ist, und ob das anfällig für Sql Injections oder so ist spielt eigentlich keine rolle erstmal. Manche stört das

...zur Frage

Wikipedia Änderungen nicht übernommen?

Hi,

ich habe letztens einen Wikiartikel ergänzt und zur Ergänzung entsprechend Quellen angegeben. Einige der Quellen waren sogar schon vorher angegeben, wie ein Szenewikiartikel. Mir wurde auch die Änderung angezeigt und habe dann nochmal geguckt, dass es wirklich übernommen wurde.

Gestern, ca. 1 Woche nach meiner Änderung, bei einem Kumpel hat der zufällig genau danach gegoogelt, worauf ich gesagt habe, dass ich das letztens erst ergänzt habe. Nur waren alle meine Ergänzungen weg... die Quellen die offiziell angegeben sind und in denen alle meine Ergänzungen belegt sind stehen weiterhin da. Was zur Hölle ist da los? Wird da einfach willkürlich entschieden? Oder durch eine KI die nicht immer fehlerfrei arbeitet? Wozu dann ein Wiki, das ergänzt werden kann, wenn es nachträglich wieder entfernt wird, obwohl es klar nachvollziehbar belegt ist?

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen