Dobra funkcja skrótu dla ciągów znaków

Próbuję wymyślić dobrą funkcję mieszającą dla ciągów. Pomyślałem, że dobrym pomysłem może być podsumowanie wartości Unicode dla pierwszych pięciu znaków w ciągu (zakładając, że ma pięć, w przeciwnym razie zatrzymaj się tam, gdzie się kończy). Czy to byłby dobry pomysł, czy zły?

Robię to w Javie, ale nie wyobrażam sobie, że miałoby to duże znaczenie.

Zazwyczaj mieszań nie robić sum, inaczej stopi potsbędą miały ten sam hash.

i nie ograniczyłbyś go do pierwszych n znaków, ponieważ w przeciwnym razie house i domy miałyby ten sam skrót.

Generalnie hashy pobierają wartości i mnożą je przez liczbę pierwszą (zwiększa prawdopodobieństwo generowania unikalnych haszów), więc możesz zrobić coś takiego:

int hash = 7;
for (int i = 0; i < strlen; i++) {
    hash = hash*31 + charAt(i);
}

Jeśli jest to kwestia bezpieczeństwa, możesz użyć Java Crypto:

import java.security.MessageDigest;

MessageDigest messageDigest = MessageDigest.getInstance("SHA-256");
messageDigest.update(stringToEncrypt.getBytes());
String encryptedString = new String(messageDigest.digest());

Prawdopodobnie powinieneś użyć String.hashCode () .

Jeśli naprawdę chcesz sam zaimplementować hashCode:

Nie ulegaj pokusie, aby wykluczyć znaczące części obiektu z obliczeń kodu skrótu, aby poprawić wydajność - Joshua Bloch, Effective Java

Używanie tylko pierwszych pięciu znaków to zły pomysł . Pomyśl o nazwach hierarchicznych, takich jak adresy URL: wszystkie będą miały ten sam kod skrótu (ponieważ wszystkie zaczynają się od „http: //”, co oznacza, że ​​są przechowywane w tym samym zasobniku na mapie skrótów, wykazując straszną wydajność.

Oto historia wojenna sparafrazowana na podstawie kodu skrótu String z „ Effective Java ”:

Funkcja skrótu String zaimplementowana we wszystkich wersjach wcześniejszych niż 1.2 sprawdzała co najwyżej szesnaście znaków, równomiernie rozmieszczonych w całym ciągu, zaczynając od pierwszego znaku. W przypadku dużych zbiorów nazw hierarchicznych, takich jak adresy URL, ta funkcja skrótu wykazała okropne zachowanie.

Jeśli robisz to w Javie, dlaczego to robisz? Wystarczy wezwać .hashCode()sznurek

GuavaHashFunction ( javadoc ) zapewnia przyzwoity haszowanie bez szyfrowania.

Ta funkcja dostarczona przez Nicka jest dobra, ale jeśli użyjesz new String (bajt [] bajtów) do przekształcenia w String, nie powiodła się. Możesz użyć tej funkcji, aby to zrobić.

private static final char[] hex = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };

public static String byteArray2Hex(byte[] bytes) {
    StringBuffer sb = new StringBuffer(bytes.length * 2);
    for(final byte b : bytes) {
        sb.append(hex[(b & 0xF0) >> 4]);
        sb.append(hex[b & 0x0F]);
    }
    return sb.toString();
}

public static String getStringFromSHA256(String stringToEncrypt) throws NoSuchAlgorithmException {
    MessageDigest messageDigest = MessageDigest.getInstance("SHA-256");
    messageDigest.update(stringToEncrypt.getBytes());
    return byteArray2Hex(messageDigest.digest());
}

Może to komuś pomoże

// djb2 hash function
unsigned long hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

source Logika funkcji skrótu djb2 - SO

Mówi się, że FNV-1 jest dobrą funkcją mieszającą dla ciągów znaków.

W przypadku długich łańcuchów (dłuższych niż, powiedzmy, około 200 znaków) można uzyskać dobrą wydajność z funkcji skrótu MD4 . Jako funkcja kryptograficzna została zerwana około 15 lat temu, ale do celów niekryptograficznych nadal jest bardzo dobra i zaskakująco szybka. W kontekście Javy należałoby zamienić wartości 16-bitowe charna słowa 32-bitowe, np. Grupując takie wartości w pary. Szybką implementację MD4 w Javie można znaleźć w sphlib . Prawdopodobnie przesada w kontekście zadania w klasie, ale poza tym warto spróbować.

Jeśli chcesz zobaczyć standardowe implementacje branżowe, przyjrzyj się java.security.MessageDigest .

„Digesty wiadomości to bezpieczne jednokierunkowe funkcje skrótu, które pobierają dane o dowolnej wielkości i wyświetlają wartość skrótu o stałej długości”.

tutaj jest link, który wyjaśnia wiele różnych funkcji skrótu, na razie wolę funkcję skrótu ELF dla twojego konkretnego problemu. Jako dane wejściowe przyjmuje ciąg o dowolnej długości.

sdbm: ten algorytm został stworzony dla biblioteki baz danych sdbm (reimplementacja domeny publicznej ndbm)

static unsigned long sdbm(unsigned char *str)
{   
    unsigned long hash = 0;
    int c;
    while (c = *str++)
            hash = c + (hash << 6) + (hash << 16) - hash;

    return hash;
}

         public String hashString(String s) throws NoSuchAlgorithmException {
    byte[] hash = null;
    try {
        MessageDigest md = MessageDigest.getInstance("SHA-256");
        hash = md.digest(s.getBytes());

    } catch (NoSuchAlgorithmException e) { e.printStackTrace(); }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < hash.length; ++i) {
        String hex = Integer.toHexString(hash[i]);
        if (hex.length() == 1) {
            sb.append(0);
            sb.append(hex.charAt(hex.length() - 1));
        } else {
            sb.append(hex.substring(hex.length() - 2));
        }
    }
    return sb.toString();
}

Dobrym pomysłem jest praca z liczbą nieparzystą podczas próby opracowania dobrej funkcji przyspieszającej dla łańcucha. ta funkcja przyjmuje ciąg znaków i zwraca wartość indeksu, na razie działa całkiem nieźle. i ma mniej kolizji. indeks waha się od 0 do 300, może nawet więcej, ale jak dotąd nie doszedłem wyżej, nawet przy długich słowach, takich jak „inżynieria elektromechaniczna”

int keyHash(string key)
{
    unsigned int k = (int)key.length();
    unsigned int u = 0,n = 0;

    for (Uint i=0; i<k; i++)
    {
        n = (int)key[i];
        u += 7*n%31;
    }
    return u%139;
}

inną rzeczą, którą możesz zrobić, jest pomnożenie każdego znaku int parse przez indeks, gdy będzie on zwiększany jak słowo "niedźwiedź" (0 * b) + (1 * e) + (2 * a) + (3 * r), co da ci wartość int do zabawy. pierwsza funkcja skrótu powyżej zderza się w miejscu „tutaj” i „słyszysz”, ale nadal świetnie daje dobre, unikalne wartości. ten poniżej nie koliduje z „tutaj” i „słyszysz”, ponieważ mnożę każdy znak wraz ze wzrostem indeksu.

int keyHash(string key)
{
    unsigned int k = (int)key.length();
    unsigned int u = 0,n = 0;

    for (Uint i=0; i<k; i++)
    {
        n = (int)key[i];
        u += i*n%31;
    }
    return u%139;
}

Oto prosta funkcja skrótu, której używam do zbudowanej przeze mnie tabeli skrótów. Zasadniczo służy do pobierania pliku tekstowego i przechowywania każdego słowa w indeksie, który reprezentuje porządek alfabetyczny.

int generatehashkey(const char *name)
{
        int x = tolower(name[0])- 97;
        if (x < 0 || x > 25)
           x = 26;
        return x;
}

Zasadniczo to oznacza, że ​​słowa są haszowane zgodnie z ich pierwszą literą. Zatem słowo zaczynające się od „a” otrzyma klucz krzyżyka równy 0, „b” otrzyma 1 itd., A „z” będzie równe 25. Liczby i symbole miałyby klucz krzyżyka 26. Jest to zaleta ; Możesz łatwo i szybko obliczyć, gdzie dane słowo byłoby indeksowane w tabeli skrótów, ponieważ jest w porządku alfabetycznym, coś takiego: Kod można znaleźć tutaj: https://github.com/abhijitcpatil/general

Wprowadzając następujący tekst jako dane wejściowe: Atticus powiedział pewnego dnia Jemowi: „Wolałbym, żebyś strzelał do puszek na podwórku, ale wiem, że będziesz polował na ptaki. Zastrzel wszystkie niebieskie sójki, jakie chcesz, jeśli możesz je uderzyć, ale pamiętaj, że zabicie przedrzeźniacza jest grzechem ”. To był jedyny raz, kiedy Atticus mówił, że robienie czegoś jest grzechem, i zapytałem o to pannę Maudie. - Twój ojciec ma rację - powiedziała. „Przedrzeźniacze nie robią tylko jednej rzeczy, poza tworzeniem muzyki dla nas. Nie zjadają ludzkich ogrodów, nie gnieżdżą się w żłóbkach z kukurydzą, nie robią jednego, tylko śpiewają dla nas swoje serca. Dlatego grzechem jest zabicie przedrzeźniacza.

Byłby to wynik:

0 --> a a about asked and a Atticus a a all after at Atticus
1 --> but but blue birds. but backyard
2 --> cribs corn can cans
3 --> do don’t don’t don’t do don’t do day
4 --> eat enjoy. except ever
5 --> for for father’s
6 --> gardens go
7 --> hearts heard hit
8 --> it’s in it. I it I it’s if I in
9 --> jays Jem
10 --> kill kill know
11 --> 
12 --> mockingbird. music make Maudie Miss mockingbird.”
13 --> nest
14 --> out one one only one
15 --> people’s
16 --> 17 --> right remember rather
18 --> sin sing said. she something sin say sin Shoot shot said
19 --> to That’s their thing they They to thing to time the That to the the tin to
20 --> us. up us
21 --> 
22 --> why was was want
23 --> 
24 --> you you you’ll you
25 --> 
26 --> “Mockingbirds ” “Your ‘em “I’d

Pozwoli to uniknąć kolizji i będzie działać szybko, dopóki nie użyjemy przesunięcia w obliczeniach.

 int k = key.length();
    int sum = 0;
    for(int i = 0 ; i < k-1 ; i++){
        sum += key.charAt(i)<<(5*i);
    }