Haszowanie 2-wyborowe

Mieszanie 2-wyborów , znane również jako łączenie 2-wyborów , to „wariant tablicy mieszającej , w której klucze są dodawane przez mieszanie z dwiema funkcjami mieszającymi . Klucz jest umieszczany w pozycji tablicy z mniejszą liczbą (kolidujących) kluczy. Niektóre potrzebny jest schemat rozwiązywania kolizji , chyba że klucze są przechowywane w zasobnikach. Średni koszt udanego wyszukiwania to ${\ Displaystyle O (2 + (m-1) / n) }$ , gdzie $to$ liczba kluczy, a to rozmiar tablicy. Najwięcej kolizji to $log$ $Displaystyle \$ z dużym prawdopodobieństwem."

Jak to działa

Haszowanie 2-wyborowe wykorzystuje dwie funkcje haszujące h ₁ ( x ) i h ₂ ( x ), które działają tak, jak oczekuje się od funkcji mieszających (tj. odwzorowują liczby całkowite z wszechświata na określony zakres). Dwie funkcje skrótu powinny być niezależne i nie mieć ze sobą korelacji. Posiadanie dwóch funkcji skrótu pozwala każdemu kluczowi x mieć do dwóch potencjalnych lokalizacji do przechowywania w oparciu o wartości odpowiednich wyjść, h ₁ ( x ) i h ₂ ( x ). Należy zauważyć, że chociaż istnieją dwie funkcje skrótu, istnieje tylko jedna tabela; obie funkcje skrótu odwzorowują lokalizacje w tej tabeli.

Realizacja

Najważniejszymi funkcjami implementacji haszującej w tym przypadku są wstawianie i wyszukiwanie.

Wstawianie: podczas wstawiania wartości obu funkcji skrótu są obliczane dla obiektu, który ma zostać wstawiony. Obiekt jest następnie umieszczany w wiadrze, który zawiera mniej obiektów. Jeśli zasobniki są równej wielkości, domyślną lokalizacją jest h ₁ ( x ).
Wyszukiwanie: Skuteczne wyszukiwanie polega na wyszukiwaniu żądanej wartości w obu zasobnikach (lokalizacjach zasobników, do których odwzorowano h ₁ ( x ) i h ₂ ( x )).

Wydajność

Podobnie jak w przypadku wszystkich tablic mieszających, wydajność jest oparta na największym wiadrze. Chociaż istnieją przypadki, w których rozmiary zasobników są duże w oparciu o wartości i użyte funkcje skrótu, jest to rzadkie. Posiadanie dwóch funkcji skrótu, a zatem dwóch możliwych lokalizacji dla dowolnej wartości, sprawia, że możliwość wystąpienia dużych zasobników jest jeszcze mniej prawdopodobna.

Oczekiwany rozmiar zasobnika podczas korzystania z haszowania z dwoma wyborami to: $θ (log(log(n)))$ . Ta poprawa wynika z losowej koncepcji znanej jako The Power of Two Choices.

Użycie dwóch funkcji skrótu zapewnia znaczne korzyści w porównaniu z pojedynczą funkcją skrótu. Istnieje niewielka poprawa (i brak zmian w oczekiwanych statystykach zamówień), jeśli używane są więcej niż dwie funkcje skrótu: „Dodatkowe funkcje skrótu zmniejszają maksimum tylko o stały współczynnik”.

w niektórych pamięciach podręcznych procesora typ mieszania 2-wyborowego, zwany dwukierunkową skośną asocjacyjną pamięcią podręczną .

Mieszanie 2-lewe - przy użyciu dwóch tablic mieszających o równym rozmiarze n / 2 i asymetryczne rozwiązywanie powiązań przez umieszczenie klucza w lewej tablicy mieszającej - ma mniej kolizji, a zatem lepszą wydajność niż mieszanie 2-wyborowe z jedną dużą tablicą mieszającą o rozmiarze n . ^{[ potrzebne pełne cytowanie ]}

Ten artykuł zawiera materiały należące do domeny publicznej autorstwa Paula E. Blacka. „Haszowanie z dwoma wyborami” . Słownik algorytmów i struktur danych . NIST .

Dalsza lektura

Azar, Yossi; Broder, Andrzej Z.; Karlin, Anna R.; Upfal, Eli (23–25 maja 1994), „Balanced Allocations (streszczenie rozszerzone)” (PDF) , Proceedings of the 26th Annual Symposium ACM on Theory of computing - STOC '94 , Montreal, s. 593–602, CiteSeerX 10.1.1.38.5375 , doi : 10.1145/195058.195412 , ISBN 0897916638 , S2CID 1014349
Azar, Yossi; Broder, Andrzej Z.; Karlin, Anna R.; Upfal, Eli (1999), „Zrównoważone przydziały” (PDF) , SIAM J. Comput. , 29 (1): 180–200, doi : 10.1137/S0097539795288490