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

160

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.

Leif Andersen
źródło
4
Dobre funkcje skrótu zależą w dużym stopniu od danych wejściowych do skrótu i ​​wymagań algorytmu. Taki hash nie będzie zbyt dobry, jeśli na przykład wszystkie ciągi znaków zaczynają się od tych samych pięciu znaków. Będzie również powodował normalny rozkład.
WhirlWind,
1
Możliwy duplikat 98153
Michael Mrozek
14
Dlaczego nie możesz użyć Stringwłasnego hashCode()?
Bart Kiers,
@WhirlWind, prawda, nie jestem pewien, jakie będą napisy, poza tym prawdopodobnie będzie to tekst w języku angielskim.
Leif Andersen
@Barl, głównie dlatego, że mój profesor kazał nam zaimplementować nasz własny funktor haszujący ... a powodem, dla którego nie chciałem używać Javy, był fakt, że był on ogólny i wyobrażam sobie, że bardziej szczegółowy funktor haszujący byłby lepszy.
Leif Andersen

Odpowiedzi:

161

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);
}
jonathanasdf
źródło
@jonathanasdf Jak możesz powiedzieć, że zawsze daje Ci unikalny klucz mieszający. Czy jest jakiś dowód matematyczny? Myślę, że musimy wziąć mod hasza z inną większą liczbą pierwszą, w przeciwnym razie wystąpi problem z przepełnieniem.
devsda
17
@devsda Nie powiedział, że zawsze jest wyjątkowy, powiedział raczej, że prawdopodobnie będzie wyjątkowy. Jeśli chodzi o powód, szybkie wyszukiwanie w Google ujawnia ten artykuł: computinglife.wordpress.com/2008/11/20/… wyjaśniający, dlaczego 31 został użyty do mieszania ciągów Java. Nie podano matematycznego dowodu, ale wyjaśnia on ogólną koncepcję, dlaczego liczby pierwsze działają lepiej.
Pharap
2
Wielkie dzięki za wyjaśnienie pomysłu lepszego haszowania. Tylko do podwójnego sprawdzenia - wartość zwracana przez hashCode () zostanie użyta przez Javę do odwzorowania na jakiś indeks tabeli przed zapisaniem obiektu. Tak więc, jeśli hashCode () zwraca m, wykonuje coś w rodzaju (m mod k), aby uzyskać indeks tabeli o rozmiarze k. Czy to prawda?
whitehat
1
"hash = hash * 31 + charAt (i);" tworzy ten sam skrót dla spot, tops, stop, opts i pots.
Jack Straub
1
@maq Wierzę, że masz rację. Nie wiem, o czym myślałem.
Jack Straub
139

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());

źródło
93
Miły. Mam aplikację do uczenia maszynowego, wykonującą statystyczne NLP na dużym korpusie. Po kilku początkowych przebiegach normalizacji morfologicznej oryginalnych słów w tekście wyrzucam wartości ciągów i zamiast tego używam kodów skrótów. W całym moim korpusie jest około 600 000 unikalnych słów, a używając domyślnej funkcji kodu skrótu java, uzyskiwałem około 3,5% kolizji. Ale jeśli SHA-256 wartość ciągu, a następnie wygeneruję kod skrótu z trawionego ciągu, współczynnik kolizji jest mniejszy niż 0,0001%. Dzięki!
benjismith
3
Dziękujemy za podanie informacji o kolizjach i liczbie słów. Bardzo pomocne.
philipp
19
@benjismith Jeden na milion jest o wiele za duży… czy „mniej niż 0,0001%” to ukośne określenie „dokładnie 0”? Naprawdę wątpię, że widziałeś kolizję SHA-256, ponieważ nigdy jej nie zaobserwowano, nigdzie, nigdy; nawet dla 160-bitowego SHA-1. Jeśli masz dwa łańcuchy, które generują ten sam SHA-256, społeczność bezpieczeństwa chciałaby je zobaczyć; będziesz znany na całym świecie ... w bardzo niejasny sposób. Zobacz porównanie funkcji SHA
Tim Sylvester
7
@TimSylvester, źle zrozumiałeś. Nie znalazłem kolizji SHA-256. Obliczyłem SHA-256, a następnie wprowadziłem wynikowe sekwencje bajtów do typowej funkcji „hashCode” w języku Java, ponieważ potrzebowałem 32-bitowego skrótu. Tam znalazłem kolizje. Nic niezwykłego :)
benjismith
1
Czy nie ma różnicy między „haszowaniem” a „szyfrowaniem”? Rozumiem, że MessageDigest to jednokierunkowa funkcja mieszająca, prawda? Ponadto, kiedy korzystałem z tej funkcji, po otwarciu pliku w LibreOffice otrzymałem zaszyfrowany ciąg znaków jako dużo niepotrzebnych znaków UTF. Czy można uzyskać zaszyfrowany ciąg jako losową grupę znaków alfanumerycznych zamiast niepotrzebnych znaków UTF?
Nav
38

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.

Frederik
źródło
1
Jeśli używasz kolekcji z podwójnym haszowaniem, może być warto, aby pierwszy hash był naprawdę szybki i brudny. Jeśli ktoś ma tysiąc długich ciągów, z których połowa jest odwzorowana przez kiepską funkcję na jedną konkretną wartość, a połowa z nich jest odwzorowana na różne wartości, wydajność w tabeli z pojedynczym haszowaniem byłaby zła, ale wydajność w podwójnej tablica mieszana, w której drugi hash zbadał cały ciąg, może być prawie dwa razy większa niż tablica z pojedynczym hashem (ponieważ połowa ciągów nie musiałaby być w pełni zaszyfrowana). Jednak żadna ze standardowych kolekcji Java nie wykonuje podwójnego haszowania.
supercat,
Łącze Efektywna Java jest uszkodzony @Frederik
KGS
17

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

Pirolistyczne
źródło
2
Robię to w ramach zajęć, a częścią zadania jest napisanie kilku różnych funkcji skrótu. Profesor kazał nam szukać pomocy z zewnątrz dla „lepszych”.
Leif Andersen
20
Jeśli chcesz, aby Twoja platforma była spójna we wszystkich wersjach maszyny JVM i implementacjach, nie powinieneś polegać na .hashCode(). Zamiast tego użyj jakiegoś znanego algorytmu.
Stephen Ostermiller
7
Algorytm for String::hashCodejest określony w JDK, więc jest tak przenośny, jak samo istnienie klasy java.lang.String.
yshavit
12

GuavaHashFunction ( javadoc ) zapewnia przyzwoity haszowanie bez szyfrowania.

Mike Samuel
źródło
1
Jest nadal w wersji beta od tego komentarza
ThomasRS
1
A teraz 404d.
Shawn
8

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

Festus Tamakloe
źródło
Możesz po prostu przekazać tablicę bajtów do messageDigest.update ().
szgal
byteArray2Hex () - dokładnie tego szukałem! Wielkie dzięki :)
Krzysiek
5
// 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

Pratik Deoghare
źródło
1
Myślę, że to tylko liczba pierwsza, od której można zacząć, aby było mniej kolizji.
CornSmith
5

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ć.

Thomas Pornin
źródło
Ta funkcja skrótu jest o wiele lepsza niż ta, która jest dostarczana z Javą.
clankill3r
3

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”.

Dean J.
źródło
1

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.

Yefei
źródło
1

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;
}
Anchal
źródło
0
         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();
}
Charaf JRA
źródło
-1

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;
}
kanthonye
źródło
-1

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 dont dont dont do dont do day
4 --> eat enjoy. except ever
5 --> for for fathers
6 --> gardens go
7 --> hearts heard hit
8 --> its in it. I it I its 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 --> peoples
16 --> 17 --> right remember rather
18 --> sin sing said. she something sin say sin Shoot shot said
19 --> to Thats 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 youll you
25 --> 
26 --> Mockingbirds  Your em Id
user2311285
źródło
2
Dobra funkcja skrótu rozkłada wartości równo w segmentach.
Jonathan Peterson
-1

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);
    }
kamal el-deen shair
źródło