Haszowanie i struktury probabilistyczne

Schemat haszowania dla statycznego zbioru kluczy gwarantujący brak kolizji i wyszukiwanie w stałym czasie pesymistycznym.

Schemat losowego wyboru funkcji skrótu z rodziny tak, by prawdopodobieństwo kolizji dwóch kluczy było małe niezależnie od danych wejściowych.

Schemat haszowania z dwiema funkcjami skrótu, w którym wstawiany element wypiera dotychczasowy zajmujący pozycję, gwarantując stały czas wyszukiwania pesymistyczny.

Metoda rozwiązywania kolizji, w której wszystkie elementy są przechowywane w samej tablicy, a przy zajętości pozycji szuka się kolejnych wg sekwencji prób.

Technika adresowania otwartego, w której krok przeszukiwania sekwencji prób wyznacza druga funkcja skrótu, redukując grupowanie.

Sytuacja, w której funkcja skrótu przypisuje tę samą wartość dwóm różnym kluczom wejściowym.

Metoda rozwiązywania kolizji polegająca na przechowywaniu wszystkich elementów o tej samej wartości skrótu na liście powiązanej z daną pozycją tablicy.

Deterministyczna funkcja odwzorowująca dane wejściowe dowolnego rozmiaru na wartość o stałym rozmiarze, używana do indeksowania i wyszukiwania.

Struktura danych przechowująca pary klucz-wartość, w której pozycję elementu wyznacza funkcja skrótu, dająca średnio stały czas dostępu.

Probabilistyczna struktura testująca przynależność, oparta na tablicy odcisków i przemieszczaniu kukułczym; wspiera usuwanie elementów, czego brak filtrowi Blooma.

Probabilistyczna struktura szacująca częstość elementów w strumieniu za pomocą tablicy liczników indeksowanej wieloma funkcjami skrótu; zawyża, nigdy nie zaniża.

Probabilistyczna struktura szacująca liczbę unikalnych elementów (kardynalność) strumienia danych przy stałym, bardzo małym zużyciu pamięci.