Haszowanie spiralne

Spiralne haszowanie , znane również jako Spiral Storage, to rozszerzalny algorytm haszujący. Podobnie jak we wszystkich schematach mieszania, haszowanie spiralne przechowuje rekordy w różnej liczbie segmentów, używając klucza rekordu do adresowania. W rozwijającym się mieszaniu liniowym plik, zasobniki są dzielone w określonej kolejności. Powoduje to dodanie nowego zasobnika na końcu pliku. Chociaż pozwala to na stopniową reorganizację pliku, oczekiwana liczba rekordów w nowo utworzonym zasobniku i zasobniku z tego, co dzieli, spada do połowy poprzedniej liczby. Podjęto kilka prób złagodzenia tego nagłego spadku wykorzystania przestrzeni. Spiralne przechowywanie Martina wykorzystuje inne podejście. Plik składa się z szeregu stale numerowanych wiader. Zasobniki o niższych numerach (po lewej) mają wyższą oczekiwaną liczbę rekordów. Kiedy plik się rozwija, najbardziej wysunięty na lewo zasobnik jest zastępowany przez dwa zasobniki po prawej stronie. Istnieją pewne warianty tego pomysłu.

Mieszanie spiralne wymaga jednolitej funkcji skrótu kluczy rekordów w przedziale jednostkowym ${\ Displaystyle [0,1]}$ . Jeśli plik mieszający zaczyna się od wiadra $+h(k)\in [S,S+1]}$ $klucz$ jest na liczbę rzeczywistą $S$ ${\ Displaystyle x =$ . Adres końcowy jest następnie obliczany jako ${\ Displaystyle \ lfloor d ^ {x} \ rfloor}$ gdzie ${\ Displaystyle d}$ jest „współczynnikiem rozszerzenia”. Gdy zwiększa się, $po$ $.$ stronie tworzone są w przybliżeniu nowe Larson przeprowadził eksperymenty, które wykazały, że mieszanie liniowe nadal ma lepszą wydajność niż mieszanie spiralne.

Zobacz też