Wyjątkowo identyfikujące adresy URL z jednym 64-bitowym numerem

Question

Jest to w zasadzie problem matematyczny, ale bardzo związany z programowaniem: jeśli mam 1 miliard ciągów zawierających adresy URL i biorę pierwsze 64 bitów sumy kontrolnej MD5 każdego z nich, rodzaj częstotliwości kolizji powinienem się spodziewać?

Jak zmienia się odpowiedź, jeśli mam tylko 100 milionów adresów URL?

Wydaje mi się, że kolizje będą niezwykle rzadkie, ale te rzeczy wydają się mylące.

Czy mogę lepiej użyć czegoś innego niż MD5? Pamiętaj, że nie szukam bezpieczeństwa, tylko dobra funkcja szybkiego mieszania. Również natywne wsparcie w MySQL jest miłe.

EDIT: not quite a duplicate

Answer 1

Jeśli pierwsze 64 bity MD5 stanowiły skrót z idealną dystrybucją, paradoks urodzin nadal będzie oznaczać, że będziesz dostawał kolizje na każde 2^32 adresy URL. Innymi słowy, prawdopodobieństwo kolizji to liczba adresów URL podzielona przez 4 294 967 296. Aby uzyskać szczegółowe informacje, patrz http://en.wikipedia.org/wiki/Birthday_paradox#Cast_as_a_collision_problem.

Nie czułbym się komfortowo, po prostu wyrzucając połowę bitów w MD5; byłoby lepiej XOR wysokie i niskie 64-bitowe słowa, aby dać im szansę na wymieszanie. Z drugiej strony MD5 wcale nie jest szybki ani bezpieczny, więc nie zawracałbym sobie tym głowy. Jeśli chcesz uzyskać oślepiającą prędkość z dobrą dystrybucją, ale bez pozorów bezpieczeństwa, możesz wypróbować 64-bitowe wersje programu MurmurHash. Aby uzyskać szczegółowe informacje i kod, patrz: http://en.wikipedia.org/wiki/MurmurHash.

Answer 2

Państwo określili to jako "Birthday-paradoksu", myślę, że know the answer already.

P(Collision) = 1 - (2^64)!/((2^64)^n (1 - n)!) 

gdzie n oznacza 1 miliard w Twoim przypadku.

Będziesz nieco lepiej używać czegoś innego niż MD5, ponieważ MD5 ma pratical collusion problem.

Answer 3

Z tego co widzę, trzeba funkcji skrótu z następującymi wymaganiami,

1. Hash dowolnej długości struny do wartości 64-bitowej
   • Bądź dobry - uniknąć kolizji
   • Nie koniecznie w jedną stronę (zabezpieczenie nie jest wymagane)
   • Najlepiej szybko - co jest niezbędną cechą aplikacji niezwiązanej z ochroną

Ten hash function survey może być przydatny podczas wiercenia w dół do najbardziej odpowiedniej funkcji.
Proponuję przetestować wiele funkcji stąd i scharakteryzować je pod kątem prawdopodobnego zestawu danych wejściowych (wybierz kilka miliardów adresów URL, które według Ciebie zobaczysz).

Można faktycznie wygenerować another column like this test survey dla listy testowych adresów URL w celu scharakteryzowania i wyboru istniejących lub nowych funkcji skrótu (więcej wierszy w tej tabeli), które można sprawdzić. Mają kod źródłowy MSVC++ na początek (reference to ZIP link).

Zmiana funkcji mieszania w celu dopasowania do szerokości wyjściowej (64-bit) zapewnia dokładniejszą charakterystykę dla aplikacji.

Answer 4

Za pomocą skrótu zawsze istnieje ryzyko kolizji. I nie wiadomo wcześniej, że zderzenia będą miały miejsce raz lub dwa razy, a nawet setki lub tysiące razy na liście adresów URL.

Prawdopodobieństwo jest nadal tylko prawdopodobieństwem. To jak rzucanie kostką 10 lub 100 razy, jakie są szanse na zdobycie wszystkich szóstek? Prawdopodobieństwo mówi, że jest niskie, ale wciąż może się zdarzyć. Może nawet wiele razy z rzędu ...

Podczas gdy birthday paradox pokazuje, jak obliczyć prawdopodobieństwa, nadal musisz zdecydować, czy kolizje są dopuszczalne, czy nie.

... a kolizje są dopuszczalne, a hashe są nadal właściwą drogą; znajdź 64-bitowy algorytm mieszający, zamiast polegać na "pół-a-MD5" o dobrej dystrybucji. (Choć prawdopodobnie ma ...)

Answer 5

Jeśli masz 2^n hash możliwości, istnieje ponad 50% szans na kolizję, gdy masz 2^(n/2) przedmiotów.

E.G. jeśli twój hasz ma 64 bity, masz 2^64 hash możliwości, masz 50% szansy na kolizję, jeśli masz 2^32 pozycji w kolekcji.