Pytanie w sprawie hash, c++ – Funkcja mieszania z ciągiem do liczby całkowitej z precyzją

4

Chcę mieszać tablicę znaków w int lub long. Wynikowa wartość musi być zgodna z określoną wartością dokładności. Używana przeze mnie funkcja jest podana poniżej:

<code>int GetHash(const char* zKey, int iPrecision /*= 6*/)
{
        /////FROM : http://courses.cs.vt.edu/~cs2604/spring02/Projects/4/elfhash.cpp

        unsigned long h = 0;
        long M = pow(10, iPrecision);

        while(*zKey)
        {
                h = (h << 4) + *zKey++;
                unsigned long g = h & 0xF0000000L;
                if (g) h ^= g >> 24;
                h &= ~g;
        }            

        return (int) (h % M);
}
</code>

Łańcuch do mieszania jest podobny do „SAEUI1210.00000010_1”.

Jednak w niektórych przypadkach powoduje to powielenie wartości. Czy są jakieś dobre alternatywy, które nie powielają tego samego skrótu dla różnych wartości ciągu.

Spróbuj użyć CRC 32:pl.wikipedia.org/wiki/Crc32 Akira Yamamoto

Twoja odpowiedź

4   odpowiedź
2

Urodziny Problem.

Możesz sprawdzić kryptograficzne funkcje, takie jak MD5 (stosunkowo szybko i nie obchodzi cię, że jest to niebezpieczne), ale będzie również mieć kolizje.

Idealne skróty z definicji tego nie robią. MSalters
1

MD5 lubSHA. Istnieje wiele otwartych implementacji, a wynik jest bardzo mało prawdopodobny, aby uzyskać duplikat wyniku.

Tak. Ale moje wymaganie obejmuje również fakt, że wynik musi być liczbą całkowitą. Skróty MD5 zawierają zarówno znaki int, jak i znaki. Myślę, że to samo dotyczy algorytmów SHA Gayan
Prawda, ale konwersja jest trywialna - od 128-bitowej do 32-bitowej liczby całkowitej. Otrzymasz 2-liniowy kod (skrót, konwersja int), który generuje de facto brak skrótu kolizyjnego. Adam Matan
13

że generuje zduplikowane wartości dla niektórych wartości, ponieważ zakres wartości mieszania jest mniejszy niż przestrzeń mieszanych danych.

Teoretycznie 32-bitowy skrót ma wystarczający zasięg, aby mieszać wszystkie ~ 6 łańcuchów znaków (tylko A-Z, a-z, 0-9), bez powodowania kolizji. W praktyce skróty nie są doskonałą permutacją danych wejściowych. Biorąc pod uwagę 32-bitowy skrót, możesz spodziewać się kolizji hashów po zmieszaniu ~ 16 bitów losowych danych wejściowych, ze względu naurodzinowy paradoks.

Biorąc pod uwagę statyczny zestaw wartości danych, zawsze możliwe jest skonstruowanie funkcji mieszającej zaprojektowanej specjalnie dla nich, która nigdy nie będzie kolidować z samą sobą (oczywiście rozmiar jej wyjścia będzie co najmniejlog(|data set|). Wymaga to jednak wcześniejszego poznania wszystkich możliwych wartości danych. To się nazywadoskonałe mieszanie.

To powiedziawszytutaj jest kilka alternatyw, które powinny Cię uruchomić (są zaprojektowane tak, aby zminimalizować kolizje)

Jedynym sposobem sprawdzenia, która funkcja skrótu jest „najlepsza” dla twoich celów, jest wykonanie testu porównawczego na próbce danych, która pasuje do oczekiwanych rzeczywistych danych. Funkcja, której używasz, nie stara się zbyt mocno mieszać bitów wejściowych, aby utworzyć hash - w każdym kroku miesza się najwyżej 4 najwyższe bity; aw ciągach o długości <8, nawet jeśli tak się nie dzieje, twój skrót po prostu gromadzi wszystkie znaki, z niewielkim nakładaniem się bitów. ASk
Jaka jest najlepsza funkcja haszująca do użycia z podanych w podanym przez Ciebie linku i tej, której używam teraz. Używana przeze mnie funkcja wydaje się być bardziej złożona niż djb2 i sdbm. Czy to oznacza, że ​​lepiej unikać kolizji? Gayan
2

co możesz zrobić, to utworzyć funkcję mieszania z wystarczającą dystrybucją lub głębią bitową (lub obie), aby zminimalizować te kolizje. Ponieważ masz dodatkowe ograniczenie precyzji (0-5?), Będziesz częściej uderzał w kolizje.

Powiązane pytania