Podwójne haszowanie

Podwójne haszowanie to technika programowania komputerowego używana w połączeniu z otwartym adresowaniem w tablicach skrótów w celu rozwiązywania kolizji skrótów , przy użyciu wtórnego skrótu klucza jako przesunięcia w przypadku wystąpienia kolizji. Podwójne mieszanie z otwartym adresowaniem to klasyczna struktura danych w tabeli ${\ displaystyle T}$ .

Technika podwójnego haszowania wykorzystuje jedną wartość skrótu jako indeks w tabeli, a następnie wielokrotnie przechodzi do przodu o przedział, aż do znalezienia żądanej wartości, osiągnięcia pustej lokalizacji lub przeszukania całej tabeli; ale ten przedział jest ustalany przez drugą, niezależną funkcję mieszającą . W przeciwieństwie do alternatywnych metod rozwiązywania kolizji sondowania liniowego i kwadratowego , interwał zależy od danych, więc wartości mapowane do tej samej lokalizacji mają różne sekwencje przedziałów; minimalizuje to powtarzające się kolizje i skutki grupowania.

$displaystyle h_ {2}}$ dwie losowe, jednolite i niezależne funkcje skrótu i ${\$ , to $displaystyle i}$ w sekwencji wiadra dla wartości $displaystyle k}$ ${$ w tablicy skrótów ${\ Displaystyle | T |}$ wiadra to: ${\ Displaystyle h (i, k) = (h_ {1} (k) + i \ cdot h_ {2} (k)) {\ bmod {|}} T |.} Ogólnie rzecz biorąc, h 1 {$ \ $}}$ ${$ $uniwersalnych$ i są z zestawu funkcji mieszających ; ${\ displaystyle h_ {1}}$ jest wybrany tak, aby miał zakres ${\ Displaystyle \ {0, | T | -1 \}}$ i ${\ Displaystyle h_ {2}}$ mieć zakres ${\ Displaystyle \ {1, | T | -1 \}}$ . Podwójne mieszanie przybliża rozkład losowy; $,$ niezależne parami funkcje skrótu dają prawdopodobieństwo, będzie podążać za tą

Wybór h ₂ (k)

Wtórna funkcja skrótu powinna mieć kilka cech: ${\ Displaystyle h_ {2} (k)}$

nigdy nie powinien dawać indeksu równego zero
powinien przechodzić przez całą tabelę
powinno być bardzo szybkie do obliczenia
powinno być parami niezależne od ${\ Displaystyle h_ {1} (k)}$
$jest$ dystrybucji . Jest to analogiczne do generatora liczb losowych.
${\ Displaystyle h_ {2} (k)}$ być względnie pierwsze do | T |.

W praktyce:

Jeśli mieszanie dzielenia jest używane dla obu funkcji, dzielniki są wybierane jako liczby pierwsze.
Jeśli T $zawsze$ potęgą 2, pierwsze i ostatnie wymagania są zwykle spełnione, powodując, że nieparzystą Ma to efekt uboczny w postaci podwojenia szansy na kolizję z powodu jednego zmarnowanego bitu.

Analiza

Niech ${\ displaystyle n}$ będzie liczbą elementów przechowywanych w $displaystyle$ a następnie współczynnik obciążenia $T} wynosi$ ${\ Displaystyle \ alfa = n/| T |}$ . To znaczy $jednolitego$ $i$ i niezależnego wybrania dwóch $uniwersalnych$ funkcji mieszających i podwójną . Wszystkie $h_ {2}$ są umieszczane w $haszowaniu$ przy użyciu i $displaystyle$ . Biorąc pod uwagę klucz , -st lokalizacja skrótu jest obliczana przez: ${\ Displaystyle (i + 1$ $)$

{\ Displaystyle h (i, k) = (h_ {1} (k) + i \ cdot h_ {2} (k)) {\ bmod {|}} T |.}

Niech mają $stały$ współczynnik obciążenia ${\ Displaystyle \ alpha: 1> \ alpha > 0$ . Bradford i Katehakis wykazali, że oczekiwana liczba sond do nieudanego wyszukiwania w $,$ używając tych początkowo wybranych funkcji skrótu, wynosi ${\ Displaystyle {\ tfrac {1} {1-\ alpha}} }$ niezależnie od rozkładu wejść. Wystarczy parami niezależność funkcji skrótu.

Podobnie jak wszystkie inne formy otwartego adresowania, podwójne mieszanie staje się liniowe, gdy tablica mieszająca zbliża się do maksymalnej pojemności. Zwykła heurystyka polega na ograniczeniu ładowania tabeli do 75% pojemności. W końcu konieczne będzie ponowne haszowanie do większego rozmiaru, tak jak w przypadku wszystkich innych otwartych schematów adresowania.

Warianty

$y) = - h_ {2} (x)}$ wskazuje, że podwójne mieszanie daje niepożądane równoważne funkcje mieszające, gdy $filtrach$ Blooma : i ${\ Displaystyle h_ {1} (y) = h_ {1} (x) + k \ cdot h_ {2} (x)}$ , wtedy ${\ Displaystyle h (i, y) = h (ki, x)}$ i zbiory skróty ${\ Displaystyle \ lewo \ {h (0, x) ..., h (k, x) \ prawo \} = \ lewo \ {h (0, y) .. .,h(k,y)\right\}}$ są identyczne. To sprawia, że kolizja jest dwa razy bardziej prawdopodobna niż oczekiwana ${\ Displaystyle 1/| T | ^ {2}}$ .

Istnieje dodatkowo znaczna liczba w większości nakładających się zestawów skrótów; jeśli ${\ Displaystyle h_ {2} (y) = h_ {2} (x)}$ i ${ \ Displaystyle h1 (y) = h_ {1} (x) \ pm h_ {2} (x)}$ , a następnie ${\ Displaystyle h (i, y) =h(i\pm 1,x)} i porównywanie dodatkowych wartości skrótu ($ $)$ zakresu nie pomaga.

Potrójne haszowanie

Dodanie wyrażenia kwadratowego ${\ Displaystyle i ^ {2},}$ ${\ Displaystyle i (i + 1) / 2}$ ( liczba trójkątna ) lub nawet ${\ Displaystyle i ^ {2} \ cdot h_ {3} (x)}$ ( potrójne haszowanie ) do funkcji skrótu nieco poprawia funkcję skrótu, ale nie rozwiązuje tego problemu; Jeśli:

{\ Displaystyle h_ {1} (y) = h_ {1} (x) + k \ cdot h_ {2} (x) + k ^ {2} \ cdot h_ {3} (x),}

{\ Displaystyle h_{2}(y)=-h_{2}(x)-2k\cdot h_{3}(x)}

i

{\ displaystyle h_ {3} (y) = h_ {3} (x).}

Następnie

{\ Displaystyle {\ rozpocząć {wyrównane} h (ki, y) & = h_ {1} (y) + (ki) \ cdot h_ {2} (y) + (ki) ^ {2} \ cdot h_ {3 }(y)\\&=h_{1}(y)+(ki)(-h_{2}(x)-2kh_{3}(x))+(ki)^{2}h_{3}( x)\\&=\ldots \\&=h_{1}(x)+kh_{2}(x)+k^{2}h_{3}(x)+(ik)h_{2}(x )+(i^{2}-k^{2})h_{3}(x)\\&=h_{1}(x)+ih_{2}(x)+i^{2}h_{3 }(x)\\&=h(i,x).\\\koniec{wyrównany}}}

Ulepszone podwójne haszowanie

Dodanie terminu sześciennego $rozwiązuje$ ( ${3}$ problem, Displaystyle ^ technika znana jako ulepszone podwójne mieszanie . Można to skutecznie obliczyć przez różnicowanie w przód :

 	

          






          

	        

	   0      
		  
		  	
		  	
		       	
	
 klucz  struktury  ;  /// Nieprzezroczyste  /// W razie potrzeby użyj innych typów danych. (Musi być unsigned dla gwarantowanego zawijania.)   extern  unsigned  int  h1  (  struct  key  const  *  ),  h2  (  struct  key  const  *  );  /// Oblicz wartości skrótu k z dwóch bazowych funkcji skrótu  /// h1() i h2() przy użyciu ulepszonego podwójnego skrótu. Po powrocie   /// hasze[i] = h1(x) + i*h2(x) + (i*i*i - i)/6.  /// Korzysta z automatycznego zawijania (redukcji modułowej)  /// typów bez znaku w C.  void  ext_dbl_hash  (  struct  key  const  *  x  ,  unsigned  int  hashes  [],  unsigned  int  n  )  {  unsigned  int  a  =  h1  (  x  ),  b  =  h2  (  x  ),  ja  ;  dla  (  ja  =  ;  ja  <  n  ;  ja  ++  )  {  hasze  [  ja  ]  =  za  ;  za  +=  b  ;  // Dodaj kwadratową różnicę, aby otrzymać sześcienny  b  +=  i  ;  // Dodaj różnicę liniową, aby otrzymać kwadratową  // i++ dodaje stałą różnicę, aby otrzymać liniową  }  }

Oprócz rozwiązania problemu kolizji, ulepszone podwójne mieszanie usuwa również ograniczenia numeryczne podwójnego mieszania dotyczące $,$ mieszania podobną pod względem właściwości do ( niezależnie od) ${\ displaystyle h_ {1}}$ do użycia.

Zobacz też

Linki zewnętrzne

Jak buforowanie wpływa na mieszanie , Gregory L. Heileman i Wenbin Luo 2005.
Animacja tablicy skrótów
klib biblioteka C, która zawiera funkcję podwójnego haszowania.