Nr 01 · Słownik · Teoria informatyki · Algorytmy i struktury danych

Haszowanie i struktury probabilistyczne

12 pojęć w 8 podgrupach, z prostymi definicjami i źródłami.

Haszowanie teoretyczne · 2

  • 01haszowanie doskonałeperfect hashingSchemat haszowania dla statycznego zbioru kluczy gwarantujący brak kolizji i wyszukiwanie w stałym czasie pesymistycznym.
  • 02haszowanie uniwersalneuniversal hashingSchemat 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.

Haszowanie zaawansowane · 1

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

Kolizje · 4

  • 01adresowanie otwarteopen addressingMetoda 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.
  • 02haszowanie dwukrotnedouble hashingTechnika adresowania otwartego, w której krok przeszukiwania sekwencji prób wyznacza druga funkcja skrótu, redukując grupowanie.
  • 03kolizja haszującaSytuacja, w której funkcja skrótu przypisuje tę samą wartość dwóm różnym kluczom wejściowym.
  • 04łańcuchowaniechainingMetoda 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.

Podstawy haszowania · 1

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

Struktury haszujace · 1

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

Struktury probabilistyczne · 1

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

Szacowanie czestosci · 1

  • 01szkic Count-MinCount-Min sketchProbabilistyczna 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.

Szacowanie kardynalnosci · 1

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

Pozostałe grupy — Algorytmy i struktury danych

Grupa pojęć · Algorytmy i struktury danych12 haseł