Sondowanie liniowe

Kolizja między Johnem Smithem i Sandrą Dee (oboje haszują do komórki 873) jest rozwiązywana przez umieszczenie Sandry Dee w następnej wolnej lokalizacji, komórce 874.

Sondowanie liniowe to schemat w programowaniu komputerowym do rozwiązywania kolizji w tablicach skrótów , strukturach danych do utrzymywania zbioru par klucz-wartość i wyszukiwania wartości powiązanej z danym kluczem. Został wynaleziony w 1954 roku przez Gene'a Amdahla , Elaine M. McGraw i Arthura Samuela , a po raz pierwszy przeanalizowany w 1963 roku przez Donalda Knutha .

Wraz z sondowaniem kwadratowym i podwójnym mieszaniem , sondowanie liniowe jest formą adresowania otwartego . W tych schematach każda komórka tablicy skrótów przechowuje pojedynczą parę klucz-wartość. Gdy funkcja skrótu powoduje kolizję poprzez mapowanie nowego klucza do komórki tablicy skrótów, która jest już zajęta przez inny klucz, sondowanie liniowe przeszukuje tabelę w poszukiwaniu najbliższego wolnego miejsca i wstawia tam nowy klucz. Wyszukiwanie odbywa się w ten sam sposób, przeszukując tabelę sekwencyjnie, zaczynając od pozycji podanej przez funkcję haszującą, aż do znalezienia komórki z pasującym kluczem lub pustej komórki.

Jak piszą Thorup i Zhang (2012) : „Tabele skrótów są najczęściej używanymi nietrywialnymi strukturami danych, a najpopularniejsza implementacja na standardowym sprzęcie wykorzystuje sondowanie liniowe, które jest zarówno szybkie, jak i proste”. Sondowanie liniowe może zapewnić wysoką wydajność ze względu na dobrą lokalizację odniesienia , ale jest bardziej wrażliwe na jakość swojej funkcji mieszającej niż niektóre inne schematy rozwiązywania kolizji. Wyszukiwanie, wstawianie lub usuwanie zajmuje stały oczekiwany czas, gdy jest zaimplementowane przy użyciu losowej funkcji skrótu, 5-niezależnej funkcji skrótu lub haszowania tabelarycznego . Dobre wyniki można również osiągnąć w praktyce za pomocą innych funkcji skrótu, takich jak MurmurHash .

Operacje

Sondowanie liniowe jest składnikiem otwartych schematów adresowania do wykorzystania tablicy mieszającej do rozwiązania problemu ze słownikiem . W problemie słownikowym struktura danych powinna utrzymywać zbiór par klucz-wartość podlegający operacjom, które wstawiają lub usuwają pary ze zbioru lub wyszukują wartość powiązaną z danym kluczem. W otwartych rozwiązaniach adresowania tego problemu strukturą danych jest tablica T ( tabela skrótów), której komórki T [ i ] (jeśli nie są puste) przechowują pojedynczą parę klucz-wartość. A funkcja skrótu służy do mapowania każdego klucza do komórki T , w której ten klucz powinien być przechowywany, zwykle szyfrując klucze, tak aby klucze o podobnych wartościach nie były umieszczane blisko siebie w tabeli. Kolizja skrótu występuje, gdy funkcja skrótu mapuje klucz do komórki, która jest już zajęta przez inny klucz. Sondowanie liniowe to strategia rozwiązywania kolizji poprzez umieszczanie nowego klucza w najbliższej następnej pustej komórce.

Szukaj

Aby wyszukać dany klucz x , sprawdzane są komórki T , zaczynając od komórki o indeksie h ( x ) (gdzie h jest funkcją skrótu) i kontynuując do sąsiednich komórek h ( x ) + 1 , h ( x ) + 2 , ..., aż do znalezienia pustej komórki lub komórki, której przechowywany klucz to x . Jeśli zostanie znaleziona komórka zawierająca klucz, wyszukiwanie zwróci wartość z tej komórki. W przeciwnym razie, jeśli zostanie znaleziona pusta komórka, klucz nie może znajdować się w tabeli, ponieważ zostałby umieszczony w tej komórce zamiast jakiejkolwiek późniejszej komórki, która nie została jeszcze przeszukana. W takim przypadku wyszukiwanie zwróci jako wynik, że klucza nie ma w słowniku.

Wprowadzenie

Aby wstawić parę klucz-wartość ( x , v ) do tabeli (ewentualnie zastępując dowolną istniejącą parę tym samym kluczem), algorytm wstawiania stosuje tę samą sekwencję komórek, która byłaby stosowana podczas wyszukiwania, aż do znalezienia pustej komórki lub komórka, której przechowywany klucz to x . Nowa para klucz-wartość jest następnie umieszczana w tej komórce.

Jeśli wstawienie spowodowałoby wzrost współczynnika obciążenia tabeli (jej frakcji zajętych komórek) powyżej pewnego zadanego progu, cała tabela może zostać zastąpiona nową tabelą, większą o stały współczynnik, z nową funkcją haszującą, jak w dynamiczna tablica . Ustawienie tego progu na wartość bliską zeru i użycie wysokiego tempa wzrostu dla rozmiaru tabeli prowadzi do szybszych operacji na tablicy skrótów, ale większego wykorzystania pamięci niż wartości progowe bliskie jedności i niskiego tempa wzrostu. Częstym wyborem byłoby podwojenie rozmiaru stołu, gdy współczynnik obciążenia przekraczałby 1/2, powodując, że współczynnik obciążenia utrzymywałby się między 1/4 a 1/2.

Usunięcie

Po usunięciu pary klucz-wartość może być konieczne przeniesienie innej pary wstecz do jej komórki, aby zapobiec znajdowaniu pustej komórki podczas wyszukiwania przeniesionego klucza.

Możliwe jest również usunięcie pary klucz-wartość ze słownika. Jednak nie wystarczy to zrobić po prostu opróżniając jego celę. Wpłynęłoby to na wyszukiwanie innych kluczy, które mają wartość skrótu wcześniejszą niż opróżniona komórka, ale które są przechowywane na pozycji późniejszej niż opróżniona komórka. Pusta komórka spowodowałaby, że te wyszukiwania nieprawidłowo zgłaszałyby brak klucza.

Zamiast tego, gdy komórka i jest pusta, konieczne jest przeszukanie kolejnych komórek tabeli, aż do znalezienia kolejnej pustej komórki lub klucza, który można przenieść do komórki i (tj. klucza, którego wartość skrótu jest równa lub wcześniej niż i ). Gdy zostanie znaleziona pusta komórka, wówczas opróżnianie komórki i jest bezpieczne i proces kasowania zostaje zakończony. Ale gdy wyszukiwanie znajdzie klucz, który można przenieść do komórki i , wykonuje ten ruch. Ma to wpływ na przyspieszenie późniejszych poszukiwań przesuniętego klucza, ale także opróżnia kolejną komórkę, później w tym samym bloku zajętych komórek. Poszukiwanie ruchomego klucza jest kontynuowane dla nowej, opróżnionej komórki, w ten sam sposób, aż zakończy się dotarciem do komórki, która była już pusta. W tym procesie przenoszenia kluczy do wcześniejszych komórek każdy klucz jest sprawdzany tylko raz. W związku z tym czas potrzebny do zakończenia całego procesu jest proporcjonalny do długości bloku zajętych komórek zawierających usunięty klucz, dopasowując się do czasu wykonania pozostałych operacji tablicy skrótów.

Alternatywnie możliwe jest zastosowanie strategii leniwego usuwania , w której para klucz-wartość jest usuwana poprzez zastąpienie wartości specjalną wartością flagi wskazującą usunięty klucz. Jednak te wartości flag będą miały wpływ na współczynnik obciążenia tabeli skrótów. W przypadku tej strategii może okazać się konieczne wyczyszczenie wartości flag z tablicy i ponowne mieszanie wszystkich pozostałych par klucz-wartość, gdy zbyt duża część tablicy zostanie zajęta przez usunięte klucze.

Nieruchomości

Sondowanie liniowe zapewnia dobrą lokalizację odniesienia , co powoduje, że wymaga kilku niebuforowanych dostępów do pamięci na operację. Z tego powodu, przy niskim lub średnim współczynniku obciążenia, może zapewnić bardzo wysoką wydajność. Jednak w porównaniu z niektórymi innymi otwartymi strategiami adresowania, jego wydajność spada szybciej przy wysokich współczynnikach obciążenia z powodu klastrowania podstawowego , tendencja, że ​​jedna kolizja powoduje więcej pobliskich kolizji. Ponadto osiągnięcie dobrej wydajności tą metodą wymaga wyższej jakości funkcji mieszającej niż w przypadku niektórych innych schematów rozwiązywania kolizji. W przypadku użycia z funkcjami mieszającymi niskiej jakości, które nie eliminują niejednorodności w rozkładzie wejściowym, sondowanie liniowe może być wolniejsze niż inne strategie otwartego adresowania, takie jak podwójne mieszanie , które sonduje sekwencję komórek, których separacja jest określona przez drugą funkcję mieszającą, lub sondowanie kwadratowe , gdzie rozmiar każdego kroku zmienia się w zależności od jego pozycji w sekwencji sondy.

Analiza

Korzystając z sondowania liniowego, operacje słownikowe można realizować w stałym oczekiwanym czasie . Innymi słowy, operacje wstawiania, usuwania i wyszukiwania można zaimplementować w O(1) , o ile współczynnik obciążenia tablicy skrótów jest stałą ściśle mniejszą niż jeden.

Bardziej szczegółowo, czas dla każdej określonej operacji (wyszukiwanie, wstawianie lub usuwanie) jest proporcjonalny do długości ciągłego bloku zajętych komórek, w którym rozpoczyna się operacja. Jeśli wszystkie komórki początkowe są jednakowo prawdopodobne, to w tablicy skrótów z N komórkami maksymalny blok k zajętych komórek będzie miał prawdopodobieństwo k / N zawierania początkowej lokalizacji wyszukiwania i zajmie czas O ( k ) zawsze, gdy jest to lokacja początkowa. Dlatego oczekiwany czas operacji można obliczyć jako iloczyn tych dwóch składników, O ( k ² / N ) , zsumowane po wszystkich maksymalnych blokach ciągłych komórek w tabeli. Podobna suma kwadratów długości bloków daje oczekiwany czas dla losowej funkcji skrótu (a nie dla losowej lokalizacji początkowej w określonym stanie tablicy skrótów), sumując wszystkie bloki, które mogą istnieć (zamiast tych, które faktycznie istnieją w danym stanie tabeli) i pomnożenie terminu dla każdego potencjalnego bloku przez prawdopodobieństwo, że blok jest faktycznie zajęty. Oznacza to, że zdefiniowanie Block( i , k ) jest zdarzeniem, w którym występuje maksymalny ciągły blok zajętych komórek o długości k zaczynając od indeksu i , oczekiwany czas operacji wynosi

${\ Displaystyle E [T] = O (1) + \ suma _ {i = 1} ^ {N} \ suma _ {k = 1} ^ {n} O (k ^ {2} / N) \ operatorname { Pr} [\operatorname {blok} (i,k)].}$

Formułę tę można uprościć, zastępując Block( i , k ) prostszym warunkiem koniecznym Full ( k ) , czyli zdarzeniem, w którym co najmniej k elementów ma wartości skrótu mieszczące się w bloku komórek o długości k . Po tym zastąpieniu wartość w sumie nie zależy już od i , a czynnik 1/ N anuluje N wyrazów sumowania zewnętrznego. Te uproszczenia prowadzą do granicy

${\ Displaystyle E [T] \ równoważnik O (1) + \ suma _ {k = 1} ^ {n} O (k ^ {2}) \ nazwa operatora {Pr} [\ nazwa operatora {pełna} (k)]. }$

Ale przez multiplikatywną postać granicy Chernoffa , gdy współczynnik obciążenia jest ograniczony od jedności, prawdopodobieństwo, że blok o długości k zawiera co najmniej k zaszyfrowanych wartości, jest wykładniczo małe jako funkcja k , powodując, że ta suma jest ograniczona przez stała niezależna od n . Możliwe jest również przeprowadzenie tej samej analizy przy użyciu przybliżenia Stirlinga zamiast wiązania Chernoffa, aby oszacować prawdopodobieństwo, że blok zawiera dokładnie k zaszyfrowanych wartości.

Pod względem współczynnika obciążenia α , oczekiwany czas pomyślnego wyszukiwania wynosi O (1 + 1/(1 − α )) , a oczekiwany czas nieudanego wyszukiwania (lub wprowadzenia nowego klucza) to O (1 + 1/(1 - α ) ² ) . Dla stałych współczynników obciążenia, z dużym prawdopodobieństwem, najdłuższa sekwencja sondy (spośród sekwencji sond dla wszystkich kluczy zapisanych w tabeli) ma długość logarytmiczną.

Wybór funkcji haszującej

Ponieważ sondowanie liniowe jest szczególnie wrażliwe na nierównomiernie rozłożone wartości skrótu, ważne jest, aby połączyć je z wysokiej jakości funkcją mieszającą, która nie powoduje takich nieregularności.

Powyższa analiza zakłada, że ​​skrót każdego klucza jest liczbą losową niezależną od skrótów wszystkich pozostałych kluczy. To założenie jest nierealne dla większości zastosowań mieszania. Jednak losowe lub pseudolosowe wartości skrótu mogą być używane podczas mieszania obiektów według ich tożsamości, a nie według ich wartości. Na przykład odbywa się to za pomocą sondowania liniowego przez klasę IdentityHashMap środowiska kolekcji Java . Wartość hash, którą ta klasa kojarzy z każdym obiektem, jej identityHashCode, gwarantuje, że pozostanie niezmieniona przez cały okres istnienia obiektu, ale poza tym jest dowolna. Ponieważ IdentityHashCode jest konstruowany tylko raz na obiekt i nie musi być powiązany z adresem ani wartością obiektu, jego konstrukcja może wymagać wolniejszych obliczeń, takich jak wywołanie generatora liczb losowych lub pseudolosowych. Na przykład Java 8 używa Xorshift do konstruowania tych wartości.

W przypadku większości zastosowań haszowania konieczne jest obliczenie funkcji skrótu dla każdej wartości za każdym razem, gdy jest ona haszowana, a nie tylko raz, gdy tworzony jest jej obiekt. W takich aplikacjach liczby losowe lub pseudolosowe nie mogą być używane jako wartości skrótu, ponieważ wtedy różne obiekty o tej samej wartości miałyby różne wartości skrótu. I kryptograficzne funkcje skrótu (które są zaprojektowane tak, aby były obliczeniowo nie do odróżnienia od prawdziwie losowych funkcji) są zwykle zbyt wolne, aby można ich było używać w tablicach mieszających. Zamiast tego opracowano inne metody konstruowania funkcji mieszających. Te metody szybko obliczają funkcję skrótu i ​​można udowodnić, że działają dobrze z sondowaniem liniowym. W szczególności sondowanie liniowe zostało przeanalizowane w ramach k -niezależnego mieszania , klasy funkcji mieszających, które są inicjowane z małego losowego materiału siewnego i które z równym prawdopodobieństwem odwzorowują dowolną k -krotkę różnych kluczy na dowolną k -krotkę indeksy. parametr k można traktować jako miarę jakości funkcji skrótu: im większe k , tym więcej czasu zajmie obliczenie funkcji skrótu, ale będzie ona zachowywać się bardziej podobnie do całkowicie losowych funkcji. W przypadku sondowania liniowego wystarczy 5-niezależność, aby zagwarantować stały oczekiwany czas na operację, podczas gdy niektóre 4-niezależne funkcje skrótu działają źle, zajmując czas do logarytmu na operację.

Inną metodą konstruowania funkcji mieszających, charakteryzujących się zarówno wysoką jakością, jak i praktyczną szybkością, jest mieszanie tabelaryczne . W tej metodzie wartość skrótu dla klucza jest obliczana przy użyciu każdego bajtu klucza jako indeksu w tablicy liczb losowych (z inną tabelą dla każdej pozycji bajtu). Liczby z tych komórek tabeli są następnie łączone za pomocą bitowego wyłącznego lub operacja. Funkcje skrótu skonstruowane w ten sposób są niezależne tylko od 3. Niemniej jednak sondowanie liniowe przy użyciu tych funkcji skrótu wymaga stałego oczekiwanego czasu na operację. Zarówno mieszanie tabelaryczne, jak i standardowe metody generowania 5-niezależnych funkcji mieszających są ograniczone do kluczy, które mają stałą liczbę bitów. Aby obsłużyć ciągi lub inne typy kluczy o zmiennej długości, możliwe jest skomponowanie prostszej uniwersalnej techniki haszowania , która odwzorowuje klucze na wartości pośrednie, oraz funkcji skrótu wyższej jakości (niezależnej od 5 lub tabelarycznej), która odwzorowuje wartości pośrednie na tablicę skrótów indeksy.

W porównaniu eksperymentalnym Richter i in. okazało się, że rodzina funkcji skrótu Multiply-Shift (zdefiniowana jako ${\ displaystyle h_ {z} (x) = (x \ cdot z {\ bmod {2}}^{w})\div 2^{wd}}$ ) była „najszybszą funkcją skrótu po zintegrowaniu ze wszystkimi schematami haszowania, tj. zapewniała najwyższą przepustowość, a także dobrą jakość”, podczas gdy mieszanie tabelaryczne dawało „najniższą przepustowość”. Zwracają uwagę, że każde przeszukanie tabeli wymaga kilku cykli, co jest droższe niż proste operacje arytmetyczne. Stwierdzili również, MurmurHash jest lepszy niż mieszanie tabelaryczne: „Badając wyniki dostarczone przez Mult i Murmur, uważamy, że kompromis za pomocą tabeli (...) jest mniej atrakcyjny w praktyce”.

Historia

Pomysł na tablicę asocjacyjną , która umożliwia dostęp do danych na podstawie ich wartości, a nie adresu, pochodzi z połowy lat czterdziestych XX wieku w pracach Konrada Zuse i Vannevara Busha , ale tablice skrótów zostały opisane dopiero w 1953 roku w memorandum IBM przez Hansa Petera Luhna . Luhn zastosował inną metodę rozwiązywania kolizji, łańcuchowanie, zamiast sondowania liniowego.

Knuth ( 1963 ) podsumowuje wczesną historię sondowania liniowego. Była to pierwsza otwarta metoda adresowania i pierwotnie była synonimem otwartego adresowania. Według Knutha, po raz pierwszy użyli go Gene Amdahl , Elaine M. McGraw (z domu Boehme) i Arthur Samuel w 1954 roku w programie asemblera dla komputera IBM 701 . Pierwszy opublikowany opis sondowania liniowego jest autorstwa Petersona (1957) , który również przypisuje Samuelowi, Amdahlowi i Boehme'owi, ale dodaje, że „system jest tak naturalny, że bardzo prawdopodobne, że mógł zostać wymyślony niezależnie przez innych przed lub później”. Inną wczesną publikacją tej metody był sowiecki badacz Andriej Erszow w 1958 roku.

Pierwszą teoretyczną analizę sondowania liniowego, pokazującą, że operacja zajmuje stały oczekiwany czas z losowymi funkcjami mieszającymi, przedstawił Knuth. Sedgewick nazywa pracę Knutha „przełomem w analizie algorytmów”. Znaczące późniejsze osiągnięcia obejmują bardziej szczegółową analizę rozkładu prawdopodobieństwa czasu działania oraz dowód, że sondowanie liniowe przebiega w stałym czasie na operację z praktycznie użytecznymi funkcjami mieszającymi, a nie z wyidealizowanymi funkcjami losowymi przyjętymi we wcześniejszej analizie.