Dobra funkcja Hash dla ciągów

Jeśli chodzi o bezpieczeństwo, 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());

Powinieneś prawdopodobnie użyć String.hashCode () .

Jeśli naprawdę chcesz zaimplementować hashCode samodzielnie:

Nie daj się skusić na wykluczenie znaczące części obiektu z obliczenie kodu hashowego w celu poprawy wydajność -- Joshua Bloch, skuteczna Java

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

Oto historia wojenna sparafrazowana na hashcode z " Effective Java":

Zaimplementowana funkcja Hash String we wszystkich wydaniach sprzed 1.2 co najwyżej szesnaście znaków, równomiernie rozmieszczone w całym sznurku, zaczynając z pierwszą postacią. Dla dużych zbiory nazw hierarchicznych, takich jak adresy URL, ta funkcja hash Wyświetlono okropne zachowanie.

Jeśli robisz to w Javie to dlaczego to robisz? Wystarczy wywołać .hashCode() na łańcuchu

Guawa ' S HashFunction (javadoc ) zapewnia przyzwoite hashowanie bez użycia kryptografii.

Ta funkcja dostarczona przez Nick jest dobra, ale jeśli użyjesz nowego ciągu znaków (bajt [] bajtów), aby dokonać transformacji na łańcuch, to się nie uda. 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());
}

May be this can help somebody

// 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;
}

Źródło Logic behind djb2 hash function-SO

Jeśli chcesz zobaczyć implementacje standardów branżowych, zajrzyj do java.Ochrona.MessageDigest .

"Message Digest to bezpieczne jednokierunkowe funkcje skrótu, które pobierają dane o dowolnych rozmiarach i wypisują wartość skrótu o stałej długości."

FNV-1 jest podobno dobrą funkcją skrótu dla łańcuchów.

Dla długich łańcuchów (dłuższych niż, powiedzmy, około 200 znaków), można uzyskać dobrą wydajność z MD4 funkcji hash. Jako funkcja kryptograficzna została złamana około 15 lat temu, ale do celów nie kryptograficznych nadal jest bardzo dobra i zaskakująco szybka. W kontekście Javy trzeba by zamienić 16-bitowe wartości char Na 32-bitowe słowa, np. grupując takie wartości w pary. A szybką implementację MD4 w Javie można znaleźć w sphlib . Prawdopodobnie przesada w kontekście zadania w klasie, ale poza tym warto spróbować.

Sdbm: ten algorytm został stworzony dla biblioteki baz danych sdbm (public-domain reimplementation of 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;
}

Oto link , który wyjaśnia wiele różnych funkcji skrótu, na razie wolę funkcję skrótu ELF dla konkretnego problemu. Przyjmuje jako wejście ciąg o dowolnej długości.

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

Pozwoli to uniknąć kolizji i będzie szybkie, 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);
    }

Dobrym pomysłem jest praca z liczbą nieparzystą podczas próby opracowania dobrej funkcji hast Dla ciągu. ta funkcja pobiera ciąg znaków i zwraca wartość indeksu, jak dotąd jego praca jest całkiem dobra. i ma mniej kolizji. indeks waha się od 0-300 może nawet więcej niż to, ale do tej pory nie osiągnąłem wyższego poziomu nawet z długimi słowami, takimi 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ć, to pomnożyć każdy znak int parse przez indeks, ponieważ rośnie jak słowo "miś" (0 * b) + (1 * e) + (2*a) + (3 * r) co da ci wartość int do gry. pierwsza funkcja hash powyżej zderzają się w "tutaj" i "usłyszeć", ale nadal wielki w dać kilka dobrych unikalnych wartości. ten poniżej nie koliduje z "tutaj" i "usłyszeć", ponieważ mnożę każdy znak z indeksu, jak rośnie.

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 w tabeli skrótów, którą zbudowałem. Jego zasadniczo do podjęcia pliku tekstowego i przechowuje każde słowo w indeksie, który reprezentuje kolejność alfabetyczną.

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

To, co w zasadzie robi, to słowa są haszowane zgodnie z ich pierwszą literą. Tak więc słowo zaczynające się na 'a' otrzymałoby klucz hashowy równy 0, ' b 'otrzymałoby 1 i tak dalej, a' z ' byłoby 25. Cyfry i symbole mają klucz skrótu 26. Jest to zaleta; można łatwo obliczyć i szybko, gdzie dane słowo byłoby indeksowane w tabeli hash, ponieważ jego wszystko w porządku alfabetycznym, coś takiego: Kod można znaleźć tutaj: https://github.com/abhijitcpatil/general

Podając następujący tekst jako wejście: Atticus powiedział do Jema pewnego dnia: "wolałbym, żebyś strzelał do puszek na podwórku, ale wiem, że pójdziesz po ptakach. Strzelać wszystkie niebieskie jays chcesz, jeśli można uderzyć 'em, ale pamiętaj, że zabicie drozda to grzech."To był only time I słyszałem kiedyś, jak Atticus mówił, że to grzech, żeby coś zrobić. Maudie o tym. "Twój ojciec ma rację", powiedziała. "Drozdy nie zrób jedną rzecz z wyjątkiem tworzenia muzyki dla nas, aby cieszyć. Nie jedzą ogrody ludzi, nie gnieżdżą się w łóżeczkach kukurydzianych, nie robią ani jednej rzeczy ale zaśpiewaj ich serca dla nas. Dlatego grzechem jest zabić drozd.

To będzie wyjście:

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