C++ Hashfunktion implementieren?

...komplette Frage anzeigen

3 Antworten

Die Berechnungsvorschrift sieht nach einer typischen Rekursion aus.

head(str) ist ziemlich sicher str um das letzte Byte verkürzt und tail das letzte Byte.

Bei der Linksrotation würde ich das erste Bit rausnehmen und nach dem Schieben rechts einfügen. Z. B.:

unsigned char ROT(unsigned char c) {
unsigned char msb = c & 0x80;
unsigned char rest = c & 0x7f;
rest <<= 1;
return rest | (msb>>7);
}

Die Bildungsvorschrift von string_hash kannst du so ziemlich aus der Aufgabenstellung abschreiben.

Ahh ok ich habe den head dann falsch angenommen :D, aber kannst du das kurz erklären wie kommst du auf diese werte 0x80 , 0x7f  ?

0
@RealAutism

0x80 = binär 1000.0000, nur das höchstwertige Bit gesetzt (also das, das wir später als niederstwertiges Bit anhängen wollen)

0x7F = binär 0111.1111, alle anderen Bits gesetzt - Maske, um das höchstwertige Bit zurückzusetzen vor der ShiftLeft-Operation

1

Ich hätte eine rekursive Funktion erstellt.

int string_hash(string str)
{
    if (str.length() == 0)
    {
         return 0;
    }

    string head = str.substring(0, str.length() - 1);
    
    int temp = string_hash(head) ^ str[str.length() - 1];
    
    // Evtl. Limits libary benutzen
    return (temp << 1) && (temp >> 7);
    
}

Leider kann ich grad nicht testen ob der Code funktioniert.

Beim return muss (temp << 1) | (temp >> 7) stehen. Gleich zwei Fehler an einer Stelle 😂😂

1
@okarin

ach alles gut ich teste es morgen mal ist jetzt etwas spät^^ aber ist der head nicht von 0 bis str.length()-2 also um einen verkürzt?

0

Da war ich mir auch nicht ganz sicher. Aber ich glaube es sollte so passen da ich dort ja eine Länge angebe und keinen index. Wenn ich beispielsweise einen String der Länge zwei hätte würd ich dort vom 0ten index 1 Zeichen nach vorne gehen also hätte ich genau ein Zeichen.

0

Achso da ich da ja int hab musst du beim Return wahrscheinlich sizeof(int) * 8 - 1 statt 7 schreiben. Ist so oder so besser das so zu machen.

1

Was möchtest Du wissen?