Dla jakiego rodzaju danych są operacje tabeli skrótów O (1)?

Od odpowiedzi do (Kiedy) jest wyszukiwanie tablicy skrótów O (1)? , Rozumiem, że tabele skrótów mają $O(1)$zachowanie w najgorszym przypadku ) , przynajmniej zamortyzowane, gdy dane spełniają określone warunki statystyczne, i istnieją techniki, które pomagają rozszerzyć te warunki.

Jednak z perspektywy programisty nie wiem z góry, jakie będą moje dane: często pochodzą one z zewnętrznego źródła. I rzadko mam wszystkie dane naraz: często wstawianie i usuwanie odbywa się z częstotliwością, która nie jest znacznie niższa niż liczba wyszukiwań, więc wstępne przetwarzanie danych w celu dostrojenia funkcji skrótu jest wyłączone.

Tak więc, robiąc krok naprzód: mając pewną wiedzę na temat źródła danych, w jaki sposób mogę ustalić, czy tabela skrótów ma szansę na wykonanie operacji i ewentualnie jakich technik użyć w funkcji skrótu?$O(1)$

Istnieje kilka technik, które gwarantują, że wyszukiwanie zawsze będzie wymagało operacji O (1), nawet w najgorszym przypadku.

Jak mogę ustalić, czy tabela skrótów ma szansę na wykonanie operacji O (1) i ewentualnie jakich technik użyć w funkcji skrótu?

Najgorszy przypadek ma miejsce, gdy jakiś złośliwy atakujący (Mallory) celowo przekazuje dane, które Mallory specjalnie wybrał, aby spowolnić działanie systemu.

Po wybraniu określonej funkcji skrótu prawdopodobnie zbyt optymistyczne jest założenie, że Mallory nigdy nie dowie się, którą funkcję skrótu wybrałeś. Gdy Mallory odkryje, którą funkcję skrótu wybrałeś, jeśli pozwolisz Mallory'emu dać ci dużo danych, które chcesz wstawić do swojej tabeli skrótów za pomocą tej funkcji skrótu, to jesteś skazany: Mallory może wewnętrznie szybko wygenerować miliardy elementów danych, mieszając je z twoim funkcja skrótu, aby znaleźć, które elementy danych mogą się zderzyć, a następnie nakarmić miliony jeden na tysiąc elementów danych, które mogą się zderzyć, co prowadzi do wyszukiwania, które działają znacznie wolniej niż O (1).

Wszystkie techniki gwarantujące „O (1) wyszukiwanie nawet w najgorszym przypadku” pozwalają uniknąć tego problemu, wykonując trochę dodatkowej pracy przy każdym wstawieniu, aby zagwarantować, że w przyszłości każde możliwe wyszukiwanie może zakończyć się sukcesem w O (1) czasie . W szczególności zakładamy (w najgorszym przypadku), że Mallory prędzej czy później odkryje, której funkcji skrótu używamy; ale dostaje on tylko szansę na wstawienie kilku elementów danych, zanim wybieramy inną funkcję skrótu - skrót tabulacji lub inny uniwersalny skrót - taki, który specjalnie wybieramy, aby wszystkie dane, które do tej pory mogliśmy przeglądać, w 2 lub 3 sondy - tj. O (1). Ponieważ losowo wybieramy tę funkcję, możemy być całkiem pewni, że Mallory przez jakiś czas nie będzie wiedział, którą funkcję wybraliśmy. Nawet jeśli Mallory natychmiastdaje nam dane, które nawet przy tej nowej funkcji skrótu kolidują z poprzednimi danymi, możemy następnie wybrać kolejną świeżą nową funkcję skrótu, dzięki której po ponownym skróceniu wszystkie poprzednie dane, które on i wszyscy inni nam karmili, można teraz wyszukać w 2 lub 3 sondach w najgorszym przypadku - tj. wyszukiwania O (1) w najgorszym przypadku.

Dosyć łatwo jest losowo wybrać nową funkcję skrótu i ​​powtarzać całą tabelę wystarczająco często, aby zagwarantować, że każde wyszukiwanie ma zawsze wartość O (1). Chociaż gwarantuje to, że każde wyszukiwanie ma zawsze wartość O (1), techniki te, wstawiając N-ty element do tablicy mieszającej, która już zawiera N-1 elementy, mogą czasami wymagać O (N) czasu na wstawienie. Możliwe jest jednak zaprojektowanie systemu w taki sposób, że nawet jeśli Mallory celowo poda nowe dane, które przy użyciu nowej funkcji skrótu kolidują z poprzednimi danymi, system może zaakceptować wiele przedmiotów od Mallory i innych, zanim będzie musiał zrobić pełna odbudowa O (N). Techniki tabeli mieszania, które wybierają nową funkcję i powtarzają, aby zagwarantować wyszukiwanie O (1), nawet w najgorszym przypadku, obejmują:

• kukułka mieszaja gwarantuje, że każdy klawisz wyszukiwanie powiedzie się z co najwyżej 2 obliczeń hash i 2 wyszukiwań stołowych.
• mieszanie klasy gra w karty gwarantuje, że każde wyszukiwanie klucza zakończy się powodzeniem po sprawdzeniu małej liczby H (być może H = 32) kolejnych wpisów w tabeli.
• dynamiczne idealne haszowanie - artykuł Dietzfelbinger z 1994 r. jest pierwszym, który przeczytałem, w którym zwróciłem uwagę, że mimo że „przerabia” często, aby zagwarantować, że każde wyszukiwanie klucza zawsze kończy się 2 obliczeniami skrótu i ​​2 przeglądami, jest to możliwe aby wykonać pełne powtórzenie tak rzadko, że chociaż każde pełne powtórzenie wykorzystuje czas O (n), oczekiwany średni koszt wstawiania i usuwania jest amortyzowany przez O (1).

Struktury danych / tabele skrótów

$O(1)$

$O(1)$$O (n^2 W)$

$O(\sqrt{\log n / \log \log n})$$O(1)$

$h_{a,b}(x) = ax + b \mod p$

W przeszłości, według artykułu Usenix autorstwa Crosby i Wallacha , popularne języki programowania nie robiły czegoś takiego, pozostawiając wiele aplikacji internetowych (i innych serwerów) otwartych na atak DoS na podstawie kolizji produkcyjnych. (Artykuł pochodzi z 2003 r., Ale sugeruje, że Dan Bernstein odkrył ten sam pomysł nieco wcześniej).

Szybkie wyszukiwanie w Google zapewnia, że ​​najnowocześniejsze rozwiązania w zakresie wdrożeń uległy poprawie, a nie poprawie .

Inną kwestią jest to, że w świecie o wysokiej przepustowości ataki czasowe sprawiają, że znalezienie kolizji w Internecie nie jest tak trudne (w przeciwieństwie do offline, jak sugeruje link Crosby-Wallach). Wydaje mi się, że pamiętam, że Daniel Golovin kilka lat temu miał wyniki dotyczące struktur danych, które nie są podatne na ataki w czasie, ale nie wiem, czy są one powszechnie stosowane.

Analiza średnich przypadków dla tablic skrótów jest wykonywana przy zwykłym założeniu jednorodności danych wejściowych, co raz robi się z powodu brzytwy Ockhama.

Jeśli masz dodatkową wiedzę na temat domeny i dystrybucji kluczy, możesz wykonać tę samą analizę średnich przypadków i zastąpić dystrybucję jednolitą dystrybucją i ponownie obliczyć oczekiwania, przynajmniej teoretycznie.

Oczywiście trudność wynika z faktu, że trudna jest niejednolita analiza przypadków średnich. A twoja „wiedza” może nie być wygodna do wyrażenia jako rozkład, który można łatwo wykorzystać w takiej analizie.

Oczywiście najłatwiejszą rzeczą są symulacje. Zaimplementuj tabele skrótów i obserwuj ich działanie dla typowego zestawu danych wejściowych.

Permutacje (o ustalonej długości), jako szczególny przypadek skończonych znanych zbiorów: stosunkowo łatwo przypisać unikalne liczby permutacjom, jak w tym artykule . Użyłem tego (w nieco mniej upiornej implementacji) do mapowania permutacji długości$n$ do tablicy rozmiarów $n!$. Ale mogłem to zrobić, ponieważ w końcu będę potrzebował każdej permutacji; jeśli używasz tylko podzbioru, potrzebujesz funkcji dostosowanej do tego podzbioru lub wydajnej rzadkiej tablicy.